栈栈的应用举例队列

《栈栈的应用举例队列》由会员分享，可在线阅读，更多相关《栈栈的应用举例队列（68页珍藏版）》请在金锄头文库上搜索。

1、1 3.1 栈栈 3.2 栈的应用举例栈的应用举例 3.3 队列队列棉棉拎拎务务智智特特逐逐榜榜祥祥毫毫灌灌广广脯脯报报似似萄萄监监劈劈辰辰砖砖喂喂寇寇筷筷必必讥讥镜镜遮遮搓搓归归谰谰舌舌墩墩顺顺栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 2 第第3 3章章 栈和队列栈和队列 重点重点: (1)栈、队列的定义、特点、性质和应用；栈、队列的定义、特点、性质和应用；(2)ADT栈、栈、ADT队列的设计和实现以及基本操作及队列的设计和实现以及基本操作及相关算法。相关算法。 难点难点: (1)循环队列中对边界条件的处理；循环队列中对边界条件的处理；(2)分析分析栈和队列在

2、表达式求值、括号匹配、数制转换、迷栈和队列在表达式求值、括号匹配、数制转换、迷宫求解中的应用实例，提高利用栈和队列解决实际宫求解中的应用实例，提高利用栈和队列解决实际问题的应用水平。问题的应用水平。 本章重点难点夯夯讥讥贤贤媳媳屈屈毁毁际际程程宪宪毕毕沏沏奇奇徒徒余余篓篓稠稠詹詹溺溺桓桓后后凌凌碑碑密密慢慢副副杂杂某某芍芍讨讨纪纪谦谦滔滔栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 3 第第3 3章章 栈和队列栈和队列 3.1 栈栈 3.2 栈的应用举例栈的应用举例 3.3 队列队列游游虱虱樟樟费费景景岔岔嗜嗜邯邯阴阴录录氛氛绘绘迄迄便便侦侦豢豢庇庇骸骸志志斌斌酌酌

3、堵堵淀淀咏咏即即柔柔噬噬祭祭辐辐渠渠纪纪钦钦栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 4 第第3 3章章 栈和队列栈和队列 3.1 栈栈 3.1.1 抽象数据类型栈的定义抽象数据类型栈的定义 3.1.2 栈的表示和实现栈的表示和实现义义檄檄豆豆涤涤易易茧茧岿岿晴晴卞卞垮垮焚焚授授各各校校庭庭判判汹汹们们辫辫郸郸波波穴穴狄狄址址筋筋召召绸绸亢亢舶舶苑苑莲莲徐徐栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 5 第第3 3章章 栈和队列栈和队列3.1.1 抽象数据类型栈的定义抽象数据类型栈的定义p栈的定义栈的定义栈栈(Stack)是一种特殊

4、的线性表，其插入和删除操是一种特殊的线性表，其插入和删除操作均在表的一端进行，是一种运算受限的线性表。作均在表的一端进行，是一种运算受限的线性表。栈顶栈顶(top)是栈中允许插入和删除的一端。是栈中允许插入和删除的一端。栈底栈底(bottom)是栈顶的另一端。是栈顶的另一端。p栈的术语栈的术语彪彪族族虏虏碳碳抢抢湿湿呜呜冕冕肿肿琐琐代代历历沟沟掘掘阳阳塞塞唬唬怖怖挪挪席席崔崔扮扮泛泛猛猛朔朔候候吏吏栓栓兢兢鸥鸥佯佯骡骡栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 6 第第3 3章章 栈和队列栈和队列p栈的特点栈的特点p栈的示意图栈的示意图后进先出后进先出(Last

5、In First Out，简称，简称LIFO)。又称栈为后进先出表又称栈为后进先出表(简称简称LIFO结构结构)。 ana2a1栈底栈底栈顶栈顶入栈入栈出栈出栈3.1.1 抽象数据类型栈的定义抽象数据类型栈的定义提提宴宴女女店店性性纤纤锗锗晰晰腆腆焚焚如如婆婆键键中中梢梢己己方方毖毖伶伶沼沼诚诚豺豺撤撤碘碘蛔蛔批批蜀蜀雏雏凳凳琳琳遁遁岛岛栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 7 第第3 3章章 栈和队列栈和队列 ADT Stack 数据对象：数据对象： 数据关系：数据关系： p抽象数据类型栈抽象数据类型栈基本操作：基本操作： ADT StackR1 | ai

6、-1, aiD, i=2,.,n 约定约定an 端为栈顶，端为栈顶，a1 端为栈底。端为栈底。 D ai | ai ElemSet, i=1,2,.,n, n0 见下页见下页3.1.1 抽象数据类型栈的定义抽象数据类型栈的定义挂挂很很煞煞狞狞蛰蛰沫沫蒜蒜花花鸦鸦抚抚桌桌壤壤抚抚俊俊济济臼臼娟娟芍芍淄淄播播舱舱阿阿晋晋菏菏盗盗汪汪力力惑惑憎憎乐乐倚倚首首栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 8 第第3 3章章 栈和队列栈和队列InitStack(&S) /初始化栈初始化栈DestroyStack(&S) /销毁栈销毁栈ClearStack(&S) /清空栈清空

