数据结构与算法-第三章-清华大学出版社-赵玉兰

第3章栈和队列3.1栈3.2队列3.3栈与队列的应用3.1栈——ADT栈栈（Stack）只允许在表的一端进行插入和删除的线性表允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom）不含元素的栈称为空栈插入：进栈，入栈删除：出栈，退栈特点后进先出（LIFO）先进后出（FILO）3.1栈——ADT栈问题有三个元素按a1,a2,a3的次序依次进栈，其出栈次序有几种可能？出栈次序：a1，a2，a3

a1，a3，a2

a2，a1，a3

a2，a3，a1

a3，a2，a1注意：栈只是对表插入和删除操作的位置进行了限制，并没有限定插入和删除操作进行的时间。3.1栈——ADT栈栈的抽象数据类型ADTStack{

Data数据项列表top：栈顶位置

OperationsConstructorProcess：创建一个空栈IsEmptyProcess：判断栈是否为空Output：如果栈为空，则返回true，否则返回falseGetTopProcess：取栈顶元素Output：返回栈顶元素3.1栈——ADT栈LengthProcess：求栈中元素个数Output：返回栈中元素的个数PushInput：要添加的数据元素Process：向栈中添加元素x，即进栈PopProcess：删除栈顶元素，即出栈Output：返回栈顶元素ClearProcess：删除栈中所有元素并置新的栈顶}//Stack3.1栈——栈的实现顺序栈顺序栈的定义如何改造数组实现栈的顺序存储？

0123456②附设指针top指示栈顶元素在数组中的位置。

top①确定用数组的哪一端表示栈底。a1a2a33.1栈——栈的实现顺序栈的基本操作出栈：先出栈top再减1进栈：top先加1再进栈栈空：top==-1

012345678a1topa2topa3top栈满：top==MaxStackSize-1toptop3.1栈——栈的实现constintMaxStackSize=50;//栈中能容纳最大元素个数classSeqStack{DataTypeStackList[MaxStackSize];inttop;public:Stack();//构造函数，初始化topboolIsEmpty();//判断栈的状态是否为空boolIsFull();DataTypeGetTop();//取栈顶元素voidPush(constDataTypex);//入栈DataTypePop();//出栈voidClear();//栈清空};//SeqStack3.1栈——栈的实现顺序栈的操作的实现构造函数，初始化一个空栈Stack(){StackList=newDataType[MaxStackSize];top=-1;}//Stack3.1栈——栈的实现判断栈是否为空boolIsEmpty(){if(top==-1)returntrue;elsereturnfalse;}//IsEmpty3.1栈——栈的实现判断栈是否已满

boolIsFull(){if(top==MaxStackSize-1)returntrue;elsereturnfalse;}//IsFull3.1栈——栈的实现取栈顶元素

DataTypeGetTop(){if(IsEmpty()){cout<<”栈空！”<<endl;returnnulldata;}returnStackList[top];}3.1栈——栈的实现向栈顶压入元素

