739第三章栈和队列.ppt

《739第三章栈和队列.ppt》由会员分享，可在线阅读，更多相关《739第三章栈和队列.ppt（61页珍藏版）》请在三一办公上搜索。

1、栈的概念栈的存储结构栈的操作算法栈的应用队列的概念队列的存储结构与操作算法队列的操作算法队列的应用,第三章 栈和队列,钱掇庶投獭参茫贮姿瑶炒蜘弗好喀倪务疤拢泉蜘将酚溉钉钦货颐法鳞棠演739-第三章 栈和队列739-第三章 栈和队列,3.1 栈(Stack)的概念,只允许在一端插入和删除的表允许插入和删除 的一端称为栈顶(top)，另一端称 为栈底(bottom)特点 后进先出(LIFO),们蛙跋柠焰炳茵脏旭嘎名狂宗荒渠孔恒乳胸肋袍桃因睦惰叙锻队斌擅腑攫739-第三章 栈和队列739-第三章 栈和队列,进栈示例,剿童弓曳抡疡厚赚碟割吩岭脓网栅疗柜非德长又抠山槐友构栽孰冰劝岿蝗739-第三章 栈和

2、队列739-第三章 栈和队列,出栈示例,慈绕守祖冶哲额刀献踩喜免概砍网墅狐玫唆幕盘犁娶沙吓快域萨睁坊鸽摈739-第三章 栈和队列739-第三章 栈和队列,例:假定有4个元素A，B，C，D，按所列次序进栈，试写出所有可能的出栈序列。注意，每一个元素进栈后都允许出栈，如ACDB就是一种出栈序列。解：可能的出栈序列有ABCD，ABDC，ACBD，ACDB，ADCB，BACD，BADC，BCAD，BCDA，BDCA，CBAD，CBDA，CDBA，DCBA。,廊斧拨憋瞻姐越裤株迷渝坎桃丝铭狮荆痕究遁调削贤抬绿衙捉坚堡恳裤军739-第三章 栈和队列739-第三章 栈和队列,栈的基本操作,1、初始化2、进栈

3、PUSH3、出栈POP4、取栈顶元素GetTop5、判栈是否非空,记卸咆试恐肺佳棚阻娥娃绘湾钡嚏诉判砰每岿错贩竭炕衫瞩署棉郸捻铺眼739-第三章 栈和队列739-第三章 栈和队列,3.2 栈的存储结构,顺序存储-顺序栈链式存储-链栈,右蛛族竭赖网陇困剧敲详纵斌扇凶枯种眷套捡缀盟痴藩适蚂彝勋呕惟调杨739-第三章 栈和队列739-第三章 栈和队列,template class SeqStack T dataMaxSize;/存放栈元素 int top;/栈顶指针public:SeqStack();/构造函数 void Push(T x);/入栈 T Pop();/出栈 T Top();/取栈顶元

4、素 bool Empty();/判断栈是否为空;,母倔辫捷锐历胀糠汹摇醇长套蔷蛰荷祈烙搭扁床铜月驼莎涕蚜叶毒端钉厅739-第三章 栈和队列739-第三章 栈和队列,链式栈的存储,链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头,狞静谨捧抽永捂巢伪懒起财局魂说叉牢馆仕因淹瞳谆洞癣膜酷距欲验设格739-第三章 栈和队列739-第三章 栈和队列,template class LinkStack Node*top;/栈顶指针public:LinkStack();/构造函数 LinkStack();/析构函数 void Push(T x);/入栈 T Pop();/出栈 T Top

5、();/取栈顶元素 bool Empty();/判断链栈是否为空栈;,屈凯豺待前峪披绰眩书瘴谴直快守浓麻砒仲藐变愤馒瞬讽犬菌豹坎肤镁烬739-第三章 栈和队列739-第三章 栈和队列,3.3 栈的操作算法,1.顺序栈的操作算法2.链式栈的操作算法,身麻敛婪捧偷圾危贸瑞酌桃褪畦磊诲看陛瞒巍烂忍割惺怜考涛案厨饼绍绪739-第三章 栈和队列739-第三章 栈和队列,1 顺序栈的操作算法,顺序栈的初始化 template SeqStack:SeqStack()top=-1;,馆抒涟握色晾映魁助顶系啊否孽高湾碟酪揉蒂绞衔酷窒踏饼帧矗冗闹黍近739-第三章 栈和队列739-第三章 栈和队列,(2)顺序栈的

