数据结构第4章栈和队列

69第4章栈和队列一、复习要点本章主要讨论3种线性结构：栈、队列与优先级队列。这3种结构都是顺序存取的表，而且都是限制存取点的表。栈限定只能在表的一端（栈顶）插入与删除，其特点是先进后出。队列和优先级队列限定只能在表的一端（队尾）插入在另一端（队头）删除，不过优先级队列在插入和删除时需要根据数据对象的优先级做适当的调整，令优先级最高的对象调整到队头，其特点是优先级高的先出。而队列不调整，其特点是先进先出。这几种结构在开发各种软件时非常有用。本章复习的要点：1、基本知识点要求理解栈的定义和特点，栈的抽象数据类型和在递归和表达式计算中的使用，在栈式铁路调车线上当进栈序列为1,2,3,,n时，可能的出栈序列计数，栈的顺序存储表示和链接存储表示，特别要注意，链式栈的栈顶应在链头，插入与删除都在链头进行。另外，需要理解队列的定义和特点，队列的抽象数据类型和在分层处理中的使用，队列的顺序存储表示（循环队列）和链接存储表示，需要注意的是，链式队列的队头应在链头，队尾应在链尾。还需要理解优先级队列的定义和特点。优先级队列的最佳存储表示是堆（heap），本章介绍的表示看懂即可。2、算法设计栈的5种操作（进栈、退栈、取栈顶元素、判栈空、置空栈）的在顺序存储表示下的实现，以及在链接存储表示下的实现。使用栈的后缀表达式计算算法双栈共用一个数组的进栈、退栈、置空栈、判栈空算法及栈满、栈空条件使用两个栈模拟一个队列时的进队列和出队列算法循环队列的进队列、出队列、取队头元素、判队列空、置空队列操作的实现使用tag区分队列空和队列满的循环队列的进队列和出队列操作的实现链式队列的进队列、出队列、取队头元素、判队列空、置空队列操作的实现使用队尾指针rear和队列长度length的链式队列的进队列、出队列、取队头元素、判队列空、置空队列操作的实现队列在分层处理中的使用事例（杨辉三角形按层次打印）双端队列的顺序存储表示及其进队列、出队列算法及队空、队满条件二、难点和重点1、栈：栈的特性、栈的基本运算栈的数组实现、栈的链表实现栈满及栈空条件、抽象数据类型中的先决条件与后置条件2、栈的应用：用后缀表示计算表达式，中缀表示改后缀表示3、队列：队列的特性、队列的基本运算队列的数组实现：循环队列中队头与队尾指针的表示，队满及队空条件队列的链表实现：链式队列中的队头与队尾指针的表示、4、双向队列：双向队列的插入与删除算法5、优先级队列：优先级队列的插入与删除算法70132)16/(1612C三、教材中习题的解析4-1改写顺序栈的进栈成员函数Push(x)，要求当栈满时执行一个stackFull()操作进行栈满处理。其功能是：动态创建一个比原来的栈数组大二倍的新数组，代替原来的栈数组，原来栈数组中的元素占据新数组的前MaxSize位置。【解答】templateclassTypevoidstackType::push(constType&item){if(isFull())stackFull();//栈满，做溢出处理elements[++top]=item;//进栈}templateclassTypevoidstackType::stackFull(){Type*temp=newType[3*maxSize];//创建体积大二倍的数组for(inti=0;i=top;i++)temp[i]=elements[i];//传送原数组的数据delete[]elements;//删去原数组maxSize*=3;//数组最大体积增长二倍elements=temp;//新数组成为栈的数组空间}4-2铁路进行列车调度时,常把站台设计成栈式结构的站台，如右图所示。试问：(1)设有编号为1,2,3,4,5,6的六辆列车,顺序开入栈式结构的站台,则可能的出栈序列有多少种?(2)若进站的六辆列车顺序如上所述,那么是否能够得到435612,325641,154623和135426的出站序列,如果不能,说明为什么不能;如果能,说明如何得到(即写出进栈或出栈的序列)。【解答】(1)可能的不同出栈序列有种。(2)不能得到435612和154623这样的出栈序列。因为若在4,3,5,6之后再将1,2出栈，则1,2必须一直在栈中，此时1先进栈，2后进栈，2应压在1上面，不可能1先于2出栈。154623也是这种情况。出栈序列325641和135426可以得到。356224444111111113323232532532563256432564153441222261113135135413542135421354264-3试证明：若借助栈可由输入序列1,2,3,…,n得到一个输出序列p1,p2,p3,…,pn(它是输入序列的某一种排列)，则在输出序列中不可能出现以下情况，即存在ijk，使得pjpk71pi。(提示：用反证法)【解答】充分性：由jk，pjpk，则pj必须在pk入栈之前就出栈；而ij，pjpi，则意味着pi必须先于pj进栈且pj必须先于pi出栈；此外，ik，则表明pk必须在pi之后出栈，这与pjpkpi相矛盾（因为这意味着pj必须在pk之前和pi之后离开，但pi又出现在pk之后）。下面详细解释一下。借助栈由输入序列1,2,3,…,n，可得到输出序列p1,p2,p3,…,pn，如果存在下标i,j,k，满足ijk，那么在输出序列中，可能出现如下5种情况：①i进栈，i出栈，j进栈，j出栈，k进栈，k出栈。此时具有最小值的排在最前面pi位置，具有中间值的排在其后pj位置，具有最大值的排在pk位置，有pipjpk,不可能出现pjpkpi的情形；②i进栈，i出栈，j进栈，k进栈，k出栈，j出栈。此时具有最小值的排在最前面pi位置，具有最大值的排在pj位置，具有中间值的排在最后pk位置，有pipkpj,不可能出现pjpkpi的情形；③i进栈，j进栈，j出栈，i出栈，k进栈，k出栈。此时具有中间值的排在最前面pi位置，具有最小值的排在其后pj位置，有pjpipk,不可能出现pjpkpi的情形；④i进栈，j进栈，j出栈，k进栈，k出栈，i出栈。此时具有中间值的排在最前面pi位置，具有最大值的排在其后pj位置，具有最小值的排在pk位置，有pkpipj,也不可能出现pjpkpi的情形；⑤i进栈，j进栈，k进栈，k出栈，j出栈，i出栈。此时具有最大值的排在最前面pi位置，具有中间值的排在其后pj位置，具有最小值的排在pk位置，有pkpjpi,也不可能出现pjpkpi的情形；4-4将编号为0和1的两个栈存放于一个数组空间V[m]中，栈底分别处于数组的两端。当第0号栈的栈顶指针top[0]等于-1时该栈为空，当第1号栈的栈顶指针top[1]等于m时该栈为空。两个栈均从两端向中间增长。当向第0号栈插入一个新元素时，使top[0]增1得到新的栈顶位置，当向第1号栈插入一个新元素时，使top[1]减1得到新的栈顶位置。当top[0]+1==top[1]时或top[0]==top[1]-1时，栈空间满，此时不能再向任一栈加入新的元素。试定义这种双栈(DoubleStack)结构的类定义，并实现判栈空、判栈满、插入、删除算法。【解答】双栈的类定义如下：#includeassert.htemplateclassTypeclassDblStack{//双栈的类定义private:inttop[2],bot[2];//双栈的栈顶指针和栈底指针Type*elements;//栈数组intm;//栈最大可容纳元素个数public:DblStack(intsz=10);//初始化双栈,总体积m的默认值为10~DblStack(){delete[]elements;}//析构函数voidDblPush(constType&x,inti);//把x插入到栈i的栈顶intDblPop(inti);//退掉位于栈i栈顶的元素0m-1bot[0]top[0]top[1]bot[1]72Type*DblGetTop(inti);//返回栈i栈顶元素的值intIsEmpty(inti)const{returntop[i]==bot[i];}//判栈i空否,空返回1,否则返回0intIsFull()const{returntop[0]+1==top[1];}//判栈满否,满则返回1,否则返回0voidMakeEmpty(inti);//清空栈i的内容}templateclassTypeDblStackType::DblStack(intsz):m(sz),top[0](-1),bot[0](-1),top[1](sz),bot[1](sz){//建立一个最大尺寸为sz的空栈,若分配不成功则错误处理。elements=newType[m];//创建栈的数组空间assert(elements!=NULL);//断言:动态存储分配成功与否}templateclassTypevoidDblStackType::DblPush(constType&x,inti){//如果IsFull()，则报错；否则把x插入到栈i的栈顶assert(!IsFull());//断言:栈满则出错处理，停止执行if(i==0)elements[++top[0]]=x;//栈0情形：栈顶指针先加1,然后按此地址进栈elseelements[--top[1]]=x;//栈1情形：栈顶指针先减1,然后按此地址进栈}templateclassTypeintDblStackType::DblPop(inti){//如果IsEmpty(i)，则不执行退栈，返回0；否则退掉位于栈i栈顶的元素，返回1if(IsEmpty(i))return0;//判栈空否,若栈空则函数返回0if(i==0)top[0]--;//栈0情形：栈顶指针减1elsetop[1]++;//栈1情形：栈顶指针加1return1;}templateclassTypeType*DblStackType::DblGetTop(inti){//若栈不空则函数返回该栈栈顶元素的地址。if(IsEmpty(inti))returnNULL;//判栈i空否,若栈空则函数返回空指针return&elements[top[i]];//返回栈顶元素的值}templateclassTypevoidMakeEmpty(inti){if(i==0)top[0]=bot[0]=-1;elsetop[1]=bot[1]=m;}4-5写出下列中缀表达式的后缀形式：(1)A*B*C(2)-A+B-C+D(3)A*-B+C(4)(A+B)*D+E/(F+A*D)+C(5)A&&B||!(EF)/*注：按C++的优先级*/(6)!(A&&!((BC)||(CD)))||(CE)73【解答】(1)AB*C*(2)A-B+C-D+(3)AB-*C+(4)AB+D*EFAD*+/+C+(5)AB&&EF!||(6)ABCCD||!&&!CE||4-6根据课文中给出的优先级，回答以下问题：(1)在函数postfix中，如果表达式e含有n个运算符和分界符，问栈中最多可存入多少个元素？(2)如果表达式e含有n个运算符，且括号嵌套的最大深度为6层，问栈中最多可存入多少个元素？【解答】(1)在函数postfix中，如果表达式e含有n个运算符和分界符，则可能的运算对象有n+1个。因此在利用后缀表达式求值时所用到的运算对象栈中最多可存入n+1个元素。(2)同上。4-7设表达式的中缀表示为a*x-b/x↑2，试利用栈将它改为后缀表示ax*bx2↑/-。写出转换过程中栈的变化。【解答】若设当前扫描到的运算符ch的优先级为icp(ch)，该运算符进栈后的优先级为isp(ch)，则可规定各个算术运算符的优先级如下表所示。运算符;(^*,/,%+,-)isp017538icp086421isp也叫做栈内(inst