山大《数据结构》讲义03栈和队列

1、第三章 栈和队列内容概述从数据结构角度来看，栈和队列是两种特殊的线性表，其特殊性体现在它们的基本操作是线性表操作的子集，因此它们是限定性的数据结构。从抽象数据类型角度来看，它们是不同于线性表的两类重要的抽象数据类型。由于栈和队列在实际应用中的广泛性和其操作的特殊性，本章从栈和队列的抽象数据类型定义、栈和队列的顺序表示与实现、栈和队列的链式表示与实现、栈和队列的应用等几个方面进行专门讨论。重点与难点重点为栈和队列的运算，循环队列。难点为栈与递归的关系，栈与队列的应用。思考1栈是具有什么特性的线性表？2队列是具有什么特性的线性表？3分析栈与递归的关系。4若已知一个栈的入栈序列是1，2，3，n，其输

2、出序列为p1,p2,p3,pn，若p1=n，则pi=?5设有一个顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素的出栈顺序为s2,s3,s4,s6,s5,s1，则顺序栈的容量至少应为多少？6为什么要循环队列？在循环队列中队列空、满的评定标准是什么？7利用两个栈模拟一个队列的入队、出队、判断队空等运算。第一节栈栈是一种具有“后进先出”特性的线性表。这种特性对其操作有何影响呢？其存储结构相对于一般线性表又会有哪些变化？本节将从栈的定义、抽象类型定义、栈的顺序与链式存储结构等方面入手解答上述问题。1、栈的定义1、栈的定义栈（Stack）又称堆栈，是一种特殊的线性表，可定义为插入

3、、删除和访问只能在某一端进行的线性数据结构。堆栈允许插入、删除和访问的一端称为栈顶（Top），另一端称为栈底（Bottom）。栈顶的第一个元素被称为栈顶元素。不含数据元素的空表称为空栈。向一个栈插入新元素又称为进栈或入栈，它是把该元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称为出栈或退栈，它是把栈顶元素删除掉，使其下面的相邻元素成为新的栈顶元素。堆栈的性质决定它的数据是按“先进后出”的顺序被访问，即最先存储的元素最后被访问、删除，最后存储的元素最先被访问、删除，所以栈也称为“LIFO”（Last_In,First_Out）。栈的模型在日常生活中是普遍存在的，如铁路列车调度系

4、统等，在计算机科学中，栈是一种非常有用的数据结构。实际上，TurboC在将参数传递给函数时，就使用堆栈。我们应该注意到：栈是一种动态的数据结构，也就是说，随着对栈进行插入和删除等不同的操作，其结点个数、内容等将会不断发生变化。假设栈S=(a1,a2,an)，则称a1为栈底元素，an为栈顶元素。栈中元素按a1,a2,an的次序进栈，如图3.1所示。2、栈的抽象类型定义2、栈的抽象类型定义在栈的抽象数据类型定义中，用Stack标识符来表示栈对象类型，操作部分应包括初始化、元素进栈、元素出栈、读取栈顶元素、检查栈是否为空等。下面给出栈的抽象数据类型的具体定义。ADTStack数据对象：D=ai|ai