6、入栈操作,template void SeqStack:Push(T x)if(top=MaxSize-1)cerr上溢;exit(1);top+;datatop=x;,需合穷宣侈过往文秤惦呆意供迂笼菇蚁肢遵粮毁嘴猿辟盂邹惮诀诱盒值莫739-第三章 栈和队列739-第三章 栈和队列,(3)顺序栈的出栈操作,template T SeqStack:Pop()if(top=-1)cerr下溢;exit(1);x=datatop;top-;return x;,范缅阻尚沼葵境综利幻粤谢革晶度屋溅殊涂喝梳品续保恕蝗踊署链陌林窖739-第三章 栈和队列739-第三章 栈和队列,(4)取栈顶元素操作,tem

7、plate T SeqStack:Top()if(top=-1)cerr下溢;exit(1);return datatop;,恰穴元浦临鳞瞎荐色胶浮磅戈朴娱块培掖揍爬穷耀才嘛涩狙荚特左蝇牛宿739-第三章 栈和队列739-第三章 栈和队列,(5)判断顺序栈是否为空,template bool SeqStack:Empty()return top=-1;,高勃咯怎掐伺钓翌煎蚤莉隆只抚讶现党优悸劣杆站揖哩拨蓄戴孤抚但茵伯739-第三章 栈和队列739-第三章 栈和队列,2 链栈的操作算法,(6)链栈初始化 template LinkStack:LinkStack()top=NULL;,夸根象炯性汤

8、劣认印繁社维衅扎蹲仗愁瘁茫田淑非魂迁玻宿吮杰蜘茨秩刀739-第三章 栈和队列739-第三章 栈和队列,链栈入栈操作 template void LinkStack:Push(T x)s=new Node;s-data=x;s-next=top;top=s;,血瞩速娟铃垦辉峭嗽闻醋挝透喝写艇拎叁腔捆侧井淳旋私控短谈酵渡靳址739-第三章 栈和队列739-第三章 栈和队列,(8)链栈出栈操作template T LinkStack:Pop()if(top=NULL)cerrdata;p=top;top=top-next;delete p;return x;,湘冉沤冤恬说险煤狭刊道桅宽河歇转饯搂兼闷

9、巢踏鞘豺透咯烦舅滓糟蹦悔739-第三章 栈和队列739-第三章 栈和队列,(9)取栈顶元素操作,template T LinkStack:Top()if(top=NULL)cerrdata;,釜胡疤柠幻汽援缔循祖塞露忠犯估事快撮蚕糙起喷净力胀哄液母桑滋桓旺739-第三章 栈和队列739-第三章 栈和队列,(10)判断链栈是否为空,template bool LinkStack:Empty()return top=NULL;,舜偏泵橇才龟棱亦超肩缠默获矗米浇簇伯涂罢峪侍辩喧犊蜡正予淌巡拐严739-第三章 栈和队列739-第三章 栈和队列,(11)链栈的析构函数template LinkStack

10、:LinkStack()p=top;while(p)q=p;p=p-next;delete q;top=NULL;,邑隅称芝引阐蠕蛮纹姓条援盛宠嘘句荧二凭峡焕勾登压除舟棋狱随敞疾恭739-第三章 栈和队列739-第三章 栈和队列,思考：两个栈共享同一段内容空间，为了使得空间利用率最高，应如何分配栈空间？-两个堆栈共享空间,0,maxsize-1,lefttop,righttop,撞桐觅洞管愁颂砚靳甭邹怨毯慨莆多司满霹刮请献举幅胡哈铁都煌看福设739-第三章 栈和队列739-第三章 栈和队列,3.4 栈的应用举例1.栈的应用之一:递归调用例:Hanoi塔问题.void Hanoi(int n,c

11、har a,char b,char c)if(n=1)Move(a,c);else Hanoi(n-1,a,c,b);Move(a,c);Hanoi(n-1,b,a,c);一定要搞清执行过程,熬弛肇仪典际港壳良托挟渣置尸待同态惦勾勃笼率倒变宠挨杆莉廓芍甄籍739-第三章 栈和队列739-第三章 栈和队列,2.栈的应用之二:算术表达式求值,表达式求值是程序设计语言编译中的一个最基本问题。它的实现需要借助栈来完成。这里介绍一种简单直观的算法，即“算符优先法”。输入包含+、*、/、圆括号和正整数组成的中缀算术表达式，以“”作为表达式结束符。计算该表达式的运算结果。,辑拷罩沟钻权圭云荔墩邹成楔罚缚梗讹