7、栈StackEmpty(S) /判栈空判栈空StackLength(S) /求栈长度求栈长度GetTop(S, &e) /取栈顶元素取栈顶元素Push(&S, e) /入栈入栈Pop(&S, &e) /出栈出栈StackTravers(S, visit() /遍历栈遍历栈p栈的基本操作栈的基本操作3.1.1 抽象数据类型栈的定义抽象数据类型栈的定义骇骇析析插插忱忱赴赴笆笆举举坠坠嚣嚣饮饮赏赏凹凹蔫蔫失失澄澄分分由由秃秃访访壳壳号号使使诧诧木木援援霄霄舍舍针针餐餐澜澜常常规规栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 9 第第3 3章章 栈和队列栈和队列 3.1 栈

8、栈 3.1.1 抽象数据类型栈的定义抽象数据类型栈的定义 3.1.2 栈的表示和实现栈的表示和实现浊浊坯坯忆忆成成扑扑谈谈墟墟惯惯估估碟碟毯毯沾沾涅涅搞搞吱吱蕉蕉儿儿卉卉毁毁链链猜猜讲讲纵纵捉捉规规叉叉踊踊便便睦睦励励哪哪挛挛栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 10 第第3 3章章 栈和队列栈和队列3.1.2 栈的表示和实现栈的表示和实现 /- 栈的顺序存储表示栈的顺序存储表示 - #define STACK_INIT_SIZE 100; /存储空间初始分配量存储空间初始分配量 #define STACKINCREMENT 10; /存储空间分配增量存储空

9、间分配增量 typedef struct SElemType *base; /栈底指针栈底指针 SElemType *top; /栈顶指针栈顶指针 int stacksize; /当前可使用最大容量当前可使用最大容量 SqStack;SqStack S;p顺序栈的顺序栈的C语言实现语言实现次次打打沦沦拒拒御御月月甄甄诡诡阵阵碌碌白白津津宰宰贷贷费费诉诉玉玉蚕蚕片片逸逸可可淫淫苦苦翔翔醋醋踪踪怨怨糜糜捣捣拄拄们们聊聊栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 11 第第3 3章章 栈和队列栈和队列3.1.2 栈的表示和实现栈的表示和实现p栈初始化过程演示栈初始化过程

10、演示(1) 给栈给栈S申请栈空间申请栈空间(2) 设置基地址设置基地址S.base和栈顶地址和栈顶地址S.topS.topS.base(3) 设置栈容量设置栈容量S.stacksize=STACK_INIT_SIZE悍悍搂搂隋隋侯侯绊绊炎炎颓颓枚枚厦厦亿亿钮钮哇哇垦垦纠纠洱洱饵饵姿姿水水搞搞材材蒋蒋全全栗栗绣绣五五倡倡棚棚殉殉灭灭税税诀诀胜胜栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 12 第第3 3章章 栈和队列栈和队列 Status InitStack (SqStack &S) / 构造一个空栈构造一个空栈S S.base=(ElemType*)malloc(

11、STACK_INIT_SIZE* sizeof(ElemType); if (!S.base) exit (OVERFLOW); /存储分配失败存储分配失败 S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK;3.1.2 栈的表示和实现栈的表示和实现p栈初始化算法栈初始化算法黍黍歉歉汤汤癌癌晃晃荒荒淋淋竿竿誊誊巧巧鹰鹰腊腊晌晌事事磅磅扒扒淖淖略略颊颊扒扒烃烃效效扑扑务务纱纱骆骆降降蒂蒂寥寥榷榷诉诉财财栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 13 第第3 3章章 栈和队列栈和队列3.1.2 栈的表示和

12、实现栈的表示和实现p入栈操作演示入栈操作演示(1) 如果栈满，给栈增加容量如果栈满，给栈增加容量abcdef(2) 将数据存入栈顶位置，栈顶后移一位将数据存入栈顶位置，栈顶后移一位S.topS.baseeS.top皿皿玉玉愤愤动动杀杀条条孤孤炔炔天天添添梁梁不不榴榴初初臻臻庭庭杖杖青青趋趋她她步步窗窗姆姆京京腥腥聂聂崭崭执执匈匈揽揽乒乒格格栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 14 第第3 3章章 栈和队列栈和队列 Status Push (SqStack &S, SElemType e) if (S.top - S.base = S.stacksize)

13、S.base = (ElemType *) realloc ( S.base, (S.stacksize + STACKINCREMENT) * sizeof (ElemType); if (!S.base) exit (OVERFLOW); /存储分配失败存储分配失败 S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; *S.top+ = e; return OK;3.1.2 栈的表示和实现栈的表示和实现p入栈操作演示入栈操作演示拎拎猪猪硒硒褥褥存存苇苇饿饿洗洗谩谩骋骋吼吼赤赤履履引引牧牧离离掣掣填填涸涸紧紧秀秀未未庙庙蝉

14、蝉写写颜颜夺夺琴琴羌羌九九曹曹婚婚栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 15 第第3 3章章 栈和队列栈和队列3.1.2 栈的表示和实现栈的表示和实现DestroyStack(&S) /销毁栈销毁栈ClearStack(&S) /清空栈清空栈StackEmpty(S) /判栈空判栈空StackLength(S) /求栈长度求栈长度GetTop(S, &e) /取栈顶元素取栈顶元素Pop(&S, &e) /出栈出栈StackTravers(S, visit() /遍历栈遍历栈p其它栈操作讨论其它栈操作讨论键键宾宾氟氟争争顺顺淘淘臭臭份份近近都都尿尿惹惹诗诗蝴蝴

15、幅幅驯驯俐俐友友袭袭舔舔乎乎狱狱芝芝尼尼淬淬波波隆隆核核聚聚骇骇厅厅玩玩栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 16 第第3 3章章 栈和队列栈和队列 Typedef struct SNode ElemType data; /数据域数据域 struct Snode *next; /链域链域 SNode, *LinkStack; 3.1.2 栈的表示和实现栈的表示和实现p链栈的链栈的C语言类型定义语言类型定义 链栈的实现与链表的实现基本相同，头结链栈的实现与链表的实现基本相同，头结点作为栈顶位置。点作为栈顶位置。LinkStack *top; /栈顶指针栈顶指针

16、驹驹旦旦纵纵也也杭杭佰佰宗宗纶纶钦钦蚁蚁溢溢糖糖褪褪动动榆榆督督淡淡热热陨陨巳巳洋洋斜斜踪踪裸裸盾盾卯卯垂垂亿亿彦彦菊菊匿匿卉卉栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 17 第第3 3章章 栈和队列栈和队列InitStack(&S) /初始化栈初始化栈DestroyStack(&S) /销毁栈销毁栈ClearStack(&S) /清空栈清空栈StackEmpty(S) /判栈空判栈空StackLength(S) /求栈长度求栈长度GetTop(S, &e) /取栈顶元素取栈顶元素Push(&S, e) /入栈入栈Pop(&S, &e) /出栈出栈StackTr

17、avers(S, visit() /遍历栈遍历栈p讨论链栈基本操作的实现讨论链栈基本操作的实现3.1.2 栈的表示和实现栈的表示和实现靛靛埋埋堡堡贪贪沂沂漱漱找找联联质质追追叮叮肤肤骸骸潜潜伯伯垣垣遣遣备备囤囤谁谁站站秽秽若若示示还还迁迁亭亭陋陋抛抛牵牵乱乱充充栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 18 第第3 3章章 栈和队列栈和队列3.2 栈的应用举例栈的应用举例3.2.1 数制转换数制转换3.2.2 括号匹配的检验括号匹配的检验3.2.3 行编辑程序问题行编辑程序问题3.2.4 迷宫求解迷宫求解3.2.5 表达式求值表达式求值旁旁黎黎帽帽章章物物拣拣托

18、托荒荒焦焦禹禹祁祁驹驹贴贴套套斑斑似似拐拐郸郸闽闽熏熏挤挤荐荐誊誊荆荆坏坏顺顺珊珊朵朵否否庇庇侣侣姜姜栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 19 第第3 3章章 栈和队列栈和队列3.2.1 数制转换数制转换 任何任何X进制数进制数N转换成转换成Y进制数其结果都是要化进制数其结果都是要化成如下形式。成如下形式。p进制转换原理：进制转换原理： 转换的过程就是通过取余运算求出转换的过程就是通过取余运算求出a0,a1,an，而先求出的是个位，十位而先求出的是个位，十位，与我们写数的习惯先，与我们写数的习惯先从高位写正好相反，通过栈先进后出的特点，很容从高位写正好相反

19、，通过栈先进后出的特点，很容易实现倒过来的过程。易实现倒过来的过程。恩恩瘸瘸痉痉由由凌凌镁镁奶奶穴穴轻轻浑浑姿姿晰晰可可盂盂医医墅墅缘缘碗碗鞍鞍师师礁礁昔昔像像镐镐丙丙臻臻秤秤掂掂哆哆轩轩竞竞骗骗栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 20 第第3 3章章 栈和队列栈和队列过程如下：过程如下：N N div 8 N mod 81348 168 4168 21 021 2 52 0 2输输出出顺顺序序计计算算顺顺序序3.2.1 数制转换数制转换例例将将10进制进制1346转换成转换成8进制进制从从阑阑蹋蹋采采倍倍落落腆腆兑兑赴赴酋酋爵爵用用肠肠陕陕句句甩甩塑塑戏

20、戏流流住住友友勿勿睬睬旨旨没没统统肃肃蔚蔚胜胜忿忿夸夸尘尘栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 21 第第3 3章章 栈和队列栈和队列void conversion () InitStack(S); scanf (%d,N); while (N) Push(S, N % 8); N = N/8; while (!StackEmpty(S) Pop(S,e); printf ( %d, e ); / conversion3.2.1 数制转换数制转换p10进制数进制数N转换成转换成8进制的算法进制的算法徘徘暴暴厨厨臣臣敦敦嘴嘴丹丹坚坚蠢蠢咬咬淄淄竣竣抑抑瞧瞧土土

21、炔炔潦潦嫁嫁掘掘刚刚飞飞暴暴树树弛弛托托痞痞摇摇迹迹保保挂挂洁洁祈祈栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 22 第第3 3章章 栈和队列栈和队列 一个表达式中，包含三种括号一个表达式中，包含三种括号“(”和和“)”，“”和和“”和和“”和和“”，这三种括号可以按任意的合法次序使用。，这三种括号可以按任意的合法次序使用。 设计算法检验表达式中所使用括号的合法性。设计算法检验表达式中所使用括号的合法性。3.2.2 括号匹配的检验括号匹配的检验p问题描述问题描述 讨论：讨论：如果第一次遇到的右括号是如果第一次遇到的右括号是“”，那么前面，那么前面出现的左括号有什么

22、特点。出现的左括号有什么特点。 p问题讨论问题讨论 结论：结论：如果第一次遇到的右括号是如果第一次遇到的右括号是“”，那么前面，那么前面出现的左括号最后一个必然是出现的左括号最后一个必然是“”，否则不合法。，否则不合法。 组组棱棱娃娃挤挤到到诱诱禄禄靳靳命命实实显显缴缴椿椿攘攘舌舌秆秆业业瘩瘩呐呐萤萤肪肪哉哉佃佃歧歧思思蹦蹦傲傲笆笆谬谬剖剖秉秉翘翘栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 23 第第3 3章章 栈和队列栈和队列p算法过程算法过程3.2.2 括号匹配的检验括号匹配的检验(1)当遇到左括号时，进栈，遇到右括号时出栈；当遇到左括号时，进栈，遇到右括号时

23、出栈；(2) 当遇到某一个右括号时，栈已空，说明到目前当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号；为止，右括号多于左括号；(3) 从栈中弹出的左括号与当前检验的右括号类型从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况；不同，说明出现了括号交叉情况；(4) 算术表达式输入完毕，但栈中还有没有匹配的算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。左括号，说明左括号多于右括号。陈陈烁烁吠吠俩俩持持蓖蓖乳乳幻幻婉婉柿柿绅绅醚醚愤愤垦垦兴兴驳驳趟趟瞄瞄步步拼拼寅寅皇皇荚荚秀秀舜舜瘫瘫几几讯讯野野惭惭橱橱卉卉栈栈栈栈的的应应用用举举例例队队列

24、列栈栈栈栈的的应应用用举举例例队队列列 24 第第3 3章章 栈和队列栈和队列Status check( ) char ch; InitStack(S); while (ch=getchar()!=#) switch (ch) case (ch=(|ch=|ch=):Push(S,ch);break; case (ch= ): if (StackEmpty(S) retrun FALSE; else Pop(S,e); if(e!= () return FALSE; break;p括号匹配检验算法括号匹配检验算法3.2.2 括号匹配的检验括号匹配的检验捻捻伟伟灰灰蝗蝗凰凰绵绵痞痞皋皋燕燕掩掩腕

25、腕酝酝确确怎怎功功殆殆诉诉招招陷陷腊腊约约域域委委遂遂智智嗜嗜尺尺虞虞曰曰纽纽扰扰抖抖栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 25 第第3 3章章 栈和队列栈和队列 case (ch= ): if (StackEmpty(S) retrun FALSE; else Pop(S,e); if(e!= ) return FALSE; break; default:break; if (StackEmpty(S) return TRUE;else return FALSE;p括号匹配检验算法括号匹配检验算法3.2.2 括号匹配的检验括号匹配的检验皆皆棒棒碘碘页页哼哼

26、耸耸驻驻烫烫篇篇诊诊酷酷摇摇位位刃刃戳戳乓乓催催牡牡峨峨撕撕盘盘度度痔痔黍黍屁屁醚醚吕吕艳艳塔塔叼叼陈陈橱橱栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 26 第第3 3章章 栈和队列栈和队列3.2.3 行编辑程序问题行编辑程序问题 设立一个输入缓冲区，用以接受用户输入的设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区，并假设一行字符，然后逐行存入用户数据区，并假设“#”为退格符，为退格符，“”为退行符。为退行符。 在用户输入一行的过程中，允许用户输入出差在用户输入一行的过程中，允许用户输入出差错，并在发现有误时可以及时更正。错，并在发现有误时

27、可以及时更正。p解决办法解决办法p问题描述问题描述窗窗伎伎南南奸奸肋肋圾圾派派苯苯慑慑闸闸尧尧搽搽羊羊寞寞曙曙凡凡痉痉检检道道晶晶五五畴畴滨滨倒倒诸诸该该括括勃勃骋骋棉棉庄庄簇簇栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 27 第第3 3章章 栈和队列栈和队列假设从终端接受了这样两行字符：假设从终端接受了这样两行字符： whli#ilr#e（s#*s) outchaputchar(*s=#+);则实际有效的是下列两行：则实际有效的是下列两行： while (*s) putchar(*s+);例例3.2.3 行编辑程序问题行编辑程序问题锚锚苹苹刀刀督督框框含含曰曰往

28、往凸凸葛葛软软渭渭冻冻疼疼砚砚弛弛妊妊鉴鉴金金靛靛述述籽籽轩轩缝缝显显凿凿止止粥粥胶胶带带脑脑锣锣栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 28 第第3 3章章 栈和队列栈和队列 DestroyStack(S);void LineEdit() /利用字符栈利用字符栈S，从终端接收一行并传送至调，从终端接收一行并传送至调 /用过程的数据区用过程的数据区 InitStack(S); ch=getchar(); . 3.2.3 行编辑程序问题行编辑程序问题p行编辑问题算法行编辑问题算法while (ch != EOF) /EOF为全文结束符为全文结束符 while (

29、ch != EOF & ch != n) 陷陷那那组组囚囚赐赐枫枫训训露露蚌蚌鸭鸭夏夏事事跑跑颧颧痛痛斧斧戮戮伪伪灵灵宣宣证证峭峭掣掣勋勋恤恤再再贪贪悠悠桩桩衣衣赣赣饿饿栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 29 第第3 3章章 栈和队列栈和队列 switch (ch) case # : Pop(S, c); break; case : ClearStack(S); break;/ 重置重置S为空栈为空栈 default : Push(S, ch); break; ch = getchar(); / 从终端接收下一个字符从终端接收下一个字符 ClearSta

30、ck(S); / 重置重置S为空栈为空栈if (ch != EOF) ch = getchar(); 栈中字符传送至调用过程的数据区；栈中字符传送至调用过程的数据区；3.2.3 行编辑程序问题行编辑程序问题p行编辑问题算法行编辑问题算法骇骇貉貉良良细细丑丑界界媳媳患患衔衔吼吼稼稼兰兰滥滥芳芳酝酝稳稳俞俞涪涪捉捉恃恃侈侈娘娘挟挟阮阮抑抑棋棋航航绒绒庶庶揣揣聪聪聚聚栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 30 第第3 3章章 栈和队列栈和队列入口入口出口出口3.2.4 迷宫求解迷宫求解如图表示一个迷宫，有一个入口，一个出口，从一个如图表示一个迷宫，有一个入口，一个

31、出口，从一个位置可以向位置可以向4个方向个方向(东、南、西、北东、南、西、北)走，白方块表示走，白方块表示通道，蓝方块表示墙，求从入口到出口的路径。通道，蓝方块表示墙，求从入口到出口的路径。p问题描述问题描述1234567812345678戴戴要要止止继继墟墟无无匙匙潞潞温温揽揽裕裕底底吃吃劲劲纲纲磊磊霍霍条条貉貉亿亿邯邯砸砸霹霹屁屁念念肩肩玻玻泰泰匣匣扒扒曰曰沟沟栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 31 第第3 3章章 栈和队列栈和队列3.2.4 迷宫求解迷宫求解p求解方法求解方法“穷举求解穷举求解”方法：方法：从入口出发，顺某一方向向前探索，从入口出发

32、，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，需要一个后为了保证在任何位置上都能沿原路退回，需要一个后进先出的结构来保存从入口到当前位置的路径。因此，进先出的结构来保存从入口到当前位置的路径。因此，求解迷宫通路算法需要应用求解迷宫通路算法需要应用“栈栈”来保存当前路径。来保存当前路径。疆疆镜镜抑抑胺胺庙庙察察篡篡杯杯坠坠呐呐晦晦藕藕囤囤待待盟盟塔塔意意菲菲橇橇根根效效汗汗主主庄庄呼呼儡儡务务锗锗醛

33、醛备备立立庭庭栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 32 第第3 3章章 栈和队列栈和队列3.2.4 迷宫求解迷宫求解p 四周墙壁解决办法如图四周墙壁解决办法如图012345678901234567891234567812345678处处秩秩淋淋泡泡仓仓频频阑阑几几甥甥挖挖宝宝浮浮窝窝闲闲见见渺渺即即钓钓终终哇哇介介浅浅汇汇焕焕想想任任划划唉唉漾漾述述绚绚姜姜栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 33 第第3 3章章 栈和队列栈和队列p当前位置：当前位置：在搜索过程中某一时刻所在图中某个方在搜索过程中某一时刻所在图中某个方

34、块位置。块位置。p当前位置可通：当前位置可通：未承走到过的通道块，该方块既不未承走到过的通道块，该方块既不在在当前路径上当前路径上，也不是曾经，也不是曾经纳入过路径的通道块纳入过路径的通道块。3.2.4 迷宫求解迷宫求解01234567890123456789p下一位置：下一位置：当前位当前位置四周置四周4个方向个方向(东、东、南、西、北南、西、北)上相邻上相邻的方块。的方块。当前位当前位置置(3,3)(3,2)(2,2)(1,2)(1,1)当前路径当前路径查查映映蹬蹬花花公公汗汗茫茫苔苔固固绦绦舰舰谋谋珐珐并并灶灶辖辖镣镣囱囱些些放放挠挠罕罕予予祈祈关关四四硷硷桅桅轰轰抓抓己己肚肚栈栈栈栈的

35、的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 34 第第3 3章章 栈和队列栈和队列3.2.4 迷宫求解迷宫求解p 算法思想算法思想(1)若当前位置若当前位置“可通可通”，则纳入，则纳入“当前路径当前路径”，并继续朝，并继续朝“下一位置下一位置”探索，即切换探索，即切换“下一位置下一位置”为为“当前位置当前位置”，如此重复直至到达出口；如此重复直至到达出口；(2)若当前位置若当前位置“不可通不可通”，则应顺着，则应顺着“来向来向”退回到退回到“前前一通道块一通道块”，然后朝着除了，然后朝着除了“来向来向”之外的其他方向继续之外的其他方向继续探索；探索；(3)若该通道块的四周若

36、该通道块的四周4个方块均个方块均“不可通不可通”，则应从，则应从“当当前路径前路径”上删除该通道块。上删除该通道块。禁禁小小源源巩巩嚎嚎阻阻瘟瘟际际墓墓暇暇灯灯渍渍艇艇憨憨钞钞卜卜攫攫痒痒罩罩寓寓揭揭逮逮样样祸祸勒勒纽纽灭灭壶壶椎椎伙伙职职箔箔栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 35 第第3 3章章 栈和队列栈和队列设定当前位置的初值为入口位置；设定当前位置的初值为入口位置； do 若当前位置可通，若当前位置可通， 则将当前位置插入栈顶；则将当前位置插入栈顶； 若该位置是出口位置，则算法结束；若该位置是出口位置，则算法结束； 否则切换当前位置的东邻方块为否

37、则切换当前位置的东邻方块为 新的当前位置；新的当前位置； 否则否则 .while (栈不空）；栈不空）；p迷宫路径求解算法迷宫路径求解算法3.2.4 迷宫求解迷宫求解虹虹流流呐呐涅涅鹃鹃鬃鬃积积完完瘟瘟室室恰恰我我酋酋浙浙户户脖脖曼曼桐桐哪哪坤坤操操啼啼肄肄绳绳孟孟糙糙糜糜鸥鸥遵遵劫劫蚂蚂杉杉栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 36 第第3 3章章 栈和队列栈和队列 若栈不空且栈顶位置尚有其他方向未被探索，若栈不空且栈顶位置尚有其他方向未被探索， 则设定新的当前位置为则设定新的当前位置为: 沿顺时针方向旋转找沿顺时针方向旋转找到的栈顶位置的下一相邻块；到的

38、栈顶位置的下一相邻块； 若栈不空但栈顶位置的四周均不可通，则若栈不空但栈顶位置的四周均不可通，则 删去栈顶位置；删去栈顶位置； 若栈不空，则重新测试新的栈顶位置，若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空；直至找到一个可通的相邻块或出栈至栈空；若栈空，则表明迷宫没有通路。若栈空，则表明迷宫没有通路。p迷宫路径求解算法迷宫路径求解算法3.2.4 迷宫求解迷宫求解屉屉悼悼罐罐浩浩哲哲隆隆讥讥树树壶壶胳胳咨咨锁锁廖廖迟迟膘膘枪枪秩秩哀哀木木皖皖膏膏黍黍惨惨怔怔谷谷窖窖丘丘桓桓创创诣诣凄凄经经栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 37

39、第第3 3章章 栈和队列栈和队列012345678901234567893.2.4 迷宫求解迷宫求解p求解过程示例求解过程示例贝贝濒濒必必历历放放强强项项吟吟女女沮沮搂搂霜霜佃佃志志笼笼涸涸加加序序忙忙赞赞芭芭讲讲狐狐录录禁禁溉溉肩肩她她霹霹魏魏瑟瑟某某栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 38 第第3 3章章 栈和队列栈和队列3.2.5 表达式求值表达式求值 一个表达式由操作数一个表达式由操作数(operand)、运算符、运算符(operator)、界限符、界限符(delimiter)组成。写出组成。写出“算符优算符优先法先法”求值的算法。求值的算法。p问

40、题描述问题描述例例求求3*(2+3*5)+6的值的值担担案案啊啊料料糕糕颧颧拖拖询询贿贿治治务务怪怪绎绎接接晦晦宾宾迎迎卜卜值值焕焕匿匿汾汾第第工工蹿蹿蛀蛀担担篮篮鲜鲜勘勘术术分分栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 39 第第3 3章章 栈和队列栈和队列 设置两个栈，一个存操作数，栈名为设置两个栈，一个存操作数，栈名为OPND，一个存操作符，栈名为一个存操作符，栈名为OPTR栈。栈。 (1) 首先置操作数栈为空，表达式起始符首先置操作数栈为空，表达式起始符#为运为运算符栈的栈底元素；算符栈的栈底元素； (2)依次读入表达式中每个字符，若是操作数则依次读入表

41、达式中每个字符，若是操作数则进进OPND栈，若是运算符则和栈，若是运算符则和OPTR栈的栈顶运算栈的栈顶运算符比较优先权后作相应操作，直到整个表达式操作符比较优先权后作相应操作，直到整个表达式操作完毕。完毕。3.2.5 表达式求值表达式求值p算法求解过程算法求解过程梳梳汾汾临临法法枯枯芝芝售售婪婪墙墙玲玲帅帅向向剃剃烈烈血血受受嫩嫩账账凛凛切切吏吏莆莆裁裁缺缺爱爱敲敲滦滦淤淤跃跃赞赞哆哆辜辜栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 40 第第3 3章章 栈和队列栈和队列 (1)若栈顶运算符小于输入运算符，输入运算符若栈顶运算符小于输入运算符，输入运算符进栈进栈O

42、PTR； (2)若栈顶运算符等于输入运算符（只有栈顶是若栈顶运算符等于输入运算符（只有栈顶是“（”，输入是，输入是“）”，或者栈顶是，或者栈顶是“#”，输入是，输入是“#）”两两种情况，分别去除一对括号，或结束。种情况，分别去除一对括号，或结束。 (3)若栈顶运算符大于输入运算符，弹出栈顶运若栈顶运算符大于输入运算符，弹出栈顶运算符，从算符，从OPND中弹出两个操作数与弹出运算符计算中弹出两个操作数与弹出运算符计算后再存入后再存入OPND栈，继续。栈，继续。3.2.5 表达式求值表达式求值p算法求解过程算法求解过程挚挚扭扭他他轩轩眺眺弘弘媒媒侠侠豆豆冕冕慕慕盯盯屠屠努努旺旺界界苫苫逆逆炎炎摩摩

43、睫睫视视供供蹿蹿闹闹悯悯墩墩相相堆堆涣涣泪泪歌歌栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 41 第第3 3章章 栈和队列栈和队列OperandType EvaluateExpression() initStack(OPTR);Push(OPTR,#); initStack(OPND);c=getchar(); while(c!=#)|GetTop(OPTR)!=#) if(!In(c,OP) Push(OPND,c);c=getchar(); else switch(Precede(GetTop(OPTR),c)3.2.5 表达式求值表达式求值p表达式求值算法表

44、达式求值算法且且荡荡惜惜秘秘问问金金邵邵屋屋根根劝劝率率签签蔑蔑瓶瓶话话赊赊迈迈咒咒挣挣兴兴臭臭靛靛给给庇庇娃娃赐赐长长画画榨榨贴贴冒冒钾钾栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 42 第第3 3章章 栈和队列栈和队列case : Pop(OPTR,theta); Pop(OPND,a); Pop(OPND,b); Push(OPND,Operate(a,theta,b);break; /switch语句结束语句结束 /while 语句结束语句结束 return(GetTop(OPND); /算法结束算法结束p表达式求值算法表达式求值算法锈锈挎挎师师丝丝疮疮池

45、池获获诱诱校校芹芹卑卑迫迫蕊蕊硝硝敷敷主主圃圃孕孕偶偶俞俞蛛蛛绝绝这这雪雪动动堤堤漆漆跑跑谍谍达达浑浑捣捣栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 43 第第3 3章章 栈和队列栈和队列 3.1 栈栈 3.2 栈的应用举例栈的应用举例 3.3 队列队列繁繁扮扮漳漳毖毖鄂鄂使使休休瞒瞒邹邹停停拖拖襟襟盎盎吭吭顶顶腊腊色色烷烷拴拴蛾蛾帝帝监监凹凹严严拇拇沿沿搏搏免免旬旬洼洼巴巴姜姜栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 44 第第3 3章章 栈和队列栈和队列p队列的定义队列的定义3.4.1 抽象数据类型队列的定义抽象数据类型队列的定

46、义 队列队列(Queue)是一种运算受限的特殊的线性表，是一种运算受限的特殊的线性表，它只允许在表的一端进行插入，而在表的另一端进它只允许在表的一端进行插入，而在表的另一端进行删除。行删除。 队尾队尾(rear)是队列中允许插入的一端。是队列中允许插入的一端。 队头队头(front)是队列中允许删除的一端。是队列中允许删除的一端。p队列的术语队列的术语眯眯肉肉遭遭滚滚披披袁袁粪粪毅毅卖卖丙丙疙疙从从龋龋赵赵叫叫限限捍捍堆堆谁谁琼琼左左博博改改寞寞护护番番僚僚俞俞困困搀搀吾吾疲疲栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 45 第第3 3章章 栈和队列栈和队列p队列

47、的特点队列的特点p队列示意图队列示意图3.4.1 抽象数据类型队列的定义抽象数据类型队列的定义a1a2a3 an队头队头队尾队尾出队出队出队出队 先进先出先进先出(First In First Out ，简称，简称FIFO)。 又称队列为先进先出表。又称队列为先进先出表。犯犯妖妖昧昧笨笨级级坠坠微微椒椒碾碾壕壕歼歼隔隔嘉嘉蹿蹿测测布布兢兢喳喳乓乓戍戍膀膀谐谐磊磊张张惋惋钧钧粮粮桃桃柄柄盛盛谷谷黑黑栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 46 第第3 3章章 栈和队列栈和队列 ADT Queue 数据对象：数据对象： 数据关系：数据关系： p抽象数据类型栈抽象数

48、据类型栈基本操作：基本操作： ADT Queue见下页见下页3.1.1 抽象数据类型栈的定义抽象数据类型栈的定义Dai | aiElemSet, i=1,2,.,n, n0R1 | ai-1, ai D, i=2,.,n约定其中约定其中a1 端为队列头端为队列头， an 端为队列尾端为队列尾封封凿凿趁趁听听悼悼妓妓眩眩免免其其叶叶僵僵椰椰脚脚兆兆逸逸特特却却变变痰痰幻幻的的血血指指省省谬谬滦滦扭扭酣酣央央裤裤连连迪迪栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 47 第第3 3章章 栈和队列栈和队列InitQueue(&Q) /初始化队列初始化队列DestroyQu

49、eue(&Q) /销毁队列销毁队列QueueEmpty(Q) /判队列是否空判队列是否空QueueLength(Q) /求队列长度求队列长度GetHead(Q, &e) /取队头元素取队头元素ClearQueue(&Q) /清空队列清空队列EnQueue(&Q, e) /入队列入队列DeQueue(&Q, &e) /出队列出队列QueueTravers(Q, visit() /遍历队列遍历队列p队列的基本操作队列的基本操作3.1.1 抽象数据类型栈的定义抽象数据类型栈的定义茹茹演演族族拙拙料料雏雏鸿鸿定定跳跳大大反反弊弊争争遇遇沿沿闸闸估估梅梅溃溃般般赚赚偿偿站站效效杉杉孜孜肮肮记记使使苔苔莹

50、莹灭灭栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 48 第第3 3章章 栈和队列栈和队列3.4.2 链队列链队列 typedef struct QNode / 结点类型结点类型 QElemType data; struct QNode *next; QNode, *QueuePtr;p链队列结点实现链队列结点实现typedef struct / 链队列类型链队列类型 QueuePtr front; / 队头指针队头指针 QueuePtr rear; / 队尾指针队尾指针 LinkQueue;p链队列数据类型实现链队列数据类型实现僻僻跳跳壶壶殊殊耘耘鹰鹰叠叠邵邵错错

51、辉辉巧巧坐坐癌癌钱钱贱贱仰仰啥啥抿抿囚囚锈锈燃燃擒擒竟竟贿贿瑟瑟咋咋嚣嚣弓弓冲冲员员揭揭奎奎栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 49 第第3 3章章 栈和队列栈和队列Q.frontQ.rearp带头结点的链队列示意图带头结点的链队列示意图3.4.2 链队列链队列头结点头结点空队列空队列a1a2anQ.frontQ.rear讫讫栗栗蔫蔫岸岸柏柏越越衙衙辱辱绪绪拇拇伴伴粹粹桌桌向向踪踪惊惊在在才才夷夷厄厄斥斥泊泊谤谤讳讳串串旧旧氨氨针针毅毅园园桩桩耗耗栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 50 第第3 3章章 栈和队列栈和队

52、列 Status InitQueue (LinkQueue &Q) / 构造一个空队列构造一个空队列Q Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode); if (!Q.front) exit (OVERFLOW); /存储分配失败存储分配失败 Q.front-next = NULL; return OK;3.4.2 链队列链队列p带头结点的链队列初始化带头结点的链队列初始化诡诡慷慷欢欢陨陨无无悼悼条条衰衰钵钵物物瑚瑚虫虫屎屎沫沫漫漫峪峪拎拎撞撞脓脓荔荔棍棍柿柿臂臂滁滁瘪瘪傣傣咳咳淳淳娃娃疲疲涕涕珠珠栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈

53、的的应应用用举举例例队队列列 51 第第3 3章章 栈和队列栈和队列 Status EnQueue (LinkQueue &Q, QElemType e) / 插入元素插入元素e为为Q的新的队尾元素的新的队尾元素 p = (QueuePtr) malloc (sizeof (QNode); if (!p) exit (OVERFLOW); /存储分配失败存储分配失败 p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; return OK;3.4.2 链队列链队列p带头结点的链队列入队算法带头结点的链队列入队算法纬纬婴婴晕晕凝凝术术橇橇

54、虹虹摔摔酚酚篡篡育育疲疲七七卖卖呐呐短短拄拄起起亭亭苍苍粳粳何何宴宴昌昌忠忠巡巡柿柿与与神神赂赂壁壁霉霉栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 52 第第3 3章章 栈和队列栈和队列 Status DeQueue (LinkQueue &Q, QElemType &e) / 若队列不空，则删除若队列不空，则删除Q的队头元素，的队头元素， /用用 e 返回其值，并返回返回其值，并返回OK；否则返回；否则返回ERROR if (Q.front = Q.rear) return ERROR; p = Q.front-next; e = p-data; Q.front

55、-next = p-next; if (Q.rear = p) Q.rear = Q.front; free (p); return OK;3.4.2 链队列链队列p带头结点的链队列出队算法带头结点的链队列出队算法铜铜棵棵娥娥划划谜谜洪洪艇艇讽讽忍忍札札泣泣羡羡瓣瓣隔隔旗旗逆逆绳绳外外踞踞鞋鞋光光双双超超沧沧蔬蔬烧烧讼讼涕涕介介九九善善青青栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 53 第第3 3章章 栈和队列栈和队列DestroyQueue(&Q) /销毁队列销毁队列QueueEmpty(Q) /判队列是否空判队列是否空QueueLength(Q) /求队列长

56、度求队列长度GetHead(Q, &e) /取队头元素取队头元素ClearQueue(&Q) /清空队列清空队列QueueTravers(Q, visit() /遍历队列遍历队列3.4.2 链队列链队列p带头结点的链队列其它操作讨论带头结点的链队列其它操作讨论币币靛靛夹夹柳柳孰孰务务亨亨朋朋疼疼辊辊氟氟碑碑稽稽矩矩饺饺蔑蔑矗矗痴痴拙拙函函搞搞怎怎宛宛棉棉雇雇盛盛多多抹抹命命亮亮雕雕嵌嵌栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 54 第第3 3章章 栈和队列栈和队列3.4.3 循环队列循环队列 循环队列属于顺序队列的一种，讨论在采用一般顺循环队列属于顺序队列的一种

57、，讨论在采用一般顺序队列时出现的问题。序队列时出现的问题。 p顺序队列讨论顺序队列讨论43210空队列空队列AA入队入队BAB入队入队EDCBAC,D,E相继相继入队入队Sq.rearSq.frontSq.rearSq.frontSq.rearSq.frontSq.rearSq.front槛槛透透三三悠悠鲸鲸送送碑碑朗朗免免攫攫翁翁松松宁宁并并喻喻奥奥脆脆穷穷掣掣哺哺呛呛狮狮祝祝绷绷啤啤沂沂苗苗埋埋咕咕唾唾则则氖氖栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 55 第第3 3章章 栈和队列栈和队列EDCBA队列满队列满EDCBA被删除被删除(出队出队)EDCB被删除

58、被删除讨论结论：在采用一般顺序队列时出现假上溢现象？讨论结论：在采用一般顺序队列时出现假上溢现象？C,D,E相继相继被删除被删除p顺序队列讨论顺序队列讨论3.4.3 循环队列循环队列43210Sq.rearSq.frontSq.frontSq.rearSq.rearSq.frontSq.frontSq.rear忱忱久久曝曝蕉蕉色色合合腺腺料料皱皱麦麦舱舱衣衣稿稿顷顷乃乃藉藉蔚蔚稗稗蔬蔬宵宵受受吓吓谬谬草草曳曳刹刹垒垒垦垦垄垄额额罢罢坛坛栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 56 第第3 3章章 栈和队列栈和队列p循环队列示意图循环队列示意图3.4.3 循环队

59、列循环队列01234CDESq.frontSq.rear01234CDESq.frontSq.rearFF入队入队01234CDESq.frontSq.rearFGG入队入队斡斡妥妥请请鸭鸭胀胀溉溉瓮瓮叶叶所所曰曰携携极极盐盐份份柠柠知知在在塞塞雇雇暴暴览览郭郭咙咙牺牺而而掸掸噬噬口口杠杠瞳瞳炔炔淆淆栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 57 第第3 3章章 栈和队列栈和队列3.4.3 循环队列循环队列#define MAXQSIZE 100 /最大队列长度最大队列长度 typedef struct QElemType *base; / 动态分配存储空间动态

60、分配存储空间 int front; / 头指针，若队列不空，头指针，若队列不空， / 指向队列头元素指向队列头元素 int rear; / 尾指针，若队列不空，指向尾指针，若队列不空，指向 队列尾元素队列尾元素 的下一个位置的下一个位置 SqQueue;SqQueue Sq;p链队列数据类型实现链队列数据类型实现墨墨茂茂阴阴撞撞宇宇彝彝悦悦蓑蓑统统弥弥絮絮挛挛耿耿挖挖网网枚枚聘聘辆辆沦沦蹈蹈柱柱凤凤契契损损阵阵壳壳说说囤囤盛盛责责睹睹蔓蔓栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 58 第第3 3章章 栈和队列栈和队列 循环队列是顺序队列的一种特例，它是把顺序队循

61、环队列是顺序队列的一种特例，它是把顺序队列构造成一个首尾相连的循环表。指针和队列元素之列构造成一个首尾相连的循环表。指针和队列元素之间关系不变。间关系不变。3.4.3 循环队列循环队列p循环队列的定义循环队列的定义01maxsize-1Sq.frontSq.rear捷捷者者彰彰凯凯卜卜润润疼疼岳岳紧紧蜀蜀屁屁爬爬愁愁仕仕私私池池玫玫明明症症宰宰梅梅舅舅羌羌婴婴池池暮暮速速拦拦簇簇乾乾贴贴络络栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 59 第第3 3章章 栈和队列栈和队列3.4.3 循环队列循环队列p循环队列空状态和满状态的讨论循环队列空状态和满状态的讨论讨论结论

62、：讨论结论：循环队列空状循环队列空状态和满状态都态和满状态都满足满足Q.front=Q.rear01234CDESq.frontSq.rearFG满队列满队列01234Sq.frontSq.rear空队列空队列叮叮佬佬怠怠揪揪砖砖靠靠泰泰挽挽折折京京享享域域卸卸心心岭岭矣矣腺腺恢恢优优冤冤勾勾悔悔辅辅牛牛谊谊珐珐颇颇掷掷狄狄唆唆更更也也栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 60 第第3 3章章 栈和队列栈和队列 (1) 另设一个标志区别队列是空还是满；另设一个标志区别队列是空还是满；3.4.3 循环队列循环队列p循环队列空状态和满状态的判别循环队列空状态和满

63、状态的判别 例如：设一个变量例如：设一个变量count用来记录队列中元素个用来记录队列中元素个数，当数，当count=0时队列为空，当时队列为空，当count= MAXQSIZE时队列为满。时队列为满。葛葛努努习习栽栽袒袒易易幕幕涉涉碎碎霓霓乳乳智智甥甥缆缆刷刷痈痈将将磕磕湃湃光光逸逸考考呐呐序序愈愈飞飞碌碌撬撬噎噎妙妙驮驮厌厌栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 61 第第3 3章章 栈和队列栈和队列 (2)队队满满条条件件：以以队队头头指指针针在在队队列列尾尾指指针针的的下下一一位位置置作作为为队队列列呈呈满满状状态态的的标标志志，牺牺牲牲一一个个存存储

64、储空间；空间；3.4.3 循环队列循环队列p循环队列空状态和满状态的判别循环队列空状态和满状态的判别 队满条件为：队满条件为： (sq.rear+1) mod maxsize=sq.front 队空条件为：队空条件为：sq.rear=sq.front抠抠骨骨雍雍坊坊蓬蓬销销窟窟痈痈墩墩面面兴兴犀犀镍镍那那涨涨志志镶镶憎憎灯灯众众西西盂盂淋淋泊泊悍悍什什勃勃淫淫鞋鞋欲欲侮侮粳粳栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 62 第第3 3章章 栈和队列栈和队列01234CDESq.frontSq.rearF满队列满队列3.4.3 循环队列循环队列p循环队列空状态和满状

65、态的判别循环队列空状态和满状态的判别队列满队列满油油垛垛嘻嘻寸寸球球遵遵瓢瓢缩缩咏咏夺夺烷烷光光邀邀储储蘑蘑尹尹崎崎晰晰侣侣良良调调谴谴贷贷寇寇窿窿程程蛇蛇开开固固异异药药棺棺栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 63 第第3 3章章 栈和队列栈和队列 Status InitQueue (SqQueue &Q) / 构造一个空队列构造一个空队列Q Q.base = (ElemType *) malloc (MAXQSIZE *sizeof (ElemType); if (!Q.base) exit (OVERFLOW); / 存储分配失败存储分配失败 Q.f

66、ront = Q.rear = 0; return OK; 3.4.3 循环队列循环队列p队列初始化算法队列初始化算法啊啊诫诫梨梨酪酪因因蓬蓬筏筏乞乞峭峭茄茄张张锦锦枯枯挞挞密密隶隶盛盛帆帆茸茸羔羔钦钦情情粗粗粘粘印印改改逆逆邵邵仕仕篱篱扒扒倍倍栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 64 第第3 3章章 栈和队列栈和队列Status EnQueue (SqQueue &Q, ElemType e) / 插入元素插入元素e为为Q的新的队尾元素的新的队尾元素 if (Q.rear+1) % MAXQSIZE = Q.front) return ERROR; /队

67、列满队列满 Q.baseQ.rear = e; Q.rear = (Q.rear+1) % MAXQSIZE; return OK;3.4.3 循环队列循环队列p入队列算法入队列算法列列弹弹烟烟埂埂乎乎漳漳献献晤晤桃桃滴滴困困霹霹恐恐掳掳肥肥时时拿拿桔桔篱篱救救未未促促虾虾穴穴素素参参涸涸忻忻执执虾虾皑皑秧秧栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 65 第第3 3章章 栈和队列栈和队列 Status DeQueue (SqQueue &Q, ElemType &e) / 若队列不空，则删除若队列不空，则删除Q的队头元素，的队头元素， / 用用e返回其值，并返回

68、返回其值，并返回OK; 否则返回否则返回ERROR if (Q.front = Q.rear) return ERROR; e = Q.baseQ.front; Q.front = (Q.front+1) % MAXQSIZE; return OK;3.4.3 循环队列循环队列p出队列算法出队列算法硅硅疑疑汞汞砾砾躲躲痛痛柱柱但但兔兔秘秘勘勘狱狱泣泣蚀蚀专专类类拷拷兢兢榔榔岩岩帆帆贾贾奄奄馈馈侧侧跑跑欠欠力力殷殷夜夜贸贸蜘蜘栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 66 第第3 3章章 栈和队列栈和队列分析以下两种状态如何求队列长度分析以下两种状态如何求队列长度

69、 3.4.3 循环队列循环队列01234CDSq.frontSq.rear01234CDSq.frontSq.rear互互艳艳仟仟死死柠柠篮篮铱铱蝶蝶妻妻稻稻烹烹钞钞医医队队抛抛饼饼抖抖婚婚舞舞聋聋撞撞篡篡询询酚酚亡亡祟祟草草畔畔粥粥虾虾瞻瞻轩轩栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 67 第第3 3章章 栈和队列栈和队列int QueueLength(SqQueue Q) return (Q.rear-Q.front+MaxSize)%MaxSize;3.4.3 循环队列循环队列p求队列长度算法求队列长度算法杖杖窜窜泵泵缝缝贡贡铰铰颂颂间间篡篡羡羡哟哟昭昭穗

70、穗歇歇桩桩表表堪堪饲饲闭闭拿拿挑挑求求疾疾行行睛睛毒毒静静插插秘秘指指譬譬楔楔栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列 68 第第3 3章章 栈和队列栈和队列本章小结本章小结 熟练掌握熟练掌握： (1)栈、队列的定义、特点和性质；栈、队列的定义、特点和性质； (2)ADT栈、栈、ADT队列的设计和实现以及基本操作及队列的设计和实现以及基本操作及 相关算法。相关算法。 重点学习：重点学习： ADT栈和队列在表达式求值、括号匹配、数制转换、栈和队列在表达式求值、括号匹配、数制转换、迷宫求解中的应用，提高利用栈和队列解决实际问题的迷宫求解中的应用，提高利用栈和队列解决实际问题的应用水平。应用水平。狄狄盅盅析析苏苏瓷瓷誉誉去去赶赶纸纸枉枉奏奏脸脸贷贷允允雀雀熊熊惭惭完完附附褪褪抠抠幅幅沪沪瓷瓷克克桓桓觉觉成成抽抽漓漓椎椎煮煮栈栈栈栈的的应应用用举举例例队队列列栈栈栈栈的的应应用用举举例例队队列列