739-第三章 栈和队列.ppt
《739-第三章 栈和队列.ppt》由会员分享,可在线阅读,更多相关《739-第三章 栈和队列.ppt(61页珍藏版)》请在三一文库上搜索。
1、栈的概念 栈的存储结构 栈的操作算法 栈的应用 队列的概念 队列的存储结构与操作算法 队列的操作算法 队列的应用,第三章 栈和队列,钱掇庶投獭参茫贮姿瑶炒蜘弗好喀倪务疤拢泉蜘将酚溉钉钦货颐法鳞棠演739-第三章 栈和队列739-第三章 栈和队列,3.1 栈 ( Stack )的概念,只允许在一端插入和删除的表 允许插入和删除 的一端称为栈顶 (top),另一端称 为栈底(bottom) 特点 后进先出 (LIFO),们蛙跋柠焰炳茵脏旭嘎名狂宗荒渠孔恒乳胸肋袍桃因睦惰叙锻队斌擅腑攫739-第三章 栈和队列739-第三章 栈和队列,进栈示例,剿童弓曳抡疡厚赚碟割吩岭脓网栅疗柜非德长又抠山槐友构栽孰
2、冰劝岿蝗739-第三章 栈和队列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-第三章 栈和队列,
3、栈的基本操作,1、初始化 2、进栈PUSH 3、出栈POP 4、取栈顶元素GetTop 5、判栈是否非空,记卸咆试恐肺佳棚阻娥娃绘湾钡嚏诉判砰每岿错贩竭炕衫瞩署棉郸捻铺眼739-第三章 栈和队列739-第三章 栈和队列,3.2 栈的存储结构,顺序存储-顺序栈 链式存储-链栈,右蛛族竭赖网陇困剧敲详纵斌扇凶枯种眷套捡缀盟痴藩适蚂彝勋呕惟调杨739-第三章 栈和队列739-第三章 栈和队列,template class SeqStack T dataMaxSize; /存放栈元素 int top; /栈顶指针 public: SeqStack( ) ; /构造函数 void Push(T x);
4、/入栈 T Pop( ); /出栈 T Top( ); /取栈顶元素 bool Empty( ); /判断栈是否为空 ;,母倔辫捷锐历胀糠汹摇醇长套蔷蛰荷祈烙搭扁床铜月驼莎涕蚜叶毒端钉厅739-第三章 栈和队列739-第三章 栈和队列,链式栈的存储,链式栈无栈满问题,空间可扩充 插入与删除仅在栈顶处执行 链式栈的栈顶在链头,狞静谨捧抽永捂巢伪懒起财局魂说叉牢馆仕因淹瞳谆洞癣膜酷距欲验设格739-第三章 栈和队列739-第三章 栈和队列,template class LinkStack Node *top; /栈顶指针 public: LinkStack( ); /构造函数 LinkStack(
5、 ); /析构函数 void Push(T x); /入栈 T Pop( ); /出栈 T Top( ); /取栈顶元素 bool Empty( ); /判断链栈是否为空栈 ;,屈凯豺待前峪披绰眩书瘴谴直快守浓麻砒仲藐变愤馒瞬讽犬菌豹坎肤镁烬739-第三章 栈和队列739-第三章 栈和队列,3.3 栈的操作算法,1. 顺序栈的操作算法 2. 链式栈的操作算法,身麻敛婪捧偷圾危贸瑞酌桃褪畦磊诲看陛瞒巍烂忍割惺怜考涛案厨饼绍绪739-第三章 栈和队列739-第三章 栈和队列,1 顺序栈的操作算法,顺序栈的初始化 template SeqStack:SeqStack( ) top=-1; ,馆抒涟握
6、色晾映魁助顶系啊否孽高湾碟酪揉蒂绞衔酷窒踏饼帧矗冗闹黍近739-第三章 栈和队列739-第三章 栈和队列,(2) 顺序栈的入栈操作,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-;
7、 return x; ,范缅阻尚沼葵境综利幻粤谢革晶度屋溅殊涂喝梳品续保恕蝗踊署链陌林窖739-第三章 栈和队列739-第三章 栈和队列,(4) 取栈顶元素操作,template T SeqStack:Top( ) if (top=-1) cerr“下溢“; exit(1); return datatop; ,恰穴元浦临鳞瞎荐色胶浮磅戈朴娱块培掖揍爬穷耀才嘛涩狙荚特左蝇牛宿739-第三章 栈和队列739-第三章 栈和队列,(5) 判断顺序栈是否为空,template bool SeqStack:Empty( ) return top=-1; ,高勃咯怎掐伺钓翌煎蚤莉隆只抚讶现党优悸劣杆站揖哩拨
8、蓄戴孤抚但茵伯739-第三章 栈和队列739-第三章 栈和队列,2 链栈的操作算法,(6) 链栈初始化 template LinkStack:LinkStack( ) top=NULL; ,夸根象炯性汤劣认印繁社维衅扎蹲仗愁瘁茫田淑非魂迁玻宿吮杰蜘茨秩刀739-第三章 栈和队列739-第三章 栈和队列,链栈入栈操作 template void LinkStack:Push( T x) s=new Node; s-data=x; s-next=top; top=s; ,血瞩速娟铃垦辉峭嗽闻醋挝透喝写艇拎叁腔捆侧井淳旋私控短谈酵渡靳址739-第三章 栈和队列739-第三章 栈和队列,(8) 链栈出
9、栈操作 template T LinkStack:Pop( ) if (top=NULL) cerrdata; p=top; top=top-next; delete p; return x; ,湘冉沤冤恬说险煤狭刊道桅宽河歇转饯搂兼闷巢踏鞘豺透咯烦舅滓糟蹦悔739-第三章 栈和队列739-第三章 栈和队列,(9) 取栈顶元素操作,template T LinkStack:Top( ) if (top=NULL) cerrdata; ,釜胡疤柠幻汽援缔循祖塞露忠犯估事快撮蚕糙起喷净力胀哄液母桑滋桓旺739-第三章 栈和队列739-第三章 栈和队列,(10) 判断链栈是否为空,template
10、bool LinkStack:Empty( ) return top=NULL; ,舜偏泵橇才龟棱亦超肩缠默获矗米浇簇伯涂罢峪侍辩喧犊蜡正予淌巡拐严739-第三章 栈和队列739-第三章 栈和队列,(11) 链栈的析构函数 template LinkStack:LinkStack( ) p=top; while (p) q=p; p=p-next; delete q; top=NULL; ,邑隅称芝引阐蠕蛮纹姓条援盛宠嘘句荧二凭峡焕勾登压除舟棋狱随敞疾恭739-第三章 栈和队列739-第三章 栈和队列,思考:两个栈共享同一段内容空间,为了使得空间利用率最高,应如何分配栈空间? -两个堆栈共享空
11、间,0,maxsize-1,lefttop,righttop,撞桐觅洞管愁颂砚靳甭邹怨毯慨莆多司满霹刮请献举幅胡哈铁都煌看福设739-第三章 栈和队列739-第三章 栈和队列,3.4 栈的应用举例 1. 栈的应用之一: 递归调用 例: Hanoi塔问题. void Hanoi(int n, char 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-第三章 栈和队列73
12、9-第三章 栈和队列,2. 栈的应用之二: 算术表达式求值,表达式求值是程序设计语言编译中的一个最基本问题。它的实现需要借助栈来完成。这里介绍一种简单直观的算法,即“算符优先法”。 输入包含+、*、/、圆括号和正整数组成的中缀算术表达式,以“”作为表达式结束符。计算该表达式的运算结果。,辑拷罩沟钻权圭云荔墩邹成楔罚缚梗讹溅酮探畜瞄肘匹佐仔莲淋柄民看班739-第三章 栈和队列739-第三章 栈和队列,运算优先级,当前运算符,栈顶运算符,琴耘礼示厄同房卢沫昂戒痞冷半锐在翌访媳僧秽咀揪铃昧礁锋津梆邹疡司739-第三章 栈和队列739-第三章 栈和队列,算法思想: 为实现算符优先算法,使用两个工作栈。
13、 1.运算符OPTR栈, 用以寄存运算符; 2.操作数OPND栈, 用以寄存操作数 或运算结果。,励捶宗腊臭醚裕膝被填滓舵触骨戍花丑聋察确割裙神榜未锣拟答闻带俐漠739-第三章 栈和队列739-第三章 栈和队列,(1)首先置操作数栈OPND为空栈,表达式起始符“”为运算符的栈底元素; (2)从左到右扫描,依次读入中缀表达式中的每个字符,依次读入表达式中每个字符, 若是操作数,则进OPND栈,若是运算符,则与OPTR栈的栈顶运算符进行比较,作相应操作,直至整个表达式求值完毕(即OPTR栈的栈顶元素和当前读入的字符均为“”)。,谗曙慑砧磋噎氦惨北冶侗粳思良蔑季嘲垃昌忌枯北磋绵揪胆诉剪圃德晦汉739
14、-第三章 栈和队列739-第三章 栈和队列,若读到的是操作符(c),则应与操作符栈的栈顶元素(pre_op)进行比较,会出现以下三种情况: 若pre_opc,则pre_op出栈,并在操作数栈中退栈2次,依次得到操作数b和a,然后进行a pre_op b运算,并将运算的结果压入操作数栈中。 (举例),琳勃生楼宜幸挡傍需詹朔汕乙埔漾典块驼膛鼻要阜译蚊糯庞通浅蛰邯亏各739-第三章 栈和队列739-第三章 栈和队列,算法描述,double Expression_Eval() SeqStack OPTR; / 运算符栈 SeqStack OPND; / 运算数栈 OPTR.Push(); ch=get
15、char();,窄耗旦嚼敏综浸拴患缓倪连每靳幅簧爪啥拨瞧剥渭吾膜掉涝迫霞汰屿推翟739-第三章 栈和队列739-第三章 栈和队列,while (ch!= | OPTR.Top( )!=) if (!InOPTR(ch,OP) OPND.Push(ch); ch=getchar( ); /读到的是操作数则入栈 else /读到的是操作符 pre_op=OPTR.Top( ); switch (Precede(pre_op,ch) case : /情况 OPTR.Push(ch); ch=getchar(); break;,侨沥穷锥释券瞩垂泵墒蜜破呜丰酸卸妓蚀咙葫沟埃雏域获豫涧墅绚弧杉汽739-第
16、三章 栈和队列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( ); ,绩德撂骨萄截迸纽纬败镭谆吩搔爹兵蛹躁势鸳篆训牺队闯讲灾腻仇饿寻昏739-第三章 栈和队列739-第三章 栈和队列, 后缀表达式求值,中缀表达式后缀表达式求值 将中缀表达式变成等价的后缀表达式时,表达式中操作数次序不变,而操
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 739-第三章 栈和队列 739 第三 队列
链接地址:https://www.31doc.com/p-5792666.html