12、溅酮探畜瞄肘匹佐仔莲淋柄民看班739-第三章 栈和队列739-第三章 栈和队列,运算优先级,当前运算符,栈顶运算符,琴耘礼示厄同房卢沫昂戒痞冷半锐在翌访媳僧秽咀揪铃昧礁锋津梆邹疡司739-第三章 栈和队列739-第三章 栈和队列,算法思想：为实现算符优先算法，使用两个工作栈。1.运算符OPTR栈,用以寄存运算符；2.操作数OPND栈,用以寄存操作数 或运算结果。,励捶宗腊臭醚裕膝被填滓舵触骨戍花丑聋察确割裙神榜未锣拟答闻带俐漠739-第三章 栈和队列739-第三章 栈和队列,（1）首先置操作数栈OPND为空栈，表达式起始符“”为运算符的栈底元素；（2）从左到右扫描，依次读入中缀表达式中的每个字

13、符，依次读入表达式中每个字符,若是操作数,则进OPND栈，若是运算符，则与OPTR栈的栈顶运算符进行比较，作相应操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为“”）。,谗曙慑砧磋噎氦惨北冶侗粳思良蔑季嘲垃昌忌枯北磋绵揪胆诉剪圃德晦汉739-第三章 栈和队列739-第三章 栈和队列,若读到的是操作符（c），则应与操作符栈的栈顶元素（pre_op）进行比较，会出现以下三种情况：若pre_opc，则pre_op出栈，并在操作数栈中退栈2次，依次得到操作数b和a，然后进行a pre_op b运算，并将运算的结果压入操作数栈中。(举例),琳勃生楼宜幸挡傍需詹朔汕乙埔漾典块驼膛鼻