5、ElemSet,i=1,2,n,n0数据关系：R=|ai-1,aiD,i=2,n约定an端为栈顶，a1端为栈底。基本操作：InitStack(&S)操作结果：构造一个空栈S。Push(&S,e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。StackEmpty(S)初始条件：栈S已存在。操作结果：若S为空栈，则返回TRUE，否则返回FALSE。StackLength(S)初始条件：栈S已存在。操作结果：返回S

6、的元素个数，即栈的长度。StackTraverse(S，visit()初始条件：栈S已存在且非空。操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。DestroyStack(&S)初始条件：栈S已存在。操作结果：栈S被销毁。ADTStack3、顺序栈的数据类型描述3、顺序栈的数据类型描述栈的顺序存储结构，即顺序栈，和线性表的顺序存储结构类似，是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时通过指针top指示栈顶元素在顺序栈中的位置。由于很难估计栈在使用过程

7、中所需要的最大空间的大小，所以通常利用C语言中动态分配的一组连续的存储单元作为顺序栈所需要的存储空间。首先定义一个指针表示存储空间的基地址，且定义一个指针指示栈顶元素的位置，此外还需要定义一个整型变量指示顺序栈当前分配的存储空间大小，即当前顺序栈的最大容量。在应用过程中，当栈的空间不够用而需要继续扩大分配其空间时，通过定义一个整型变量表示栈的动态分配增量。顺序栈所需要的具体数据类型描述如下：#defineMAXLEN100#defineSTACK_INCREASE10/顺序栈存储空间的动态分配增量typedefstructElemType*base;/栈的存储空间的基地址，即栈底指针ElemT

8、ype*top;/栈顶指针intmaxsize;/栈当前分配的存储容量SqStack;其中，maxsize指示栈当前可使用的最大容量；base为栈底指针，在顺序栈中，它始终指向栈底的位置，若base=NULL，则表明栈结构不存在；top为栈顶指针，起初值为栈底指针值，即top=base，这也可作为栈空的标记。栈插入新元素时，将新元素插入到栈顶指针所指向的位置，同时指针top增1，删除栈顶元素时，指针top减1。因此，如图3.2所示，栈顶指针始终指向栈顶元素的下一个位置。4、顺序栈的操作4、顺序栈的操作（顺序栈的生成算法、顺序栈的入栈算法、顺序栈的出栈算法、顺序栈求栈顶元素算法、顺序栈的遍历算法

9、）生成栈S顺序栈的生成算法主要是为其准备所需要的存储空间（这可通过malloc函数动态申请空间来实现），同时为参数S的成员S.base、S.top、S.maxsize赋以相应的值。StatusInitStack(SqStack&S)/构造一个空栈SS.base=(ElemType*)malloc(MAXLEN*sizeof(ElemType);if(!S.base)exit(OVERFLOW);/存储分配失败S.top=S.base;/栈顶指针也指向栈底，意味着栈为空S.maxsize=MAXLEN;returnOK;/InitStack算法3-1顺序栈的生成算法元素e进栈，即插入到栈顶插入栈

10、顶元素前首先检查是否栈满（判断S.top-S.base=S.maxsize是否成立），如果栈满，动态追加存储空间。插入栈顶元素时，在栈顶指针top指示的位置插入元素e，即*S.top=e，然后top加1。本算法的时间复杂度为O(1)。StatusPush(SqStack&S,ElemTypee)/插入元素e为新的栈顶元素if(S.top-S.base=S.maxsize)/栈满，追加存储空间newbase=(ElemType*)realloc(S.base,(S.maxsize+STACK_INCREASE)*sizeof(ElemType);if(!newbase)exit(OVERFLOW

11、);/存储分配失败S.base=newbase;S.top=S.base+S.maxsize;/确定新栈的栈顶指针的位置S.maxsize+=STACK_INCREASE;/栈的最大容量增加*S.top+=e;/插入栈顶元素，且栈顶指针增加returnOK;/Push算法3-2顺序栈的入栈算法删除栈顶元素，并返回删除元素的值删除栈顶元素时，首先检查栈是否为空，如果为空，则返回错误。若栈不为空，则栈顶指针top减1，返回此时top指向的元素的值。本算法的时间复杂度为O(1)。StatusPop(SqStack&S,ElemType&e)/若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK，否

12、则返回ERRORif(S.top=S.base)returnERROR;e=*-S.top;/e返回栈顶元素值，-S.top表示删除栈顶元素returnOK;/Pop算法3-3顺序栈的出栈算法返回栈顶元素的值与删除栈顶元素算法中的返回栈顶元素类似，返回(top1)指向的元素即为栈顶元素的值。本算法的时间复杂度为O(1)。StatusGetTop(SqStackS,ElemType&e)/若栈不空，则用e返回S的栈顶元素，并返回OK，否则返回ERRORif(S.top=S.base)returnERROR;e=*(S.top-1);/e返回栈顶元素值returnOK;/GetTop算法3-4顺序

13、栈求栈顶元素算法栈的遍历遍历栈S时，首先检查栈是否为空，如果为空，则返回错误。若栈不为空，使p指向栈顶，即p=S.top，利用循环操作，p减1后，对p所指向的元素使用visit函数访问，循环的条件为pS.base，即直到遍历完栈底元素为止。该算法的主要操作和影响算法效率的步骤为循环遍历栈的元素，频数和栈的元素个数相同，所以本算法的时间复杂度为O(n)。StatusStackTraverse(SqStackS,Status(*visit)(ElemType)/若栈不空，则使用visit函数遍历栈的元素并返回OK，否则返回ERRORif(S.top=S.base)returnERROR;p=S.t

14、op;/p指向栈顶while(pS.base)visit(*-p);/通过循环对栈的元素遍历returnOK;/StackTraverse算法3-5顺序栈的遍历算法从上述若干对栈操作的实现算法可以看出，由于对栈操作的特殊限制（LIFO），我们主要通过栈顶指针即可完成相应操作，这大大简化了我们考虑问题的思路。现实当中有许多问题可归结为这类操作，实际上，凡是符合LIFO特性的数据操作，我们都应当充分利用栈的优点来实现其简便的操作，从这个角度来看，栈是十分有用的。5、链栈的数据类型描述5、链栈的数据类型描述栈的链式存储结构，即链栈，与线性表的链式存储结构类似，是通过由结点构成的单链表实现的，但每个结

15、点的指针指向其前驱结点（在其之前进栈的结点）。此时，表头指针称为栈顶指针，其指向的结点即为栈顶结点。所需要的具体数据类型描述如下：typedefstructSNodeElemTypedata;structSNode*prior;/prior将指向其前一次入栈的元素SNode,*SLink;当栈插入新元素时，是把新元素插入到栈顶，即把新元素结点的指针指向原来栈顶元素所在的结点，同时，修改栈顶指针指向新元素所在的结点。而当删除栈顶元素时，将栈顶指针指向其前一次入栈的元素，并直接释放被删除结点的空间，如图3.3所示。6、链栈的操作6、链栈的操作（链栈的生成算法、链栈的入栈算法、链栈的出栈算法、链栈求

16、栈顶元素算法、链栈的遍历算法、链栈的清空算法）生成栈S链栈的生成算法主要是构造一个空栈，top指针为空，表示栈为空。StatusInitStack(SLink&top)/构造一个空栈Stop=NULL;returnOK;/InitStack算法3-6链栈的生成算法元素e进栈，即插入到栈顶当元素e进栈时，首先创造栈元素结点，使该元素结点的指针域指向原来的栈顶结点，而栈顶指针则修改为指向该元素结点，使该元素成为新的栈顶结点。本算法的时间复杂度为O(1)。StatusPush(SLink&top,ElemTypee)/插入元素e为新的栈顶元素p=(SLink)malloc(sizeof(SNode)

17、;/申请栈元素的结点空间if(!p)exit(OVERFLOW);p-data=e;/为新结点赋值p-prior=top;/将其插入到原栈顶结点后top=p;/栈顶指针指向该结点returnOK;/Push算法3-7链栈的入栈算法删除栈顶元素，并返回删除元素的值当删除栈顶元素时，首先检查栈是否为空，如果为空，则返回错误。若栈不为空，取出栈顶元素，使栈顶指针指向原栈顶结点的指针域所指向的结点，然后释放被删除结点的空间。本算法的时间复杂度为O(1)。StatusPop(SLink&top,ElemType&e)/若栈不空，则用e返回S的栈顶元素值后删除该结点，并返回OK/否则返回ERRORif(t

18、op=NULL)returnERROR;p=top;e=p-data;/返回栈顶元素值top=top-prior;free(p);/栈顶指针指向新的栈顶结点，释放被删除结点空间returnOK;/Pop算法3-8链栈的出栈算法返回栈顶元素的值首先检查栈是否为空，如果为空，则返回错误。若栈不为空，则直接使用e返回栈顶指针所指向的元素的数据即可。本算法的时间复杂度为O(1)。StatusGetTop(SLinktop,ElemType&e)/若栈不空，则用e返回S的栈顶元素并返回OK，否则返回ERRORif(top=NULL)returnERROR;e=top-data;/返回栈顶元素值retur

19、nOK;/GetTop算法3-9链栈求栈顶元素算法栈的遍历遍历栈S时，首先检查栈是否为空，如果为空，则返回错误。若栈不为空，使p指向栈顶元素，即p=top，通过循环，对p所指向结点的数据域使用visit函数，循环的条件为p不为空，即直到遍历完栈底元素为止。该算法的主要操作和影响算法效率的步骤为循环遍历栈的元素，频数和栈的元素个数相同，所以本算法的时间复杂度为O(n)。StatusStackTraverse(SLinktop,Status(*visit)(ElemType)/若栈不空，则使用visit函数遍历栈的元素并返回OK，否则返回ERRORif(top=NULL)returnERROR;p

20、=top;/p指向栈顶结点while(p)/通过循环对栈的元素遍历visit(p-data);p=p-prior;returnOK;/StackTraverse算法3-10链栈的遍历算法栈的清空本算法与栈的遍历算法思想类似，通过结点的指针域对栈元素结点逐一使用free函数，释放结点。该算法的主要操作和影响算法效率的步骤为通过循环逐一释放栈元素结点的空间，频数和栈的元素个数相同，所以本算法的时间复杂度为O(n)。StatusClearStack(SLink&top)/若栈不空，则通过循环清空栈的元素并返回OK，否则返回ERRORif(top=NULL)returnERROR;while(top)

21、/通过循环逐一释放栈元素结点的空间p=top;top=top-prior;free(p);returnOK;算法3-11链栈的清空算法第二节栈的应用举例由于栈结构所具有的后进先出的特性使它能够完成各种回溯性的操作，所以栈成为了程序设计中有用的工具。本节将讨论栈在数值转换、括号匹配检验、后缀表达式计算、迷宫、递归等方面的典型应用。1、利用栈完成数值转换1、利用栈完成数值转换在计算机实现计算过程中，经常会把十进制数x转化为其他d进制数，其解决方法很多，其中一个简单算法基于下列原理：x=(xdivd)*d+xmodd(其中：div为整除运算，mod为求余运算)例如：(1283)10=(2403)8，

22、其计算过程如下：xxdiv8xmod8128316031602002024202现在编写一个算法，将一个十进制整数转换成一个d进制数（十进制以内如二进制、八进制）。由于上述计算过程是从低位到高位顺序产生d进制数的各个数位，而打印输出时，一般来说应从高位到低位进行，恰好和计算过程相反。因此，若将计算过程中得到的d进制数的各位顺序进栈，则按出栈序列打印输出的即为与输入对应的d进制数，所以此问题可利用栈来解决，具体算法描述为：voidconversion(longnum,intd)/把一个长整型数num转换为一个d进制数输出SqStackS;/定义一个顺序栈InitStack(S);/栈S初始化wh

23、ile(num!=0)/由低位到高位求出d进制整数的每一位并入栈Push(S,num%d);num=num/d;/whilewhile(!StackEmpty(S)/由高位到低位输出d进制数的每一位Pop(S,e);printf(“%d”,e);/while/conversion算法3-12数制转换算法这是利用栈的后进先出特性的最简单的例子。在这个例子中，栈操作的序列是直线式的，即先一味地入栈，然后一味地出栈。也许有的读者会提出疑问：用数组实现不也很简单吗？仔细分析上述算法不难看出，栈的引入简化了程序设计的问题，划分了不同的关注层次，使思考范围缩小了，或者使思路简洁了。而用数组不仅掩盖了问题的

24、本质，还要分散精力去考虑数组下标增减等细节问题。2、利用栈实现后缀表达式计算2、利用栈实现后缀表达式计算在计算机中进行算术表达式的计算是通过栈来实现的。通常书写的算术表达式是由操作数（又叫做运算对象或运算量）和运算符以及改变运算次序的圆括号连接而成的式子。操作数可以是常量、变量和函数，同时还可以是表达式。假设我们有一个简单计算器并想要计算一趟外出购物的花费。简单计算器一般不包括括号，因此不能通过加括号的方法得到正确的答案，需要我们记住中间结果。例如计算表达式6*（5+（2+3）*8）+3）的值时，典型的计算顺序是将2和3相加并存入A1，将8和A1相乘后把结果存入A1，再将5和A1相加并将结果存

25、入A1，然后将A1和3相加并存入A1，最后将6和A1相乘并将最后结果放入A1。我们可以将这种操作顺序书写如下：6523+8*+3+*。这个记法叫做后缀或逆波兰记法，其求值过程正如我们上面所描述的一样。计算这个问题最容易的方法是使用一个栈。当读到一个数时就把它推入栈中；在读到一个运算符时该算符就作用于从该栈弹出的两个数（符号）上，将所得结果再推入栈中。计算过程如下：前四个字符放入栈中，如图3.4(a)。读到一个“+”号，所以3和2从栈中弹出，它们的和5被压入栈中，如图3.4(b)。接着，8进栈，如图3.4(c)。读到一个“*”号，因此8和5弹出，并且5*8=40进栈，如图3.4(d)。接着又读到

26、一个“+”号，因此40和5被弹出，并且5+40=45进栈，如图3.4(e)。现在将3压入栈中，如图3.4(f)。然后“+”使得3和45从栈中弹出，并将45+3=48压入栈中，如图3.4(g)。最后，读到一个“*”号，从栈中弹出48和6，将结果6*48=288压入栈中，如图3.4(h)。计算一个后缀表达式花费的时间是O(n)，因为对输入的每个元素的处理都是由一些栈操作组成从而花费常数时间。该算法的计算是非常简单的，而且具有明显的优点，当一个表达式以后缀记法给出时，没有必要知道任何优先规则就可以完成计算。3、迷宫问题的实现算法3、迷宫问题的实现算法求迷宫中从入口到出口的路径是一个经典的程序设计问题

27、。由于计算机解决迷宫问题时，通常采用的是“穷举求解”的方法，即从入口出发，顺着某一方向向前探索，若能走通，则继续往前走；否则沿原路返回，换一个方向继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路的算法中应用“栈”也就是自然而然的事了。为了在计算机中表示如图3.5所示的迷宫，需要定义一个二维数组Mazemn，m和n分别为图中行和列所在位置，此外用0、1和2分别表示通道、墙和已走过的位置。例如，图中0行1列的位置，即（0,1）为带阴影线的方块，表示墙，在数组中记为Maze01=1；图中1行2列

28、的位置，即（1,2）为空白方块，表示通道，在数组中记为Maze12=0。迷宫问题所求的路径必须是简单路径，即在求得的路径上不能重复出现同一通道方块。在迷宫的探索过程中，我们通过栈记录探索迷宫的路径，栈的每个成员都记录了通道块在路径中的“序号”、通道块在迷宫中的位置以及从该通道块走向下一个通道块的“方向”。其中，迷宫中的位置可通过一个结构体表示，其中用x（行坐标）、y（列坐标）记录路径中通道块的坐标位置；用一组整型数字表示从该通道块走向下一个通道块的“方向”，即1（东）、2（南）、3（西）、4（北）。具体存储结构描述如下：typedefstructintx;/行坐标inty;/列坐标PosTyp

29、e;/迷宫位置的类型typedefstructintnum;/通道块在路径中的“序号”PosTypepos;/通道块在迷宫中的位置intdi;/从此通道块走向下一个通道块的“方向”ElemType;/栈的元素类型下面，我们对与迷宫问题有关的一些假设进行阐述。假设“当前位置”是指在搜索过程中某一时刻在迷宫中的某个位置。“下一位置”是指“当前位置”四周四个方向（东、西、南、北）上相邻的方块。“当前位置可通”是指未曾走到过的通道块，要求该方块位置不仅是通道块，而且从未纳入过当前路径（否则只能在死胡同内转圈）。如果在迷宫中的某一个位置探索其四个方向均为墙或曾经走过的位置，则该位置不可通。下面我们开始介

30、绍本算法求迷宫路径的基本思想：若当前位置可通，则纳入当前路径，并继续朝下一位置探索，即切换下一位置为当前位置，如此重复直至到达出口；若当前位置不可通，则应顺着来向退回到前一通道块，然后朝着除来向之外的其他方向继续探索；若该通道块的四周四个方块均不可通，则应从当前路径上删除该通道块。假设以栈S记录当前路径，则栈顶中存放的是当前路径上最后一个通道块。因此，纳入路径的操作即为当前位置入栈；从当前路径上删除前一通道块的操作即为出栈。例如，图3.5中假设当前位置在(2,2)处，首先按照前文中定义的“方向”的顺序依次探索当前位置的下一个位置，即(2,3)、(3,2)、(2,1)、(1,2)。当探索到(2,

31、3)位置为墙后，探索到(3,2)为通道并且之前未走过，所以(3,2)位置可通。这时，我们可不用再探索（2,1）、(1,2)，直接走到(3,2)位置，并且将当前位置纳入到表示迷宫路径的栈中，对(3,2)位置进行标记，使Maze32=2，表示已经走过。通过上述思想探索迷宫，最终可能出现两种情况：走到迷宫出口，该迷宫问题可解，此时栈中记录着通道的路径；栈最终被清空，该迷宫没有通到出口的路径。如图3.5，图中路径为该迷宫探索的全过程，包含退回到“前一通道块”的操作过程。本算法的描述如下：StatusMazePath(MazeTypemaze,PosTypestart,PosTypeend)/若迷宫ma

32、ze中存在从入口start到出口end的通道，则求得一条路径存放在栈中（从/栈底到栈顶），并返回TRUE；否则返回FALSEInitStack(S);curpos=start;/设定“当前位置”为“入口位置”curstep=1;/探索第一步doif(Pass(curpos,maze)/当前位置可以通过，即是未曾走过的通道块FootPrint(curpos,maze);/留下足迹e=(curstep,curpos,1);Push(S,e);/加入路径if(curpos=end)return(TRUE);/到达终点（出口）curpos=NextPos(curpos,1);/下一位置是当前位置的东邻

33、curstep+;/探索下一步/ifelse/当前位置不能通过if(!StackEmpty(S)Pop(S,e);while(e.di=4&!StackEmpty(S)Pop(S,e);/whileif(e.di4)e.di+;/换下一个方向探索Push(S,e);curpos=NextPos(e.pos,e.di);/设定当前位置是该新方向上的通道块/if(e.di4)/if(!StackEmpty(S)/elsewhile(!StackEmpty(S);return(FALSE);/MazePathStatusPass(PosTypepos,MazeTypemaze)if(mazepos.

34、xpos.y=0)returnOK;elsereturn0;voidFootPrint(PosTypepos,MazeTypemaze)mazepos.xpos.y=2;/标记为已走过该方块voidNextPos(PosType&pos,intdi)switch(di)case1:(pos).y+=1;break;/向东case2:(pos).x+=1;break;/向南case3:(pos).y-=1;break;/向西case4:(pos).x-=1;break;/向北算法3-13迷宫求解算法4、栈与递归实现的关系4、栈与递归实现的关系栈还有一个重要应用是在程序设计语言中实现递归。一个直接

35、调用自己或通过一系列的调用语句间接地调用自己的函数，称作递归函数。在程序设计中，递归是一个非常重要的工具。第一，有很多数学函数是通过递归定义的，比如阶乘函数：和2阶Fibonacci数列：等；第二，由于有的数据结构本身固有的递归特性，它们的操作可以通过递归进行描述，比如二叉树、广义表等；第三，有的问题虽然本身不具备明显的递归结构，但是运用递归进行问题的求解相比迭代方法更简单，比如八皇后问题、Hanoi塔问题等。作为递归函数，在其执行过程中，需要多次进行自我调用。为了理解这个问题，我们先看任意两个函数之间是如何进行调用的。在高级语言编制的程序中，调用函数和被调用函数之间的链接及信息交换需要通过栈

36、来进行。通常，当在一个函数的运行期间调用另一个函数时，系统在运行被调用函数前要先完成以下工作：（1）将所有的实在参数、返回地址等信息传递给被调用函数保存；（2）为被调用函数的局部变量分配存储区；（3）将控制转移到被调用函数的入口。同样，从被调用函数返回调用函数前，系统也需要完成一些工作：（1）保存被调用函数的计算结果；（2）释放被调用函数的数据区；（3）依照被调用函数保存的返回地址将控制转移到调用函数。当有多个函数构成嵌套调用时，按照“后调用先返回”的原则，上述函数之间的信息传递和控制转移必须通过栈来实现。系统设置一个栈作为整个程序运行时所需的数据空间，每调用一个函数就为其在栈顶分配一个存储区

37、，每从一个函数退出时就释放其存储区，则当前正运行的函数的数据区必在栈顶。实际上，在调用函数和被调用函数之间不一定传递参数的值，也可以传递参数的地址。通常，每个程序设计语言都有它自己的参数传递方法。下面举一个例子来具体说明函数调用的工作原理。在图3.6(c)所示的程序段中，主函数main中调用了函数first，而在函数first中又调用了函数second，则当前系统正在执行函数second中某个语句时栈的状态如图3.6(a)，从函数second退出后正执行函数first中某个语句时栈的状态如图3.6(b)。注意，图中语句标号表示返回地址。一个递归函数的运行过程类似于多个函数的嵌套调用，只是调用函

38、数和被调用函数是同一个函数，因此，和每次调用相关的一个重要概念是递归函数运行的“层次”。假设调用该递归函数的主函数为第0层，则从主函数调用递归函数为进入第1层；一般地，从第i层递归调用本函数为进入“下一层”，即第i+1层。反之，从第i+1层递归退出返回至“上一层”，即第i层。5、汉诺塔问题的算法5、汉诺塔问题的算法（1）问题的提出19世纪，欧洲出现了一个称为“汉诺塔”的游戏，该游戏表示（毫无疑问是伪造的）Brahma寺庙地下通道中的一个任务。在世界产生初期，牧师得到一个镶嵌着3根钻石针的黄铜平台。第一根针上堆积着64个金圆盘，每一个金圆盘比它下面的金圆盘稍微小一些（在欧洲流行的特殊版本为具有8

39、个纸圆盘和3个木质柱子）。牧师被赋予一项任务，将所有的金圆盘从第一根针移动到第三根针，遵从的规则是：每一次只能移动一个金圆盘，移动过程中可以借助第二根针，金圆盘不能放在比它小的金圆盘之上。牧师还被告知当完成这64个金圆盘的移动之后，将昭示着世界末日的到来。当然，我们的任务是编写一个计算机程序，为牧师列出一个移动金圆盘的指令列表。这个任务可以使用如下指令：Move(64,x,y,z)指令的含义是：将64个圆盘从塔x移动到塔z，可以使用塔y作为临时存储器。（2）解决方案有一个解决方案的思想是，不要将注意力集中在第一步（第一步肯定是将顶层圆盘移动到某处），应该主要集中在最困难的步骤上：移动底层圆盘。

40、在上面的63个圆盘被移走前，无法到达最底层的圆盘，所以必须将上面的63个圆盘都移动到塔b上，这样才能将底层圆盘从塔a移动到塔c。这是因为每次只能移动一个圆盘，底层圆盘（最大的圆盘）不能在其他任何圆盘之上，因此当移动底层圆盘时，其他任何圆盘都不能在塔a或塔c上。这样可以将汉诺塔的算法步骤归结为：Move(63,a,c,b);printf(“Movedisk64fromtoweratotowerc.n”);Move(63,b,a,c);现在离解决方案又近了一小步，仅仅是非常小的一步，因为仍然必须描述如何移动上面的63个圆盘。虽然如此，这仍然是重要的一步，因为可以采用同样的方法移动剩下的63个圆盘（

41、事实上，必须采用同样的方法移动，因为每一次都有一个最大的圆盘必须最后移动）。这正是递归的思想。上面已经描述了递归的原理和主要步骤，将64个圆盘的问题转变成63个圆盘的问题，那么剩下的解决步骤在实质上和前面是相同的。（3）算法根据以上分析，设把n个盘子从塔x搬到塔z，用塔y作为过渡，则编写出递归算法如下：1voidMove(intn,charx,chary,charz)2if(n=1)3printf(“%d.Movedisk%dfrom%cto%cn”,+i,n,x,z);/当只有一个盘子时，直接由塔x搬到塔z后结束一次函数调用/其中i是初值为0的全局变量，表示搬动的步骤数。4else5Move

42、(n-1,x,z,y);6printf(“%d.Movedisk%dfrom%cto%cn”,+i,n,x,z);7Move(n-1,y,x,z);89算法3-14Hanoi塔问题求解算法（4）系统运行追踪下面我们来看Move(3,a,b,c)语句执行过程（从主函数进入递归函数到退出递归函数而返回至主函数）中，递归工作栈状态的变化情况：递归层次语句行号递归工作栈状态（返址，n、x、y、z值）塔与圆盘的状态11,2,4,50,3,a,b,c123acb21,2,4,56,2,a,c,b0,3,a,b,c31,2,3,96,1,a,b,c6,2,a,c,b0,3,a,b,c231bac26,76,

43、2,a,c,b0,3,a,b,c1cba2331,2,3,98,1,c,a,b6,2,a,c,b0,3,a,b,ccba32128,96,2,a,c,b0,3,a,b,c16,70,3,a,b,c213cba21,2,4,58,2,b,a,c0,3,a,b,c31,2,3,96,1,b,c,a8,2,b,a,c0,3,a,b,cb2a1c326,78,2,b,a,c0,3,a,b,cba1c3231,2,3,98,1,a,b,c8,2,b,a,c0,3,a,b,c321bac28,98,2,b,a,c0,3,a,b,c同上18,90,3,a,b,c同上0栈空图3.8汉诺塔的递归函数调用示意图（

44、5）算法分析现在介绍另一个分析递归调用的工具，该工具与程序追踪相比，在管理调用的多样性方面具有更高的效率。这个工具称为递归树。下面为Move(3,a,b,c)语句执行过程的递归树：现在，计算一下在程序运行过程中，将进行多少次递归。Move函数第一次调用时，n=64，然后每次递归调用n的值减去1。那么，绘制程序的调用递归树时，从叶结点向上共有64级。除了叶结点之外，每个结点导致两个递归调用，因此每一级中的结点数是上一级的两倍。通过递归树，能够相当容易的计算出移动64个圆盘所需的指令数目。树中的每一个结点对应一条指令。结点数目总共为：1+2+4+263=20+21+22+263=264-1这是64

45、个圆盘需要的总移动次数。我们可以近似的估测一下这个数到底有多大?103=100024*1018=1.6*1019总的任务花费大约5*1011年。如果天文学家估计宇宙年龄大约为200亿（2*1011）年，则根据这个故事，世界将存在很长的时间是现在已经存在的时间的2.5倍！应当特别注意的是，尽管没有计算机能够实现整个汉诺塔，原因在于缺乏时间而导致失败，但肯定不是因为缺乏存储空间。所需要的空间仅仅是追踪64个递归调用使用的空间，但所需的时间是进行264-1次计算花费的时间。第三节队列栈是一种具有“先进先出”特性的线性表。这种特性对其操作有何影响呢？其存储结构相对于一般线性表又会有哪些变化？本节将从队

46、列的定义、抽象类型定义、队列的顺序与链式存储结构等方面入手解答上述问题。1、队列的定义1、队列的定义队列（Queue）简称队，也是一种特殊的线性表，可定义为只允许在表的一端进行插入，而在表的另一端进行删除的线性结构。队列允许插入的一端称为队尾（Rear），允许删除的一端称为队首（Front）。向队列中插入新元素称为进队或入队，新元素进队后就成为新的队尾元素；从队列中删除元素称为离队或出队，元素离队后，其后继元素就成为队首元素。由于队列的插入和删除分别在不同的两端进行，因而先插入者自然先从另一端删除，所以队列具有“先进先出”的特点，简称为FIFO（First-In,First-Out）。队列在日

47、常生活中十分常见，如在银行或餐厅中排队就是一个队列。在计算机应用中队列可用于许多编程的场合，例如用来作为模拟事件的排序表以及I/O缓冲。假设队列为q=(a1,a2,an)，则称a1为队首元素，an为队尾元素。队列中的元素是按照a1,a2,an的次序进入的，退出队列也只能按照这个次序依次退出，即只有在a1,a2,an-1都离开队列之后，an才能退出队列，如图3.10所示。2、队列的抽象类型定义2、队列的抽象类型定义在队列的抽象数据类型中，用Queue标识符来表示队列对象类型，操作部分应包括初始化、元素进队、元素出队、读取队首元素、检查队列是否为空等。下面给出队列的抽象数据类型的具体定义。ADTQ

48、ueue数据对象：D=ai|aiElemSet,i=1,2,n,n0数据关系：R1=|ai-1,aiD,i=2,n约定其中a1端为队首，an端为队尾。基本操作：InitQueue(&Q)操作结果：构造一个空队列Q。QueueEmpty(Q)初始条件：队列Q已存在。操作结果：若Q为空队列，则返回TRUE，否则FALSE。QueueLength(Q)初始条件：队列Q已存在。操作结果：返回Q的元素个数，即队列的长度。EnQueue(&Q,e)初始条件：队列Q已存在。操作结果：插入元素e为Q的新的队尾元素。DeQueue(&Q,&e)初始条件：Q为非空队列。操作结果：删除Q的队首元素，并用e返回其值。

49、GetHead(Q,&e)初始条件：Q为非空队列。操作结果：用e返回Q的队首元素。QueueTraverse(Q,visit()初始条件：Q已存在且非空。操作结果：从队首到队尾，依次对Q的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。ClearQueue(&Q)初始条件：队列Q已存在。操作结果：将Q清为空队列。DestroyQueue(&Q)初始条件：队列Q已存在。操作结果：队列Q被销毁，不再存在。ADTQueue3、循环队列的数据类型描述3、循环队列的数据类型描述在队列的顺序存储结构中，和顺序栈相类似，用一组地址连续的存储单元依次存放从队首到队尾的元素，同时附设两个

50、指针front和rear分别指示队首元素及队尾元素的位置。在本书中，我们约定：初始化建空队列时，令front=rear=0，每当插入新的队尾元素时，将新元素插入到队尾指针指向的位置后，尾指针增1；每当删除队首元素时，头指针增1。因此，在非空队列中，头指针始终指向队首元素，而尾指针始终指向队尾元素的下一个位置，如图3.11所示。假设当前为队列分配的最大空间为6，则当队列处于图3.11（d）的状态时不能再继续插入新的队尾元素，否则会因数组下标越界而破坏程序。但此时队列的实际可用空间并未占满，如果同顺序栈那样，继续分配存储单元扩大数组空间将会导致更大的浪费。为了解决这个问题，我们可以使顺序队列变成一

51、个首尾相接的环状的空间，指针和队列元素之间的关系不变，如图3.12所示，称之为循环队列。在图3.13（a）所示的循环队列中，队首元素是a3，队尾元素是a5。若元素a6、a7、a8相继插入，则队列空间被占满，如图3.13（b）所示，此时存在关系Q.front=Q.rear；相反地，若元素a3、a4和a5相继从图3.13（a）的队列中删除，则队列为空，如图3.13（c）所示，此时也存在关系Q.front=Q.rear。因此，若仅凭等式Q.front=Q.rear无法判断队列空间是“空”还是“满”。解决方案有两个：一个方案是另外设置一个标志位以区别队列是“空”还是“满”；另一个方案是少用一个存储单元

52、，以“队列头指针在队列尾指针的下一位置上”作为队列为“满”的标志。本书在下面的算法中采用第二种方法进行各操作的处理。循环队列所需要的具体数据类型描述如下：#defineMAXQSIZE100/最大队列长度typedefstructElemType*base;/初始化的动态分配存储空间intfront;/头指针，若队列不空，指向队首元素intrear;/尾指针，若队列不空，指向队尾元素的下一个位置SqQueue;4、循环队列的操作4、循环队列的操作（循环队列的生成算法、循环队列元素个数的求解算法、循环队列的入队算法、循环队列的出队算法、循环队列的遍历算法）生成循环队列循环队列的生成算法主要是为其

53、准备所需要的存储空间（这可通过malloc函数申请空间实现），同时令front=rear=0，形成空队列。StatusInitQueue(SqQueue&Q)/构造一个空队列QQ.base=(ElemType*)malloc(MAXQSIZE*sizeof(ElemType);if(!Q.base)exit(OVERFLOW);/存储分配失败Q.front=Q.rear=0;returnOK;算法3-15循环队列的生成算法返回队列元素个数在存储结构中，若尾指针在后，头指针在前，则直接通过Q.rear-Q.front返回队列长度。但是由于循环队列的特点，可能出现尾指针在前，头指针在后的情况，此时

54、通过MAXQSIZE-(Q.front-Q.rear)即Q.rear-Q.front+MAXQSIZE返回队列长度。这两种情况可以统一利用表达式：(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE来表示。intQueueLength(SqQueueQ)/返回Q的元素个数，即队列的长度return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;算法3-16循环队列元素个数的求解算法插入新的队尾元素首先由条件等式判断循环队列是否为“满”，若满则返回出错信息。否则插入元素e，并使尾指针沿环指向下一位置。本算法时间复杂度为O(1)。StatusEnQueue(S

55、qQueue&Q,ElemTypee)/插入元素e为Q的新的队尾元素if(Q.rear+1)%MAXQSIZE=Q.front)returnERROR;/队列满Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXQSIZE;returnOK;算法3-17循环队列的入队算法删除队首元素并返回首先由条件等式判断循环队列是否为“空”，若空则返回出错信息。否则用e返回队首元素值，并使头指针沿环指向下一位置。本算法时间复杂度为O(1)。StatusDeQueue(SqQueue&Q,ElemType&e)/若队列不空，则删除Q的队首元素，用e返回其值，并返回OK；/否则返回ERROR

56、；if(Q.front=Q.rear)returnERROR;e=Q.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE;returnOK;算法3-18循环队列的出队算法返回队首元素值首先由条件等式判断循环队列是否为“空”，若空则返回出错信息。否则用e返回队首元素值。本算法时间复杂度为O(1)。StatusGetHead(SqQueueQ,ElemType&e)/若队列非空，则用e返回Q的队首元素值，并返回OK。/否则返回ERROR；if(Q.front=Q.rear)returnERROR;e=Q.baseQ.front;returnOK;算法3-19循环队列队

57、首元素的求解算法循环队列的遍历本算法从队首元素开始，通过pos=(pos+1)%MAXQSIZE向队尾循环，对队列元素使用visit函数，直到队尾循环结束。该算法的主要操作和影响算法效率的步骤为循环遍历队列的元素，频数和队列长度相等，所以本算法的时间复杂度为O(n)。StatusQueueTraverse(SqQueueQ,Status(*visit)(ElemType)if(Q.front=Q.rear)returnERROR;pos=Q.front;/取得队首位置while(pos!=Q.rear)/由队首向队尾进行循环visit(Q.basepos);pos=(pos+1)%MAXQSI

58、ZE;算法3-20循环队列的遍历算法5、链队列的数据类型描述5、链队列的数据类型描述应用中有时用到队列的链接存储结构。我们把用链表表示的队列简称为链队列，如图3.14所示。下面只考虑单链存储结构，由于要经常操作队列的队首结点和队尾结点，需要有两个指针分别指向队首和队尾，即头指针front和尾指针rear。为了操作方便，给链队列添加了一个头结点，并令头指针指向头结点，头结点的指针域指向队首结点。由此，链队列为空的判断条件为头指针和尾指针均指向头结点，如图3.15（a）所示。但是不需要判别队列是否为满。链队列的操作即为单链表的插入和删除操作的特殊情况，只是还需修改尾指针或头指针，图3.15（b）（

59、d）展示了这两种操作进行时指针的变化情况。假定链队列中的结点类型为QNode，那么头和尾指针为QNode*指针类型。若把一个链队列的头指针和尾指针定义在一个结构体类型中，并假定该结构体类型用标识符LinkQueue表示，则链队列所需要的具体数据类型描述如下：typedefstructQNodeElemTypedata;/值域structQNode*next;/链接指针域QNode,*QueuePtr;typedefstructQueuePtrfront;/头指针QueuePtrrear;/尾指针LinkQueue;6、链队列的操作6、链队列的操作（链队列的生成算法、链队列元素个数的求解算法、链

60、队列的入队算法、链队列的出队算法、链队列的遍历算法）生成链队列链队列的生成算法主要是为其头结点准备所需要的存储空间（这可通过malloc函数申请空间实现），同时令头指针和尾指针均指向头结点。StatusInitQueue(LinkQueue&Q)/构造一个空队列Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(OVERFLOW);/存储分配失败Q.front-next=NULL;returnOK;算法3-21链队列的生成算法插入新的队尾元素当元素e入队时，首先创造链队列元素结点，并使原来的队尾元素结点的指针指向该元素结