voidPush(DataTypex){if(IsFull()){cout<<”栈满！”<<endl;elseStackList[++top]=x;}//Push3.1栈——栈的实现删除栈顶元素

DataTypePop(){if(IsEmpty()){cout<<”栈空！”<<endl;returnnulldata;}returnStackList[top--];}//Pop3.1栈——栈的实现清空栈

voidClear(){top=-1;}//Cleartop=-1012341001234压入10top=0102501234压入25top=110255001234压入50top=2102501234弹出50top=11001234弹出25top=0图3.2出栈和入栈操作以及栈顶的变化3.1栈——栈的实现链式栈（LinkedStack）链式栈（链栈）链式存储的栈用单链表来实现链栈，因此其结点结构与单链表的结构相同链式栈无栈满问题，空间可扩充链式栈的栈顶在链头top图3.3链栈a1a2a3a4

3.1栈——栈的实现链式栈类的定义classStackNode{DataTypedata; //结点数据 StackNode*next; //结点链指针 public:friendclassLinkStack；StackNode(DataTyped=nulldata){data=d;next=NULL;}};//StackNodeclassLinkStack{StackNode*top;//栈顶指针public:LinkStack(){top=newStackNode();top->next=NULL;}//创建头结点voidPush(DataTypedata);3.1栈——栈的实现DataTypePop();DataTypeGetTop();voidClear(){top->next=NULL;}boolIsEmpty(){returntop->next==NULL;}};//LinkStack3.1栈——栈的实现类中操作算法的描述入栈操作

voidPush(DataTypeitem){p=newStackNode(item);p->next=top->next;top->next=p;}//Push3.1栈——栈的实现出栈操作DataTypepop(){if(top->next!=NULL){p=top->next;retvalue=p->data; //暂存栈顶数据top->next=p->next;//修改栈顶指针deletep;//释放，返回数据returnretvalue;} else{//栈空的情况cout<<”thestackisempty!”<<endl;returnnulldata;}}//Pop3.1栈——栈的实现取栈顶元素操作

DataTypeGetTop(){if(top->next!=NULL)returntop->next->data;else{//栈空的情况cout<<”thestackisempty!”<<endl;returnnulldata;}}//GetTop3.1栈——栈的实现顺序栈和链栈的比较时间复杂度：相同，都是常数时间O(1)空间性能：顺序栈：有元素个数的限制和空间浪费的问题。链栈：没有栈满的问题，只有当内存没有可用空间时才会出现栈满，但是每个元素都需要一个指针域，从而产生了结构性开销。定义顺序栈时，应该知道所需的最大栈长度。如果事先无法预知栈的最大长度，可以采用链式栈。3.1栈——栈与递归递归是在计算机科学和数学中一种解决问题的极其重要的方法。在数据结构中，可以用它来设计简单、易于理解的算法，特别是在一些具有递归定义的结构上设计算法。3.1栈——栈与递归递归的概念递归子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己递归是一种描述问题和解决问题的基本方法递归的基本思想问题分解：把一个不能或不好解决的大问题转化为一个或几个同类型的小问题，再把这些小问题进一步分解成更小的小问题，直至每个小问题都可以直接解决。3.1栈——栈与递归描述问题例如，求阶乘计算阶乘的递归算法

intfact(intw){

if(w==0)return(1);

elset=fact(w-1);returnw*t;}3.1栈——栈与递归例如，计算斐波那契数列计算斐波那契数列的递归算法

longFib(intn){

if(n==0||n==1)returnn;

elsereturnFib(n-1)+Fib(n-2);}3.1栈——栈与递归解决问题汉诺塔问题迷宫问题皇后问题背包问题3.1栈——栈与递归递归算法的设计递归三要素定义出口，即定义一个最小规模的问题，并给出其解；把一个大的问题划分成同类型的规模较小的子问题；把子问题的解合成为原问题的解。递归的实现建立递归工作栈3.1栈——栈与递归汉诺塔（TowerofHanoi）问题汉诺塔问题来自一个古老的传说：在世界刚被创建的时候有一座钻石宝塔（塔A），其上有64个金盘。所有盘子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两座钻石宝塔（塔B和塔C）。从世界创始之日起，婆罗门的牧师们就一直在试图把塔A上的盘子移动到塔C上去，其间借助于塔B的帮助。由于盘子非常重，因此，每次只能移动一个盘子。另外，任何时候都不能把一个盘子放在比它小的盘子上面。按照这个传说，当牧师们完成他们的任务之后，世界末日也就到了。需要移动的次数为264-13.1栈——栈与递归汉诺塔解决方法n=1时，直接把圆盘从塔A移到塔C；n>1时，先把塔A上的n-1个圆盘移到塔B，然后将n号盘从塔A移到塔C，再将n-1个圆盘从塔B移到塔C。即把求解n个圆盘的Hanoi问题转化为求解n-1个圆盘的Hanoi问题，依次类推，直至转化成只有一个圆盘的Hanoi问题。3.1栈——栈与递归3.1栈——栈与递归解决汉诺塔问题的算法

main(){intn;cout<<"Inputnumberofdisks”;cin>>n;hanoi(n,'A','B','C');}voidhanoi(intn,charx,chary,charz){if(n==1)move(1,x,z);else{hanoi(n-1,x,z,y);move(n,x,z);hanoi(n-1,y,x,z);}}3.1栈——栈与递归递归过程和运行时栈递归函数的运行轨迹描述方法1）写出函数当前调用层执行的各语句，并用箭头表示语句的执行次序；2）对函数的每个递归调用，写出相应的函数调用，从调用处画一条箭头指向被调用函数入口，表示调用路线，从被调用函数末尾处画一条箭头指向调用语句的下面，表示返回路线；3）在返回路线上标出本层调用所得的函数值。3.1栈——栈与递归n=3时汉诺塔递归算法的运行轨迹Hanoi(3,A,B,C）Move(A,3,C)Hanoi(2,A,C,B）Hanoi(2,A,C,B）Hanoi(3,A,B,C）Hanoi(1,A,B,C）递归第三层递归第二层递归第一层Move(A,1,C)Hanoi(1,C,A,B）Move(C,1,B)Hanoi(1,B,C,A）Move(B,1,A)Hanoi(1,A,B,C）Move(A,1,C)Hanoi(1,A,B,C）Move(A,2,B)Hanoi(1,C,A,B）Hanoi(2,B,A,C）Hanoi(1,B,C,A）Move(B,2,C)Hanoi(1,A,B,C）Hanoi(2,B,A,C）(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)(12)(13)(14)3.1栈——栈与递归递归函数的内部执行过程当一个函数在运行期间调用另一个函数时，在运行被调用函数之前，系统需要将实参和返回值地址等数据传递给被调函数，当函数调用时，这些数据与局部变量一起构成一条“工作记录”，被压入系统提供的栈（运行时栈）。当被调函数返回时，按照返回地址执行调用函数中下一条指令，同时释放栈中相应的工作记录。3.1栈——栈与递归主程序Callproc1rproc1proc2proc3sCallproc2tCallproc3rst系统运行时栈局部变量返回地址实际参数工作记录3.1栈——栈与递归递归调用的内部执行过程运行开始时，首先为递归调用建立一个系统运行时栈；每次执行递归调用之前，把递归函数的值参和局部变量的当前值以及调用后的返回地址等组成的工作记录压入栈中；每次递归调用结束后，将栈顶元素出栈，使相应的值参和局部变量恢复为调用前的值，然后转向返回地址指定的位置继续执行。3.1栈——栈与递归n=3时汉诺塔递归算法的部分执行过程

main(){hanoi(3,'A','B','C');}voidhanoi(intn,charx,chary,charz){if(n==1)move(1,x,z);else{hanoi(n-1,x,z,y);move(n,x,z);hanoi(n-1,y,x,z);}}0123456789ABC321返回地址zyxn3ABC01CAB82ACB61ABC6123.1栈——栈与递归递归总结递归是重要的设计和编程工具，使许多算法变得简单，易于设计和实现。

－－－－优点递归使算法的时间复杂度和空间复杂度同时增大，有时会导致效率急剧恶化，或者溢出系统栈。

－－－－缺点使用递归时应该权衡效率和设计的关系。在有足够的空间并且时间要求不高的情况下可以使用递归。3.2队列——ADT定义定义队列（Queue）是只允许在表的一端进行删除，而在另一端进行插入的线性表。允许删除的一端叫做队头（front）允许插入的一端叫做队尾（rear）特点先进先出（FIFO，FirstInFirstOut）a1a2a3……………….an

入队出队frontrear3.2队列——ADT定义ADT队列的定义ADTQueue{Data数据项列表front：队列中第一个元素的位置rear：队列中最后一个元素的位置OperationsConstructorProcess：初始化队首和队尾IsEmptyProcess：判断是否为空队列Output：若队列空，返回true，否则返回false3.2队列——ADT定义LengthProcess：求队列中元素个数Output：返回队列的元素个数FrontProcess：取出队头元素Output：返回队头元素EnterInput：要进入队列的元素Process：在队尾插入新的元素LeaveProcess：删除队头元素Output：返回队头元素ClearQueueProcess：删除队列中所有元素并设置初始状态}//Queue3.2队列——队列的实现顺序队列顺序队列的定义constintMaxQSize=50;classSeqQueue{intfront,rear;DataTypeQueueList[MaxQSize];public:SeqQueue();//构造函数,初始化数据成员voidEnter(DataTypeitem);DataTypeLeave();voidClear();DataTypeFront();intLength();boolIsEmpty();boolIsFull();};//SeqQueue3.2队列——队列的实现顺序队列的进队和出队设两个指针front和rear（初始front＝rear＝0）front指向队头元素，出队时先取出，再front+1rear指向队尾元素的下一个位置，进队时先将新元素加入，再rear+1队空条件：front==rear，此时不能出队队满条件：rear==MaxQSize，此时不能进队3.2队列——队列的实现存在问题rear==MaxQSize时，再有元素进队发生溢出当front==0——真溢出当front0——假溢出解决假溢出的方案固定队头，出队时，剩余元素均向前移动固定队尾，入队时，剩余元素均向前移动循环队列：把队列设想成环形，让0接在

MaxQSize-1后——更好3.2队列——队列的实现循环队列也是队列的顺序存储结构实现利用“模”运算入队QueueList[rear]=item;rear=(rear+1)%MaxQSize;出队item=QueueList[front];front=(front+1)%MaxQSize;01frontrear…...…...MaxQSize-13.2队列——队列的实现仍然存在问题如何判断队列是“空”还是“满”？队空：front==rear队满：front==rear3.2队列——队列的实现三种处理方法给队列设一个标志位以区别队列是空还是满给队列增加一个统计元素个数的变量count，当count=MaxQSize时队满；count=0时队空少用一个变量，约定rear+1等于front（从后面赶上队头指针）为队满的情况队满条件：(rear+1)%MaxQSize==front队空条件：

front

==rear3.2队列——队列的实现循环队列类的操作算法描述构造函数，初始化一个空队列

SeqQueue(){front=rear=0;}//SeqQueue入队操作voidEnter(DataTypeitem){if((rear+1)%MaxQSize==front)//判断是否队满cout<<”队列已满，不能入队！”<<endl;elseQueueList[rear]=item;rear=(rear+1)%MaxQSize;}//Enter3.2队列——队列的实现出队操作DataTypeLeave(){if(front==rear){//判断是否队空cout<<”队列已空，不能出队”<<endl;returnnulldata;}e=QueueList[front]);front=(front+1)%MaxQSize;returne;}//Leave清空队列voidClearQueue(){rear=front;}//ClearQueue3.2队列——队列的实现判断队列是否为空boolIsEmpty(){if(rear==front)returntrue;elsereturnfalse;}//IsEmpty判断队列是否已满boolIsFull(){if((rear+1)%MaxQSize==front)returntrue;elsereturnfalse;}//IsFull3.2队列——队列的实现链队列队列的链式存储结构用单链表来实现链队列设置一个队头指针front：在链头设置一个队尾指针rear：在链尾链队列无队满问题队空条件：front->next==NULLfront图3.13链队列a1a2a3a4

rear3.2队列——队列的实现链队列描述classQNode{//链队结点的类DataTypedata;QNode*next;public:QNode(DataTypeitem=nulldata){data=item;next=NULL;}friendclassLinkQueue;};//QNode3.2队列——队列的实现classLinkQueue{QNnode*front,*rear;public:LinkQueue(){rear=front=newQNode();}voidEnter(DataTypeitem);DataTypeLeave(); DataTypeFront(); voidClear(){front->next=rear->next=NULL;}boolIsEmpty(){returnfront–>next==NULL;} };//LinkQueue3.2队列——队列的实现链队列基本操作的算法描述入队操作voidEnter(DataTypeitem){rear->next=newQNode(item);rear=rear->next;}//Enter3.2队列——队列的实现出队操作DataTypeLeave(){if(!IsEmpty()){//判队不空p=front->next; DataTyperetvalue=p->data; //保存队头的值front->next=p->next;deletep;if(front->next==NULL)//删除队列中唯一结点后，重新设置rearrear=front;returnretvalue; }else{cout<<”队列空!”<<endl;returnnulldata;}}//Leave3.2队列——队列的实现取队头元素DataTypeFront(){if(!IsEmpty()) returnfront->next->data; else{cout<<”队列空，无队头元素！”<<endl;returnnulldata;}}//Front3.2队列——队列的实现优先级队列主要有插入和删除操作插入操作：与普通队列相同删除操作：优先级高的元素先被删除，同一优先级的元素按其到达先后进行处理实际应用中经常用到，例如操作系统中的进程优先级队列优先级队列的ADT与普通队列的ADT相似，只是删除操作与普通队列不同3.3栈与队列的应用栈的应用应用1：数制转换问题将十进制数N转换为r进制的数转换方法：辗转相除法例，N=3467，r=8（1348）10=（2504）8

NNdiv8Nmod8

13481684

168210

2125

202计算顺序输出顺序3.3栈与队列的应用所转换的8进制数按低位到高位的顺序产生的，而通常的输出是从高位到低位的，恰好与计算过程相反，因此转换过程中每得到一位8进制数则进栈保存，转换完毕后依次出栈则正好是转换结果。算法思想当N>0时重复（1），（2）（1）若N≠0，则将N%r压入栈s中，执行（2）；若N＝0，将栈s的内容依次出栈，算法结束。（2）用N/r代替N3.3栈与队列的应用算法描述voidconversion(intN，intr){SeqStacks;intx;while(N){s.Push(N%r);N=N/r;}while(!s.IsEmpty()){x=s.Pop();cout<<x;}//while}//conversion3.3栈与队列的应用应用2：表达式求值表达式表达式由操作数（operand）、运算符（operator）和分界符（delimiter）组成操作数：变量或常数运算符：算术运算符、关系运算符、逻辑运算符分界符：括号表达式的表示方法前缀表达式中缀表达式后缀表达式3.3栈与队列的应用后缀表达式（逆波兰式）求值后缀表达式不含括号运算符放在两个操作数后面例中缀表达式2+(3*8–4)/5后缀表达式238*4-5/+所有的求值计算皆按运算符出现的顺序，严格从左向右进行比中缀表达式的计算简单3.3栈与队列的应用算法思想设一个栈；顺序扫描后缀表达式的每一项，根据其类型做如下处理：如果该项是操作数，则将其压入栈顶；如果该项是运算符<op>，则连续从栈顶退出两个操作数x和y，形成运算指令x<op>y，并将结果重新压入栈顶。表达式所有项扫描并处理完后（以符号“=”为结束），栈顶存放的就是计算结果。3.3栈与队列的应用栈输入操作序列

ABCD+EF/PushABCDCDPushPushPop,Pop,PushPushPop,Pop,PushB(CD)Pop,Pop,PushA+B(CD)EFE/FPushPushPop,Pop,PushPop,Pop,PushA+B(C-D)E/F3.3栈与队列的应用中缀表达式的计算中缀表达式的计算次序根据运算符优先级由高到低的顺序进行运算有括号出现时先算括号内的，后算括号外的，多层括号，由内向外进行乘方连续出现时先算最右面的计算方法1按中缀表达式的顺序计算（本书）计算方法2先将中缀表达式转换为后缀表达式再进行后缀表达式求值3.3栈与队列的应用计算方法1根据上述三条运算规则，在运算的每一步中，对任意相继出现的运算符1和2，都要比较优先关系运算符间的优先关系见下表

21

*/+－()#*/+－（）#>>>><>>>>>><>><<>><>><<>><>><<<<<=>>>>>><<<<<=3.3栈与队列的应用算法思想设定两栈：操作数栈OPND，运算符栈OPTR栈初始化：设操作数栈OPND为空；运算符栈OPTR的栈底元素为表达式起始符‘#’；依次读入字符：是操作数则入OPND栈，是运算符则要判断（设OPTR的栈顶元素为1，当前读入的运算符为2）：

1）if1<2，将2压入OPTR栈；

2）if1==2且不为‘#’，退括号（弹出左括号）；

3）if1>2，则退栈、计算，结果压入OPND栈；重复，直至读入字符和OPTR的栈顶元素均为‘#’，此时OPND的栈顶即为计算结果3.3栈与队列的应用OPTROPNDINPUTOPERATE3*(7-2)#Push(opnd,’3’)

#*(7-2)#3#Push(optr,’*’)#,*3(7-2)#Push(optr,’(’)#,*,(37-2)#Push(opnd,’7’)#,*,(3,7-2)#Push(optr,’-’)#,*,(,-3,72)#Push(opnd,’2’)#,*,(,-3,7,2)#Operate(7-2)#,*,(3,5)#Pop(optr)#,*3,5#Operate(3*5)#15#GetTop(opnd)3.3栈与队列的应用算法描述voidEvaluateExpression(OperandType&result){//s1为操作对象栈，s2为运算符栈，OP为运算符集合SeqStacks1,s2;s2.Push(’#’);c=getchar();while((c!=‘#’)&&(s2.GetTop()!=‘#’)){if(!In(c,OP){s1.Push(c);c=getchar();}3.3栈与队列的应用elseswitch(compare(s2.GetTop(),c)){case‘<’:s2.Push(c);c=getchar();break;case‘=’:s2.Pop();c=getchar();break;case‘>’:{temat=s2.Pop();b=s1.Pop();a=s1.Pop();result=Operate(a,temat,b);s1.Push(result);

c=getchar();break;}}//switch}//whileresult=s1.GetTop();}//EvaluateExpression3.3栈与队列的应用计算方法2——将中缀表达式转换成后缀表达式设置一个栈，栈底元素为表达式起始符‘#’；依次读入中缀表达式的每一字符，是操作数则直接输出，是运算符则要判断（设栈顶元素为1，当前读入的运算符为2）：1）if1<2，则2入栈，读入下一字符；2）if1>2，

则退栈，并输出；3）if1==2且不为‘#’，

则退栈，但不输出，若退出的是’(‘则读入下一字符；重复，直至读入字符和栈顶元素均为‘#’，算法结束，此时输出序列即为后缀表达式3.3栈与队列的应用应用3：迷宫求解问题

入口出口3.3栈与队列的应用基本思想从入口出发，沿某一方向向前探索若当前位置“可通”，则纳入路径，继续前进；若当前位置“不可通”，则换方向继续探索;若四周“均无通路”，则沿原路退回到前一位置，换方向继续探索3.3栈与队列的应用迷宫求解问题的递归算法算法中用到的数据结构intMaze[m+2][p+2]：表示迷宫m表示行数，p表示列数第0、m+1行，第0、p+1列是迷宫的围墙Maze[i][j]=1时，表示该位置是墙壁，不能通行Maze[i][j]=0时，表示该位置是通路intmark[m+2][p+2]：标志矩阵初始为0，当某一位置[i][j]走过时，置mark[i][j]=13.3栈与队列的应用offsetsmove[4]：表示方向Structoffsets{inta,b;char*d;}move[q].dmove[q].amove[q].bE(东)01S(南)10W(西)0-1N(北)-10N(北)[i-1,j]W(西)[i,j-1]当前位置[i,j]E(东)[i,j+1]S(南)[i+1,j]3.3栈与队列的应用递归函数intSeekPath(intx,inty){inti,g,h;char*d;if(x==m&&y==p)return1;for(i=0;i<4;i++){g=x+move[i].a;h=y+move[i].b;d=move[i].dir;if(!Maze[g][h]&&!mark[g][h]){mark[g][h]=1;if(SeekPath(g,h)){

cout<<“(“<<g<<“,”<<h<<“),”<<“Direction”<<dir<<“,”;return1;}}}if(x==1&&y==1)