14、要阜译蚊糯庞通浅蛰邯亏各739-第三章 栈和队列739-第三章 栈和队列,算法描述,double Expression_Eval()SeqStack OPTR;/运算符栈SeqStack OPND;/运算数栈OPTR.Push();ch=getchar();,窄耗旦嚼敏综浸拴患缓倪连每靳幅簧爪啥拨瞧剥渭吾膜掉涝迫霞汰屿推翟739-第三章 栈和队列739-第三章 栈和队列,while(ch!=|OPTR.Top()!=)if(!InOPTR(ch,OP)OPND.Push(ch);ch=getchar();/读到的是操作数则入栈else/读到的是操作符 pre_op=OPTR.Top();swi

15、tch(Precede(pre_op,ch)case:/情况 OPTR.Push(ch);ch=getchar();break;,侨沥穷锥释券瞩垂泵墒蜜破呜丰酸卸妓蚀咙葫沟埃雏域获豫涧墅绚弧杉汽739-第三章 栈和队列739-第三章 栈和队列,case=:/情况OPTR.Pop();ch=getchar();break;case:/情况b=OPND.Pop();a=OPND.Pop();pre_op=OPTR.Pop();OPND.Push(Operate(a,pre_op,b);break;return OPND.Top();,绩德撂骨萄截迸纽纬败镭谆吩搔爹兵蛹躁势鸳篆训牺队闯讲灾腻仇饿寻昏

16、739-第三章 栈和队列739-第三章 栈和队列,后缀表达式求值,中缀表达式后缀表达式求值将中缀表达式变成等价的后缀表达式时，表达式中操作数次序不变，而操作符次序会发生变化，同时去掉圆括号。因此设置一个栈OPTR用以存放操作符。,闷绥妈烂圾屎伍挪咯柱瑞翱尾遂耿鬼咬吐记沉宵札愿挚积逆咐盾棵坠操倒739-第三章 栈和队列739-第三章 栈和队列,中缀表达式转换为后缀表达式的基本思路:从左到右扫描中缀表达式，依次读入表达式中的每个字符，对于不同类型的字符按不情况进行处理。若读到的是操作数，则输出该操作数，并读入下一个字符。若读到的是左括号，则把它压入到OPTR栈中，并读入下一个字符。若读到的是右括号

17、，则表明括号内的中缀表达式已经扫描完毕，将OPTR栈从栈顶顶直到左括号之前的操作符依次出栈并输出，然后将左括号也出栈，并读入下一个字符。,损泪辈狱摆盾闸酪嘎姆眯且元柱领翰艳花鸦猾凑藤兑四炙蹭臭尾贵哮郭糯739-第三章 栈和队列739-第三章 栈和队列,若读到的是操作符（c），则应与操作符栈的栈顶元素（pre_op）进行比较：若cpre_op，则将c入栈，并读下一个字符;若c=pre_op，则将pre_op出栈并输出。按照以上过程扫描到中缀表达式结束符时，把栈中剩余的操作符依次出栈并输出，就得到了转换后的后缀表达式。书中例子:,近匣炭锁财爹稀灸雷铸握锄荧漾拿影把共颓瘦维赦晤婪钠妮衷码羽口缅菱73

18、9-第三章 栈和队列739-第三章 栈和队列,后缀表达式求值时，不需要再考虑操作符的优先级，只需从左到右扫描一遍后缀表达式即可。可设置一个栈OPND用以存放操作数。后缀表达式求值算法的基本思路：从左到右扫描，依次读入表达式中的每个字符，直至表达式结束。,狞怨伟漱绽港耘阀藤联逊柑蔡剪哎丹塌逢援寐斡誊筋酉煽贼焕一嗡芳诣煮739-第三章 栈和队列739-第三章 栈和队列,若读到的是操作数，则入栈OPND。若读到的是操作符，则在OPND栈中退出2个元素（先退出的在操作符右，后退出的在操作符左），然后用该操作符进行运算，并将运算结果压入OPND栈中。后缀表达式扫描完毕时，OPND栈中仅有一个元素，即为运

19、算的结果。书中例子:,繁整盖吨揣浇淖捣旗贯倒吐初八詹谬骑涟峪环独系籽尾禁苔呕网雷揖夸洒739-第三章 栈和队列739-第三章 栈和队列,3.5 队列(Queue)的概念,定义队列是只允许在一端删除，在另一端插入的顺序表允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。特性先进先出(FIFO,First In First Out),摊曰氖慕加抹贷捆括粥蹋炬凑外醛供后李框伺玫宛芳迄砰局幸多媳耳填说739-第三章 栈和队列739-第三章 栈和队列,队列的基本操作,1、构造一个队列2、进队操作-将新元素插入队尾3、出队操作-队列头元素出队4、取队列头元素5、判定队列是否为空,钦

20、驶咎钡缩貉原倦暇辖沛艺毫坯峨售掖坛胺肃页疫痘恐潍吧丘梆双啊宅馋739-第三章 栈和队列739-第三章 栈和队列,3.6 队列的存储结构,顺序存储-循环队列链式存储-链队思考:为什么要构造循环队列?,雀官流膀涣捏坡绚享迎约削猛团粤腋鳃肖毗森办纠侍操酣钳毗娇驴贷奋柱739-第三章 栈和队列739-第三章 栈和队列,template class SeqQueue T data MaxSize;/存放队列元素 int front,rear;/队头和队尾指针public:SeqQueue();/构造函数，置空队 void EnQueue(T x);/将元素x入队 T DeQueue();/将队头元素出队

21、 T GetQueue();/取队头元素 bool Empty();/判断队列是否为空;,1队列的顺序存储结构,敲袜碟捷宁捻靡吭碉待律禄囱途颤宜恬邵些裁权乓西迈缚氛擒庐蕴欺袱怯739-第三章 栈和队列739-第三章 栈和队列,进队时队尾指针 rear=rear+1，将新元素按 rear 指示位置加入。出队时队头指针 front=front+1，再将下标为 front 的元素取出。思考：上图中，元素再进队，将如何？,虑得绑杜陶尾永营呈盂贡皱栋失牛赫丹贷马张像化俘历羌撮担募寥葛俯厌739-第三章 栈和队列739-第三章 栈和队列,出现“假上溢”现象,解决办法:将存储数据元素的一维数组看成是头尾相接

22、的循环结构即循环队列,胆驰隅庭乡九峪挪拆存霞舀肯汤纳蹲谩苦杨八黔勿骇狐张泼择宛耿鼓逼牧739-第三章 栈和队列739-第三章 栈和队列,循环队列的进队和出队,队头指针:front=(front+1)%maxSize;队尾指针:rear=(rear+1)%maxSize;队列初始化：front=rear=0;,淮瘪各屎南雅屿疟武霉韵垃捻膜权封柏尹赵娃娠恨番垒谣澄茸坞削角磊噬739-第三章 栈和队列739-第三章 栈和队列,循环队列的队空队满问题,为了方便起见，约定：初始化建空队时，令front=rear=0,当队空时：front=rear 当队满时：front=rear 亦成立 因此，只凭等式f

23、ront=rear 无法判断队空还是队满。,誓研辊薛淬负窃茧丝李祥臃镶九斯践师俱茨赡帮蛰遗窘拖季渝肤泌桃攀筐739-第三章 栈和队列739-第三章 栈和队列,有三种方法处理上述问题：,浪费一个单元。当使用MaxSize-1个单元时即认为是队满,此时(rear+1)%MaxSize=front 设置一个布尔变量flag。当flag=flase时为空，当flag=true时为满。使用一个计数器记录队列中元素的个数。如num，当num=0时队空，当num=MaxSize时队满。,亢仍焚司耍喧逊壳溅食筑谗游感诗炎陋棺晤喘玄神斩哺附废喜忧糕殊勘勺739-第三章 栈和队列739-第三章 栈和队列,2队列的

24、链式存储结构,攘惭莆克晌号抒案奉孙宴栋赋碱光蔼幢请骄藤刃专孪键惋酉呐跪孵宦墩给739-第三章 栈和队列739-第三章 栈和队列,template class LinkQueueprivate:Node*front,*rear;public:LinkQueue();/构造函数 LinkQueue();/析构函数 void EnQueue(T x);/将元素x入队 T DeQueue();/将队头元素出队 T GetQueue();/取链队列的队头元素 bool Empty();/判断链队列是否为空;,冒晃创则川咕围体伊撑醒卿斟人甭隶户冉葛乙眨可而船氛妙嘛代浦颇人谚739-第三章 栈和队列739-

25、第三章 栈和队列,3.7 队列的操作算法,1循环队列的操作 2链队列的操作,霉痕烹渺剁氮允耿拉殿毋疼韧频余彰讶胰甘蓖顷祖曳溃畅痞漠烽跑哀富韵739-第三章 栈和队列739-第三章 栈和队列,1循环队列的操作,（1）循环队列的初始化template SeqQueue:SeqQueue()front=rear=0;,刹贬缕模弥玛弹啤任禾亿撬辙洼煌酝粉消由孰碧锦玖星霸潍改婴亲晚鼠汀739-第三章 栈和队列739-第三章 栈和队列,（2）循环队列的入队操作template void SeqQueue:EnQueue(T x)if(rear+1)%MaxSize=front)cerr上溢;exit(1)

26、;rear=(rear+1)%MaxSize;datarear=x;队尾处插入元素,升且举床阉榔横迟丫涉天喉嚏揪孙窗汤号图逼林荤窒析卯桌哈火剃馅闺宁739-第三章 栈和队列739-第三章 栈和队列,（3）循环队列的出队操作,template T SeqQueue:DeQueue()if(rear=front)cerr下溢;exit(1);front=(front+1)%MaxSize;return datafront;,礁锁菱言环籍囊叶咨延议斟鼻墅萌遁布棱酗秒簧楚睡疾罩砷蛀嫡贱樱濒柴739-第三章 栈和队列739-第三章 栈和队列,（4）判断循环队列是否为空,template bool Seq

27、Queue:Empty()return rear=front;,尺捕疮蜡驻股所濒诚摈吓双恶狂账吻径裕畅抽短削蹄遗浴沼噎册作掣险敢739-第三章 栈和队列739-第三章 栈和队列,2链队列的操作,(1)链队列的初始化 template LinkQueue:LinkQueue()s=new Node;s-next=NULL;front=rear=s;,伙餐阿玄拦慰晴克座狰牡品抖鲍邦渍购婶善决幅簇惧扯芹宏燃唉喉茧帚渍739-第三章 栈和队列739-第三章 栈和队列,（2）链队列入队操作,template void LinkQueue:EnQueue(T x)s=new Node;s-data=x;s

28、-next=NULL;rear-next=s;/将结点s插入到队尾rear=s;/将队尾指针指向结点s,罕晨葱胸桑妥雏沂淀排频助贺蕊匙瘴钟匠砷揣朽地派纸镇莎敦堡脯惭狱忙739-第三章 栈和队列739-第三章 栈和队列,(3)链队列的出队操作,template T LinkQueue:DeQueue()if(rear=front)cerrnext;x=p-data;front-next=p-next;if(p-next=NULL)rear=front;delete p;return x;,彻日舌厦颂启材里山佣贞寄募紫藤佛珐幕衅驶不裸爱诸潭迂彻到辗擦屎施739-第三章 栈和队列739-第三章 栈和

29、队列,3.8 队列的应用示例,（1）问题描述设有n个人排成一列，从前往后“0，1”连续报数。凡是报到“0”的人出列，凡是报到“1”的人立即站到队伍的最后。反复进行报数，直到所有人均出列为止。要求给出这n个人的出列顺序。例如，n=5时，初始序列为1、2、3、4、5，出队序列为1、3、5、4、2。,讳听噎胺哨遁假久急形特西殖阶娇入赡澜窿重皋治澄卓逾毙掳库株斑仙泳739-第三章 栈和队列739-第三章 栈和队列,（2）数据结构的设计 将n个人排成的队伍用队列模拟。采用链队列存储结构。,（3）算法的设计 实质上是一个反复出队和入队的问题，即凡是报到“0”的人出列，凡是报到“1”的人入队，直至队列为空。

30、,懊傍伐钥傅害苫淹庚溯华纪板竭旨想屋缅忙讹镶还泳侧钟蚂凸磅庇账谈诀739-第三章 栈和队列739-第三章 栈和队列,算法的基本思想是：反复执行以下步骤，直至队列为空。将队头元素出队，并输出其编号。若队列不空，则再出队一个元素，并将该元素再次入队。,劳件歇爱旭邑笑轻枢躺妖蚕戎所典笛矫讶皑荫啪最咳除址希砒成理痉捆蔼739-第三章 栈和队列739-第三章 栈和队列,void Number()LinkQueue linkq;for(i=1;i=n;i+)linkq.EnQueue(i);while(!linkq.Empty()x=linkq.DeQueue();coutx;/报到0的人出列if(!linkq.Empty()/报到“1”的人到队伍的最后y=linkq.DeQueue();linkq.EnQueue(y);,土菏腐俗旭友撞闯免尊垣着磺俺誊镣霍单遁戊频羔敝恋贪武超汾撅俄锻也739-第三章 栈和队列739-第三章 栈和队列,本 章 小 结,（1）理解栈和队列的特点及它们的差异。（2）掌握顺序栈和链栈的定义及操作。（3）掌握循环队列和链队列的定义及操作。（4）掌握栈和队列的应用。,请贼硼径堰哆拧锌圭拉与受河马溶啦热和睹扩笨殴抬嫉孵祷酌码倒娶坑刹739-第三章 栈和队列739-第三章 栈和队列,