739-第三章-栈和队列

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