第4章 栈与队列

第四章栈与队列,栈和队列是两种重要的数据结构，也是两种典型的抽象数据类型，应用非常广泛。从逻辑结构上看，栈和队列都属于线性结构，它们与线性表的主要区别在于它们的操作。栈和队列上的插入、删除操作是受某种特殊限制的。因此，栈和队列也称作操作受限的表，或者限制存取点的表。,4.1栈及其抽象数据类型4.1.1基本概念,栈是一种特殊的线性表，它所有插入和删除都限制在表的同一端进行。表中允许进行插入、删除操作的一端叫做栈顶。表的另一端则叫做栈底。当栈中没有元素时，称之为空栈。栈的插入运算通常称为进栈或入栈。栈的删除运算通常称为退栈或出栈。栈又称为后进先出表（LastInFirstOut表，简称LIFO表）或下推表。,4.1.2抽象数据类型,ADTStackisoperationsStackcreateEmptyStack(void)创建一个空栈。intisEmptyStack(Stackst)判断栈st是否为空栈。voidpush(Stackst,DataTypex)往栈st的栈顶插入一个值为x的元素。voidpop(Stackst)从栈st的栈顶删除一个元素。DataTypetop(Stackst)获得栈顶元素的值。endADTStack,4.2栈的实现4.2.1顺序表示,栈的元素使用连续的存储区域存放，其类型可定义如下：structSeqStack/顺序栈类型定义intMAXNUM;/栈中最大元素个数intt;/ttop就是栈顶指针，plstack-top-info是栈顶元素。上述表示中，没有引入表头节点。因为对栈而言，无论插入和删除都是在栈顶进行，因此再增加表头不仅浪费空间，而且增加了处理表头的时间。,运算的实现,1.创建空链接栈PLinkStackcreateEmptyStack_link(void)创建一空链接栈，需要申请链接栈结构(structLinkStack)空间，将其中top置为NULL,返回该结构的地址。程序实现2.判断栈是否为空栈intisEmptyStack_link(PLinkStackplstack)判断plstack所指的栈是否为空栈，当plstack所指的栈为空栈时，则返回1，否则返回0。程序实现,3.进栈运算voidpush_link(PLinkStackplstack,DataTypex)往plstack所指的栈中插入（或称压入）一个值为x的元素。首先申请结点空间，然后通过指针修改，将结点插在栈顶。程序实现4.出栈运算voidpop_link(PLinkStackplstack)出栈运算，表示从plstack所指的栈中删除（或称弹出）一个元素。当栈不空时，直接修改栈顶指针，删除结点。程序实现5.取栈顶元素DataTypetop_link(PLinkStackplstack)当plstack所指的栈不空时，取栈顶元素的值，栈保持不变。程序实现,4.3栈的应用4.3.1栈与递归,递归是程序设计中有力的表达方式之一。许多程序设计语言都提供了递归的功能，使许多问题能够采用递归的方式描述，编出的程序简洁、清晰。但是，所有递归程序都不能被计算机理解，它们需要被转换成无递归的指令序列才能执行。那么，编译程序是如何处理这类带有递归调用功能的程序？如果使用了无递归功能的程序设计语言，应该如何设计和实现这类程序呢？本节介绍栈是怎样用来实现递归，以及怎样把一个递归的函数转换成一个等价的非递归的函数。,什么是递归,通常用来说明递归的最简单例子是阶乘的定义，它可以表示成：1若n=0n!=n*(n1)!若n0这种用自身的简单情况来定义自己的方式，称为递归定义。在n阶乘的定义中，当n为0时定义为1，它不再用递归来定义，称为递归定义的出口，简称为递归出口。阶乘的递归计算intfact(intn)intres=n;if(n1)res=res*fact(n1);returnres;函数fact(n)中又调用了函数fact，这种函数自己调用自己的作法称为递归调用。包含直接还是间接递归调用的函数都称为递归函数。,递归函数的执行过程,假设（主）程序中包含一个k=fact(3)语句，该语句的执行过程如图所示。在fact(3)的计算过程中，实际不需要生成3个相同的fact程序，只要一个程序在不同的阶段能够处理(3份)不同数据。根据后进先出的原则，只要保证把最后调用的程序使用的空间，保存在一个栈的栈顶就可以了。,递归函数到非递归函数的转换,设有一个程序sub要调用函数rout(x)，sub本身也可能是一个函数，我们称之为调用函数，而称rout为被调函数。调用函数中使用调用语句rout(a)来引起rout函数的执行，这里a称为实参，x称为形参。一般来说，函数调用的实现可以分解成下列三步来进行：(1)传送调用信息。(2)分配被调函数需要的数据区，并接收传送来的调用信息。(3)把控制转移到被调函数的入口。当被调函数运行结束，需要返回到调用函数时，一般的返回处理也可以分解成下列三步：(1)传送返回信息。(2)释放被调函数的数据区。(3)把控制按返回地址转移到调用函数中去。,在非递归调用的情况下，数据区的分配可以在程序运行前进行，一直到整个程序运行结束才释放，这种分配称为静态分配。静态分配时，比较简单，不需要每次调用都分配/释放。在递归调用的情况下，被调函数的局部量不能分配给固定的某些单元，而必须每调用一次就分配一份，当前程序使用的所有的量（包括形参、局部变量和中间工作单元等），都必须是最近一次递归调用时所分配的数据区中的量。即所谓的动态分配。动态分配通常的处理方法是：在内存中开辟一个存储区域称为运行栈（或简称栈），每次调用时，将动态区指针下推，分配被调函数所需的数据区；在每次返回时，将内存指针上托，释放本次调用所分配的数据区，恢复到上次调用所分配的数据区中；被调函数中变量地址全部采用相对于动态区指针的位移量来表示（称为相对地址）。,数据区的分配,根据上述思想，可以给出阶乘计算的非递归算法。因为只有一处递归调用，返回地址（locate）和返回值(fact)都容易控制，而且局部量(res)与参数(n)关系十分清楚，所以栈中只要保存一个参数n的值就可以了。intnfact(intn)intres;PSeqStackst;/使用顺序存储结构实现的栈st=createEmptyStack_seq();while(n0)push_seq(st,n);n=n1;res=1;while(!isEmptyStack_seq(st)res=res*top_seq(st);pop_seq(st);free(st);return(res);,阶乘的非递归算法,4.3.2迷宫问题,在迷宫中求从入口到出口的所有路径是一个经典的程序设计问题。迷宫可用如图所示的方块来表示，每个元素或为通道（以空白方块表示），或为墙（以带阴影的方块表示）。迷宫问题要求的是：从入口到出口的一个以空白方块构成的(无环)路径。,求解迷宫问题的简单方法是：从入口出发，沿某一方向进行探索，若能走通，则继续向前走；否则沿原路返回，换一方向再进行探索，直到所有可能的通路都探索到为止。这类方法统称回溯法。回溯法求解迷宫问题的框架mazeFrame(void)创建一个（保存探索过程的）空栈；把入口位置压入栈中;while栈不空时取栈顶位置并设置为的当前位置;while当前位置存在试探可能取下一个试探位置;if(下一个位置是出口)打印栈中保存的探索过程然后返回;if(下一个位置是通道)把下一个位置进栈并且设置为的当前位置;,算法的框架,数据结构,迷宫可用二维数组mazemn来表示，数组中元素为0的表示通道，为1的表示墙。迷宫的入口处为maze11，出口处为mazem-2n-2，它们的元素值必为0。任意时刻在迷宫中的位置可用元素的行下标和列下标(i,j)来表示。在某一点mazeij时，可能的运动方向有四个。可以建立一个数组direction42给出相对于位置(i,j)的四个方向上，i与j的增量值。若在位置(i,j)，要进入E方向的位置（g,h），则可根据由该增量值表来修改(i,j)的坐标，g=i+direction00;h=j+direction01;,为避免走到已经探索过的位置，凡是已经探索过的位置都应该做上标记。可使用非0、1的2标记。为了记录探索路径中当前位置以及在该位置上使用方向，需要使用栈来保存这些信息。栈用顺序存储结构实现，栈中的元素类型DataType说明如下：typedefstructintx,y,d;DataType;,算法的实现,求迷宫中一条路径的算法，可以从入口开始，对每个“当前位置”都从E方向（东方向）试起，若不能通过，则顺时针试S方向、W方向、N方向。当选定一个可通的方向，即找到“下一个位置”后，要把当前所在的位置纳入到探索路径中，并将当前所在的位置以及所选的方向记录下来，以便往下走不通时可顺原路一步步地退回来，每退一步以后接着试在该点上尚未试过的方向，从“下一个位置”继续探索，如此重复直至到达出口。程序实现：voidmazePath(int*maze,int*direction,intx1,inty1,intx2,inty2,intM,intN),4.3.3表达式计算,栈可以用于表达式计算。为了讨论的方便，在不影响问题实质的情况下，对表达式做如下简化：(1)假定所有运算分量都是整数；(2)所有运算符都是整数的二元操作，且都用一个字符表示。例如31(5-22)+70。这类表达式中所有运算符都出现在它的两个运算分量之间，所以称为中缀表达式。为了简化算法，处理系统通常先把中缀表达式转换成另一种等价形式：31522-70+，这种形式称为后缀表达式。后缀表达式里不再需要有括号，每个运算符都出现在它的两个运算分量后面。其运算顺序相当于：（31（522-）*）70+,中缀表达式到后缀表达式的转换,把中缀表达式转换为后缀表达式是使用栈的一个典型例子。实现转换的基本思想是：顺序扫描中缀表达式，当读入一个运算分量时就立即输出；而在读入一个操作符时,首先把它放进一个运算符栈，一直到这个运算符的两个运算分量都读到后，才能将它输出。由于操作符“*”、“/”的优先级高于“+”、“-”的优先级，因此当栈顶为加减运算符，而读入的是乘除运算符，应该先将乘除运算符保存在栈中，等乘除运算符的两个分量都读出后，再从栈中输出乘除运算符，然后输出加减运算符。当扫描到一个左括号时立即将它入栈（括号的优先级被视为最低），继续扫描直到出现右括号时，才将栈中这对括号间的操作符逐一弹出并输出，最后弹出左括号。当处理到达输入串末尾时，将栈中的操作符全部弹出并输出。例如：5(27+37)+22转化为后缀表达式为：52737+22+,举例：31*(5-22)+70转换为：31522-*70+31*(5-22)+70*(5-22)+7031(5-22)+70*315-22)+70(*31-22)+70(*31522)+70-(*315)+70-(*31522+70*31522-70+31522-*+31522-*7031522-*70+,转换举例,后缀表达式的求值,后缀表达式的主要优点是可以写出非常简单的求值过程。使用一个存放运算分量的栈，求值过程顺序扫描后缀表达式，每次遇到运算分量便将它推入栈中；遇到运算符时，就从栈中弹出两个整数(运算分量)进行计算，而后再把结果推入栈中。这样，到扫描结束时，留在栈顶的整数就是所求表达式的值。,31522-*70+522-*70+3122-*70+531-*70+22531*70+-17315-22=-17放入栈70+-52731*(-17)=-527放入栈+70-527-457-527+70=-457放入栈-457计算结束,4.4队列及其抽象数据类型4.4.1基本概念,队列是一种只允许在表的一端进行插入操作，而在另一端进行删除操作的线性表。允许进行删除的一端叫队头，允许进行插入的一端叫队尾。当队列中没有任何元素时，称为空队列。队列的插入操作通常称为进队列或入队列，队列的删除操作通常称为退队列或出队列。队列也称作先进先出表(FirstInFirstOut表，简称FIFO表）,4.4.2抽象数据类型,ADTQueueisoperationsQueuecreateEmptyQueue(void)创建一个空队列。intisEmptyQueue(Queuequ)判队列qu是否为空队列。voidenQueue(Queuequ,DataTypex)往队列qu尾部插入一个值为x的元素。voiddeQueue(Queuequ)从队列qu头部删除一个元素。DataTypefrontQueue(Queuequ)求队列qu头部元素的值。endADTQueue,4.5队列的实现4.5.1顺序表示,存储结构：用顺序存储表示队列时，要分配一块连续的存储区域来存放队列里的元素，并用两个变量分别指示当前对对头和队尾的位置。为了算法设计上的方便，我们约定：队头指针指出实际队头元素所在的位置，而队尾指针指出实际队尾元素所在位置的下一个位置。structSeqQueue/顺序队列类型定义intMAXNUM;/队列中最大元素个数intf,r;/f是对头的下标，r是队尾的下标（实际队尾元素的下一个）DataType*q;/存放队列元素的数组;typedefstructSeqQueue*PSeqQueue;/顺序队列类型的指针类型,假设paqu是PSeqQueue类型的变量paqu-f存放即将要被删除的元素的下标；paqu-r存放即将要被插入的元素的下标。paqu-qpaqu-f表示当前队列头部的元素；paqu-qpaqu-r表示当前队列尾部的元素。初始时paqu-f=paqu-r=0。当前队列中元素的个数=paqu-r-paqu-f当paqu-r=paqu-f时，元素的个数为0，即为空队列。,在顺序表示的队列中，同样由于数组是静态结构，而队列是动态结构，也存在队列溢出问题，即当队列满时，再作进队操作，这种现象称为上溢；而当队空时，作删除操作，这种现象称为下溢。这些现象在运算中都要考虑。由于队列中经常要执行插入和删除运算，而每运行一次插入或删除，paqu-r或paqu-f就增加1，使得队列中的元素被删除后，其空间就永远使用不到了。队列的动态变化犹如使整个队列向右移动。当paqu-r=MAXNUM时，再作插入运算就会产生溢出，而实际上这时队列的前端可能还有许多空的（可用的）位置，因此，这种现象称为假溢出。,队列的溢出,解决假溢出通常采用的方法是：把数组paqu-qMAXNUM从逻辑上看成一个环，这种队列也称为环形队列。可以使被删除的节点再被使用（下图右）。当表中已有MAXNUM1个结点时，如果还要插入，paqu-r和paqu-f就会重合，而这与空队列的情形相混。为区分空队列与满队列两种情况的环形队列，一般是牺牲队列中的一个结点，当队列中已有MAXNUM1个结点时就称满，再要插入就发生溢出（下图左）。,假溢出的解决,环形队列基本运算的实现,1.创建一个空队列。PSeqQueuecreateEmptyQueue_seq(intm)创建一个空队。具体实现与顺序表算法类似，需要为队列申请空间，不同之处是需要将对变量f和r均赋值为0。2.判断是否为空队列intisEmptyQueue_seq(PSeqQueuepaqu)判断paqu所指的队列是否为空队列。当paqu-f=paqu-r时，返回1，否则返回0。,3.进队运算voidenQueue_seq(PSeqQueuepaqu,DataTypex)入队运算，当队列不满时，将元素x插入paqu所指队列的队尾。程序实现4.出队列运算voiddeQueue_seq(PSeqQueuepaqu)当队列不空时，删除paqu所指队列的队头元素。程序实现5.取队列头部元素DataTypefrontQueue_seq(PSeqQueuepaqu)当paqu所指的队列不空时，取队列头部元素，队列本身保持不变。程序实现,4.5.2链接表示,存储结构:队列的链接表示就是用一个单链表来表示队列，队列中的每个元素对应链表中的一个结点，结点的结构与单链表中结点的结构一样。为了强调队头和队尾都是队列的属性，这里对队列增加了一层封装，引入LinkQueue结构的定义。这样存储的队列简称链接队列。structNode;typedefstructNode*PNode;structNode/结点结构DataTypeinfo;PNodelink;structLinkQueue/链接队列类型定义PNodef;/头指针PNoder;/尾指针;typedefstructLinkQueue*PLinkQueue;/链接队列类型的指针类型,假设plqu是PLinkQueue类型的变量plqu-f为队列的头指针，指向队列中第一个结点。plqu-r是队列尾指针，指向队列中最后一个结点(注意：这一点与顺序队列不同！)。当plqu-f为NULL时队列为空。,基本运算的实现,1.创建一个空队列PLinkQueuecreateEmptyQueue_link(void)申请队列结构空间，创建一个空队列。程序实现2.判断队列是否为空intisEmptyQueue_link(PLinkQueueplqu)判断plqu所指的队列是否为空队，为空队时，则返回1，否则返回0。程序实现,3.进队列运算voidenQueue_link(PLinkQueueplqu,Datatypex)入队运算，表示往plqu所指的队列中插入一值为x的元素。程序实现4.出队列运算intisEmptyQueue_link(PLinkQueueplqu)判断plqu所指的队列是否为空队，为空队时，则返回1，否则返回0。程序实现5.取队列头部结点的值DatatypefrontQueue_link(PLinkQueueplqu)当plqu所指的队列非空时，取队列头部元素的值，队列保持不变。程序实现,4.6队列的应用农夫过河问题,一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。问题是他面前只有一条小船，船小到只能容下他和一件物品，另外只有农夫能撑船。请问农夫该采取什么方案才能将所有的东西运过河呢？,求解这个问题的最简单的方法是一步一步进行试探，每一步都搜索所有可能的选择，对前一步合适的选择再考虑下一步的各种方案。用计算机实现上述求解的搜索过程可以采用两种不同的策略：一种是广度优先(breadth_first)搜索，另一种是深度优先(depth_first)。广度优先的含义就是在搜索过程中总是首先搜索下面一步的所有可能状态，然后再进一步考虑更后面的各种情况。要实现广度优先搜索，一般都采用队列作为辅助结构。把下一步所有可能达到的状态都列举出来，放在这个队列中，然后顺序取出来分别进行处理，处理过程中把再下一步的状态放在队列里。由于队列的操作遵循先进先出的原则，在这个处理过程中，只有在前一步的所有情况都处理完后，才能开始后面一步各情况的处理。,算法选择,状态的表示,要模拟农夫过河问题，首先需要选择一个对问题中每个角色的位置进行描述的方法。一个很方便的办法是用四位二进制数顺序分别表示农夫、狼、白菜和羊的位置。例如用0表示农夫或者某东西在河的南岸，1表示在河的北岸。因此整数5(其二进制表示为0101)表示农夫和白菜在河的南岸，而狼和羊在北岸。问题的初始状态是整数0(其二进制表示为0000)，问题的终止状态是整数15(其二进制表示为1111)。,确定每个角色位置的函数,用整数location表示上述四位二进制描述的状态，下面的四个函数从上述状态中得到每个角色所在位置的代码。函数返回值为真表示所考察的人或物在河的北岸，否则在南岸。intfarmer(intlocation)/判定农夫的位置return(0!=(location,判断状态是否安全的函数,还应该分析问题中所有角色的各种可能位置构成的状态，确定其中哪些是安全的哪些是不安全的。根据原题的描述知道，单独留下白菜和羊，或单独留下狼和羊在某一岸的状态是不安全的。由此可以编一个函数，通过位置分布的代码来判断状态是否安全。intsafe(intlocation)/安全状态的判断函数,若状态安全则返回true/羊吃白菜if(goat(location)=cabbage(location)/其他状态是安全的,完成了上面的准备工作，现在的问题变成：从初始状态二进制0000(全部在河的南岸)出发，寻找一种全部由安全状态构成的状态序列，它以二进制1111(全部到达河的北岸)为最终目标，并且在序列中的每一个状态都可以从前一状态通过农夫（可以带一样东西）划船过河的动作到达。为避免不必要的重复，在序列中不应该出现重复的状态。,问题的描述,主要数据结构的设计,为了实现广度优先搜索，算法中需要使用一个整数队列moveTo，它的每个元素表示一个可安全到达的中间状态。另外还需要一个数据结构记录已被访问过的各个状态，以及已被发现的能够到达当前这个状态的前驱状态。由于在这个问题的解决过程中需要列举的所有状态(二进制00001111)一共16种，所以可以构造一