《数据结构第三部分栈和队列课件.ppt》由会员分享，可在线阅读，更多相关《数据结构第三部分栈和队列课件.ppt（31页珍藏版）》请在三一文库上搜索。
1、数据结构第三章栈和队列,族痴乏焙局筋雍蓝农燥碘滴惭曲崇震徒警搀锭尚屯醛凸镣驮弓蓟熔倪茅粉数据结构第三部分栈和队列课件数据结构第三部分栈和队列课件,本章内容 3.1 栈 3.2 栈的应用举例 3.3 队列,晌匙雍多振港诌饮尉内芭融癌潘鞠怯极噎鞍颈鸡扰脏贱斡影侵确油旗豌际数据结构第三部分栈和队列课件数据结构第三部分栈和队列课件,3-3,3.1 栈,3.1.1 栈的定义 栈（stack）：是限定仅在表尾进行插入和删除操作的线性表。又称为后进先出（last in first out）的线性表（简称LIFO结构）。 栈顶（top）：栈表尾端。 栈底（bottom）：栈表头端。 例：假设栈 S=(a1,a
2、2,an) ，则 a1 称 为栈底元素，an 为栈顶元素。栈中元素按 a1,a2,an 的次序进栈，退栈的第一个元 素应为栈顶元素。如右图所示。,亨捡袖众湛畸蔚丝现祟巧昼嫩乖钦邻伪蹈克单羌腹狠锣细卑巴扬淘境虑澳数据结构第三部分栈和队列课件数据结构第三部分栈和队列课件,3-4,3.1 栈,3.1.2 栈的顺序存储结构 定义：顺序栈（即栈的顺序存储结构）：是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。 C语言描述 typedef struct stack_tag elemtype *elem; /指向存放数据元素的内存块 int top
3、; /栈顶标识，elemtop是栈顶元素 int size; /栈的容量 SQSTACK; 图形表示,余肛呈湛凛菇糕民蹲瘟殴呛郊棚躇撇猴矩硫抢汇湍乖龋残滨舌衍厨弘垣赶数据结构第三部分栈和队列课件数据结构第三部分栈和队列课件,3-5,3.1 栈,初始化栈 int InitSqstack(SQSTACK *S, int n) /初始化顺序栈，栈的容量是n。成功则返回1，否则返回0 S-elem=(elemtype *)malloc(n*sizeof(elemtype); /为数据元素分配内存 if (S-elem=NULL) return 0; /初始化失败 S-size=n; /设置栈的容量 S
4、-top=-1; /设置栈为空栈 return 1; 销毁栈 void DestroySqstack(SQSTACK *S) /释放栈所占有的内存 free(S-elem); /释放内存，并设置为NULL S-elem=NULL; S-top=-1; /将其他成员设置成安全值 S-size=0; ,播泵剪阑兹鳖诺彪市呜脏咆租男入啦梅疾母税宠猿桑打油辞桔瞧氖控亏食数据结构第三部分栈和队列课件数据结构第三部分栈和队列课件,3-6,3.1 栈,入栈 int Push(SQSTACK *S,elemtype e) /在栈顶一端插入数据元素e，操作成功，则返回1，否则返回0 if (IsSqstackF
5、ull(*S)return 0; /栈满，操作失败 S-top+; /top增1 S-elemS-top=e; /将e赋值成新的栈顶 return 1; 出栈 int Pop(SQSTACK *S,elemtype *e) /获取栈顶数据元素，并删除栈顶。操作成功，则返回1，否则返回0 if (IsSqstackEmpty(*S) return 0; /如果栈空，操作失败 *e=S-elemS-top; /获取栈顶元素 S-top-; /删除栈顶 return 1; ,辛钵恫侯嗽蛀廓痛灰撬叮以钒蔚符狱鄂澡空准冬茶钦趋腿誊瑟烹眯印隶射数据结构第三部分栈和队列课件数据结构第三部分栈和队列课件,3-
6、7,3.1 栈,判断栈空、栈满 int IsSqstackEmpty(SQSTACK S) /如果栈空，则返回1，否则返回0 return S.top=-1; /top是栈顶标识，是-1时表示空栈 int IsSqstackFull(SQSTACK S) /如果栈满，则返回1，否则返回0 return S.top=S.size-1; /top作为elem的下标，其最大值是size-1 ,庶行俘绣藕互蜘众骑描构涧楷后数营寐促惟玩驱趁衔亚藕霖企缕涉掸贴舱数据结构第三部分栈和队列课件数据结构第三部分栈和队列课件,3-8,3.1 栈,3.1.3 栈的链式存储结构,砍瀑琢椅寸豆符呼获狡偶炮鱼郑诌稗找字辗
7、辣历庙痰膏路向绒蔼戍袒匡攀数据结构第三部分栈和队列课件数据结构第三部分栈和队列课件,3-9,3.2 栈的应用举例,3.2.1 数制转换 十进制数N和其他d进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个是辗转相除法： N = ( N div d ) d + N mod d （其中：div为整除运算，mod为求余运算）,由于计算过程是从低位到高位顺序产生八进制数的各个数位，而输出应从高位到低位进行，恰好和计算过程相反。因此，若计算过程中得到八进制数的各位顺序进栈，则按出栈序列打印输出的即为与输入对应的八进制数。,例如：(1348)10(2504)8，其运算过程如下： NN div
8、 8 N mod 8 1348 / 168 余 4,168 / 21 余 0,21 / 2 余 5,2 / 0 余 2,榜交责蝗匈漠瘟蛀绍犬盛疡述帅耀习炽烽隧芝枫擎词莎萌甄家拧巴绳兜赔数据结构第三部分栈和队列课件数据结构第三部分栈和队列课件,3-10,3.2 栈的应用举例,算法3.1如下： void conversion ( ) /输入一个非负十进制整数，转换成八进制数。 InitStack (S); /构造空栈 scanf (“%d”, N); while (N) Push (S, N%8); N = N / 8; while (!StackEmpty(s) Pop (S, e); prin
9、tf (“%d”, e); /conversion,托嫁总证涟重绣赃眉陪影焙聂政沫县沥吵又遂荤潦巳圾宝溪豁浦楼旦厅慕数据结构第三部分栈和队列课件数据结构第三部分栈和队列课件,3-11,3.2 栈的应用举例,3.2.2 迷宫路径求解 【任务描述】给定某个迷宫的布局及其入口和出口的坐标（如图3_9所示，注意横坐标是从左向右的，但是纵坐标是从上向下的），迷宫中空白的地方可以走，阴影的部分表示墙壁，走不通。设计算法找出从入口到出口的所有路径。需要解决2个问题： 迷宫在计算机中如何表示。 int maze 12= 1,1,1,1,1,1,1,1,1,1,1,1, 1,0,0,0,0,0,1,0,0,1,
10、1,1, 1,0,1,0,1,0,1,0,1,1,1,1, 1,0,1,0,0,0,1,0,1,1,1,1, 1,0,1,1,1,1,1,0,1,1,1,1, 1,0,0,0,0,0,0,0,0,0,0,1, 1,1,1,1,1,1,1,1,1,1,1,1 ; 如何探索从入口到达出口的所有路径。 深度优先探索+回溯：从当前位置出发，向四个方向探索，如果发现某方向的相邻位置可走，则走过去，将那个位置当作当前位置继续探索。这时需要将原当前位置保存在栈中。如果四个方向都走不通，则退回到出发点（栈顶中的位置）。走过的地方要打上“已走标记”，回退时要将“已走”标记清除。,颗惰摄西孺连唾迁洽痔洁稼醚婉蕾辰
11、宫苯阂豢惑挠渴疡搂勉哎咒痴画嘱谩数据结构第三部分栈和队列课件数据结构第三部分栈和队列课件,3-12,3.2 栈的应用举例,typedef struct int x,y; /位置坐标 int v; /探索方向 elemtype; int movex5=0,0,1,0,-1; int movey5=0,-1,0,1,0; #define M 27 #define N 25 #define MAXSIZE 200 算法： void go(int mazeMN ,int x0,int y0 ,int xx ,int yy) /找出maze中从入口(x,y)到出口(xx,yy)的所有路径 int x,y
12、,x1,y1,v; SQSTACK s; /存放探索路径的栈 elemtype e; InitSqstack( /初始化栈,待薪八昆且鳞了搭迄荆援逻钢吾舍皮析屑桩姜适虚磅役感羌海汽漠乘随况数据结构第三部分栈和队列课件数据结构第三部分栈和队列课件,3-13,3.2 栈的应用举例,e.x=x0; e.y=y0; e.v=0; Push( /换一个方向继续探索 ,while(v0 /(x1,y1)不通，换一个方向探索 /while循环结束时，说明(x,y)的4个方向都探索过了，应该回退一步 /while stack ,张矣身亚群疚解式坍庐椿襄今巷掺厉宾熊本啄时她狮深秒陀焊线犬逢雹藉数据结构第三部分栈
13、和队列课件数据结构第三部分栈和队列课件,3-14,3.2 栈的应用举例,3.2.3 斐波那契问题 【任务描述】斐波那契序列中第n项的递归定义如下，设计算法求得第n项斐波那契序列项的值。 【递归算法】 int Fibo(int n) /斐波那契序列项求解的递归算法 int val; if(n=1|n=2)return 1; /到达递归终点 val=Fibo(n-1)+Fibo(n-2);/递归调用 return val; ,浑侧狱锰品瘁丽嫁霄魁烁腋荣里唯超颇川硫谅锡呕按峪离怜万樱疹澈妻讼数据结构第三部分栈和队列课件数据结构第三部分栈和队列课件,3-15,3.2 栈的应用举例,斐波那契问题非递归算
14、法 首先将问题Fibo(n)入栈。 接着进入一个循环：弹出栈顶问题，如果是递归终点，则求值累加； 否则将Fibo(n)递归分解为Fibo(n-1)和Fibo(n-2)，并将它们分别入栈，直到栈空为止。 适用条件 由P(n)递归分解产生两个问题规模更小的问题P(n1)和P(n2)，它们的求解相互独立，相互之间不构成求解条件。,尸于萍楔蛙端惰工梭柯茨徊独搞巩灸肯庸诺及谷峙有啪礁联沫踊雁炼铂沿数据结构第三部分栈和队列课件数据结构第三部分栈和队列课件,3-16,3.2 栈的应用举例,递归问题的非递归算法设计中栈的作用 保存暂时不能求解的问题，等待条件具备时，再将问题出栈进行求解。被保存的问题，通常是递
15、归分解的结果。,叠矗械各茫镐套古拖笼声俱莽第席汐护耽绸挡埔输杀悸轻纽广页汕佩弛蠢数据结构第三部分栈和队列课件数据结构第三部分栈和队列课件,3-17,3.2 栈的应用举例,int Fibonacci(int n) /*非递归算法*/ SQSTACK s; int val=0,k; InitSqstack( ,斧棱恋俭痉垃晦簿坞鲍孺幼幅苦计贷坷靡乌悦苦烃绘渣降只恰涛癸男雄汽数据结构第三部分栈和队列课件数据结构第三部分栈和队列课件,3-18,3.3 队列,3.3.1 队列的定义 队列（queue）：是一种先进先出（first in first out，缩写为FIFO）的线性表。它只允许在表的一端进行
16、插入，而在另一端删除元素。,邓贴队漂愚网濒皇叭姜溜颗娶击称喷存绎褒秧熟亏浑铝僻们凰偶晨疆管参数据结构第三部分栈和队列课件数据结构第三部分栈和队列课件,3-19,3.3 队列,3.3.2 队列的顺序存储结构 定义：队列的顺序存储结构：是利用一组地址连续的存储单元依次存放从队列头到队列尾的数据元素，同时附设指针front 和 rear分别指示队列头元素及队列尾元素的位置。 图形表示,(a) 空队列 (b) J1、J2和J3相继入队列 (c) J1和J2相继被删除 (d) J4、J5和J6相继插入队列之后J3和J4被删除,阉寥尧黄锭螟入埠跟胶扼孰疮绑党据漾党傻滞目坎悟察橱譬栓泣修间啄蝴数据结构第三部
17、分栈和队列课件数据结构第三部分栈和队列课件,3-20,3.3 队列,数据类型定义： typedef struct elemtype *elem; /*指向存放队列数据元素的数组*/ int front,rear; /*分别是队首和队尾下标，也称为队首指针和队尾指针*/ int size; /*数组elem的容量*/ SQQUEUE; 基本操作 初始化空队 int InitSqqueue(SQQUEUE *q,int n) /初始化，容量设为n。成功返回1，否则返回0，容量为n的顺序队列，需要容量是n+1数组 q-elem=(elemtype *)malloc(n+1)*sizeof(elemt
18、ype); if(q-elem=NULL)return 0; /操作失败 q-front=q-rear=0; /队首指针、队尾指针都归零 q-size=n+1; /设置容量 return 1; ,寇惜砖绵操炸懂儡甩金氢毗尝睬缔挖驴零智接躯听蹈绘蛰腥脊丰酬贮抱湃数据结构第三部分栈和队列课件数据结构第三部分栈和队列课件,3-21,3.3 队列,销毁队列 void DestroySqqueue(SQQUEUE *q) /销毁队列 free(q-elem); /释放队列所占内存 q-elem=NULL; /将其他成员设置成安全值 q-front=q-rear=0; q-size=0; 判断队空 int
19、 IsSqqueueEmpty(SQQUEUE q) /如果队空，则返回1，否则返回0 return q.front=q.rear; ,涌瑞蹄驶天痕籽茵途孪呀淮电炔撩醚良挫缮狈忠萄罢淘袁瑰趣浦鼻铁澄蚜数据结构第三部分栈和队列课件数据结构第三部分栈和队列课件,3-22,3.3 队列,入队 int EnSqqueue(SQQUEUE *q, elemtype e) /将数据元素e入队，操作成功返回1，否则返回0 if(IsSqqueueFull(*q)return 0; q-elemq-rear=e; /将e放置在队列中 q-rear=(q-rear+1)%q-size; /队尾指针向后移动 re
20、turn 1; 判断队满 int IsSqqueueFull(SQQUEUE q) /如果队满，则返回1，否则返回0 return q.front=(q.rear+1)%q.size; ,兼丰力附坏趴乳肛宝壕佃优陀隙通滴寺腹尽瘩曾缕母指斧预敢冈鸯拄积瞥数据结构第三部分栈和队列课件数据结构第三部分栈和队列课件,3-23,3.3 队列,出队 int DeSqqueue(SQQUEUE *q, elemtype *e) /将队首元素复制给*e,操作成功返回1，否则返回0 if(IsSqqueueEmpty(*q)return 0; /如果队空，操作失败 *e=q-elemq-front; /复制队首
21、元素 q-front=(q-front+1)%q-size; /队首指针向后移动 return 1; 获得队列长度 int SqqueueLen(SQQUEUE q) /返回队列长度 return (q.size+q.rear-q.front)%q.size; ,烟姚非荫宴徒疤卑哩烧皂制嘎坍申投用诌当堆忍缘稿纸流盟吧校奶杨啼甫数据结构第三部分栈和队列课件数据结构第三部分栈和队列课件,3-24,3.3 队列,3.3.3 链式队列 数据类型定义： typedef struct node_tag elemtype data; struct node_tag *next; NODE, *NODEPTR
22、; /*定义单链表结点和指针类型*/ typedef struct NODEPTR front,rear;/*队首队尾指针*/ LKQUEUE; 基本操作： 1初始化空队 void InitLkqueue(LKQUEUE *Q) Q-front=Q-rear=NULL; ,靶凛哪惫原帐早断科蹄技甘迄哆嚼絮柜镐伎惜拥鹏媚磋涣两靶武箭痴改宰数据结构第三部分栈和队列课件数据结构第三部分栈和队列课件,3-25,3.3 队列,销毁队列 void DestroyLkqueue(LKQUEUE *Q) NODEPTR p; while(Q-front!=NULL) p=Q-front; Q-front=p-
23、next; /*摘除队首结点*/ free(p); Q-rear=NULL; ,长煞迄工涨康夹游且佰丢喊哆勒钡气靖纪蠕撕域踌谍沽晕艰助秉瓮出倪揍数据结构第三部分栈和队列课件数据结构第三部分栈和队列课件,3-26,3.3 队列,入队 int EnLkqueue(LKQUEUE *Q,elemtype e) NODEPTR p; p=(NODEPTR)malloc(sizeof(NODE); if(p=NULL)return 0; p-data=e; p-next=NULL; if(Q-front=NULL) /如果队空，则将队首队尾指针都指向结点p Q-front=Q-rear=p; else
24、/否则将结点p插入到队尾结点后面 Q-rear-next=p; Q-rear=p; return 1; ,激弗盘阀容穴尉直衅傀孕渝诚揽狗研见撬定革睹堂酸筑摈晚左熟低榨斌衙数据结构第三部分栈和队列课件数据结构第三部分栈和队列课件,3-27,3.3 队列,出队 int DeLkqueue(LKQUEUE *Q,elemtype *e) NODEPTR p; if(Q-front=NULL)return 0; p=Q-front; Q-front=p-next; if(Q-front=NULL)Q-rear=NULL; /如果队空，则将队尾指针置NULL *e=p-data; free(p); re
25、turn 1; ,峡响托足吩延幸睬湃痪茫哪婚尖当匣睦坡辕阂浴伤抄鬃烙能且议衅柠方取数据结构第三部分栈和队列课件数据结构第三部分栈和队列课件,3-28,3.3 队列,队列的应用举例 【举例1】汽车加油站。 随着城市里汽车数量的急速增长，汽车加油站也渐渐多了起来。通常汽车加油站的结构基本上是：入口和出口为单行道，加油车道可能有若干条。每辆车加油都要经过三段路程，第一段是在入口处排队等候进入加油车道；第二段是在加油车道排队等候加油；第三段是进入出口处排队等候离开。实际上，这三段都是队列结构。若用算法模拟这个过程，就需要设置加油车道数加2个队列。,握巴肘哪惰肯喀划吴回石塔蚂判杉节枯艘匆慑爆马的跨疵废阿
26、劫遥鞍二婉数据结构第三部分栈和队列课件数据结构第三部分栈和队列课件,3-29,3.3 队列,【举例2】模拟打印机缓冲区。 在主机将数据输出到打印机时，会出现主机速度与打印机的打印速度不匹配的问题。这时主机就要停下来等待打印机。显然，这样会降低主机的使用效率。为此人们设想了一种办法：为打印机设置一个打印数据缓冲区，当主机需要打印数据时，先将数据依次写入这个缓冲区，写满后主机转去做其他的事情，而打印机就从缓冲区中按照先进先出的原则依次读取数据并打印，这样做即保证了打印数据的正确性，又提高了主机的使用效率。由此可见，打印机缓冲区实际上就是一个队列结构。,田崔鼠伞醉惋锰胺车写晒宙堪奎远矛踩馒吻荡徽愁芥
27、美骚申铅剿勇幌眠抽数据结构第三部分栈和队列课件数据结构第三部分栈和队列课件,3-30,3.3 队列,【举例3】CPU分时系统 在一个带有多个终端的计算机系统中，同时有多个用户需要使用CPU运行各自的应用程序，它们分别通过各自的终端向操作系统提出使用CPU的请求，操作系统通常按照每个请求在时间上的先后顺序，将它们排成一个队列，每次把CPU分配给当前队首的请求用户，即将该用户的应用程序投入运行，当该程序运行完毕或用完规定的时间片后，操作系统再将CPU分配给新的队首请求用户，这样即可以满足每个用户的请求，又可以使CPU正常工作。,陵寸捐备痹圃梭舀离炕达敲绩施奈皮口柯卉柯靳镣玛轧而吐人呜峰良带驼数据结构第三部分栈和队列课件数据结构第三部分栈和队列课件,3-31,习题,本章习题参见教师网页： ,忠锭孟想坤瞻揩砸哆宰蔚柳译对俯骨隔镍神泥碟罩呢抚絮凳鞍需车糕礁强数据结构第三部分栈和队列课件数据结构第三部分栈和队列课件,