《数据结构》-栈和队列

第3章 栈和队列,本章要点：栈和队列两种抽象数据类型的特点。栈用两种存储结构表示时的基本操作算法的实现。栈和队列的应用。,线性表的操作允计在表的任何位置进行。 本章介绍的两种特殊的线性表，是操作受限制的特殊线性表栈(Stack)和队列(Queue)，其特殊性在于限制了插入和删除等运算的位置。,3.1 栈,栈是用来保存一些尚未处理而又等待处理的数据项这些数据项的处理是依据后进先出的规则。因此，经常把栈叫做后进先出线性表。栈在日常生活中几乎到处可见，如火车进库时，库的一端是堵死的，那么最后入库的火车必须先出来，否则前面的列车都被堵住，无法倒出。栈是这种事务的一种抽象。,3.1.1 栈的意义及抽象数据类型,栈是将线性表的插入和删除运算限制为仅在表的一端进行的线性表。通常将表中允许进行插入、删除操作的一端称为栈顶(Top)。栈顶的当前位置是动态变化的，表的另一端称为栈底(Bottom)。当栈中没有元素时称为空栈。栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。不含元素的栈称为空栈。 假设栈s=（a1，a2，an），a1元素所在的位子称为栈底，an元素所在的位子称为栈顶，如图3.1所示。,进栈顺序是a1，a2an，退栈的第一个元素是an，最后一个元素是a1是按“后进先出”的原则进行的，因此栈又称为后进先出（Last In First Out），缩写为（LIFO）的线性表。,图3.1 栈,3.1.1 栈的意义及抽象数据类型（续）,图3.2为铁路调度中栈的应用。在日常生活中还有一些类似栈的例子。例如：往箱子里放衣物，这相当于进栈最先放的衣服在箱底（栈底），最后放的在箱顶（栈顶），取时应先从箱顶开始拿，这相当于出栈操作。,3.1.1 栈的意义及抽象数据类型（续）,3.1.1 栈的意义及抽象数据类型（续）,栈的基本操作除了在栈顶进行插入或删除外，还有栈的初始化、清空及取栈顶元素等，下面给出栈的抽象数据类型定义：ADT stack 数据元素：可以是任意类型的数据，但必须属于同一个数据对象。数据关系：栈中数据元素之间是线性关系。基本操作： InitStack(S)：将S初始化为空栈。 ClearStack(S)：栈S已经存在，将栈S置成空栈。 EmptyStack(S)：栈S已经存在，判断若S为空，函数值返回TRUE，否则返FALSE。, DestroyStack(S)：栈S已经存在，销毁栈并释放空间。 Push(S,x)：栈S已经存在，若S栈未满，将x插入S栈的栈顶位置，函数返回TRUE；若S栈已满，则返回FALSE，表示操作失败。 Pop(S, x)：栈S已经存在，在栈S的顶部弹出栈顶元素，并用x带回该值；若栈为空，返回值为FALSE，表示操作失败，否则返回TRUE。 GetTop(S, x)：栈S已经存在，取栈S的栈顶元素，其余不变。(8)Stacklenth(S)栈S已经存在，返回栈中元素个数。 ADT stack,3.1.1 栈的意义及抽象数据类型（续）,3.1.2 栈操作的实现,与线性表一样，栈的存储方式也有两种：顺序存储和链表存储方式。3.1.2.1 栈的顺序存储结构 栈的顺序存储结构即顺序栈是分配一块连续的存储区域依次存放自栈底到栈顶的数据元素，同时设指针top来动态地指示栈顶元素的当前位置。空栈top=0或 top=-1表示。下面的顺序栈，采用的是top指向栈顶元素的后一个元素位置的方式来描述，当空栈时top=0。顺序栈的存储结构可以用C语言中的一维数组来表示。栈的顺序存储结构定义如下：,define Stack-Size 50typedef struct elemtype elemStack-Size； /*存放栈元素的一维数组*/int top； /*存放栈顶元素的下标*/ SeqStack； 若s为SeqStack类型变量，则s.elem0存放栈中第一个元素，s.elems.top-1为最后一个元素（栈顶元素）。当s.top= Stack-Size时为栈满，此时若再有元素入栈则将产生越界的错误，称为栈上溢(overflow)，反之,top=0 时为栈空，这时若执行出栈操作则产生下溢的错误(underflow)。图3.3表示了顺序栈中数据元素和栈顶指针之间的对应关系。,3.1.2 栈操作的实现（续）,3.1.2 栈操作的实现（续）,顺序栈中几种操作算法的实现。进栈/*在S栈中插入元素x，成功返回真失败返回假*/int Push(SeqStack *S, elemtype x) if(S-top = Stack-Size) return FALSE ； /*栈满不能插入元素返回假值*/ S-elemS-top=x； S-top+； return TRUE； /*成功将元素入栈，返回真值*/ ,3.1.2 栈操作的实现（续）,出栈/* 将栈S的栈顶元素弹出，放到x所指的存储空间中 */ int Pop(SeqStack * S, elemtype *x) if(S-top=0) return FALSE； /*栈为空返回假值*/ else S-top-； /*修改栈顶指针*/ *x= S-elemS-top； return TRUE； /*成功出栈，返回真值*/ ,3.1.2 栈操作的实现（续）,3.1.2 栈操作的实现（续）, 取栈顶元素 /* 将栈S的栈顶元素弹出， 放到x所指的存储空间中*/ int GetTop（SeqStack S, elemtype *x） if(S-top=) return FALSE； /*栈为空，结束返回假值*/ else *x = S-elemS-top -； /*取栈顶数据，存放在x中*/ return TRUE ； ,3.1.2 栈操作的实现（续）,(4)求栈中元素个数 int Stacklength(SeqStack S) /*返回栈中当前元素的个数 */ return S-top; ,3.1.2 栈操作的实现（续）,在栈的共享技术中最常用的是两个栈的共享技术：如图3.4所示，两个栈共享空间,它主要利用了栈“栈底位置不变，而栈顶位置动态变化”的特性。 首先为两个栈申请一个共享的一维数组空间SM，将两个栈的栈底分别放在一维数组的两端，分别是0，M-1。由于两个栈顶动态变化，这样可以形成互补，使得每个栈可用的最大空间与实际使用的需求有关。,3.1.2 栈操作的实现（续）,由此可见，两栈共享比两个栈分别申请M/2的空间利用率高。两栈共享的数据结构定义如下： define M 100 typedef struct elemtype StackM； /*存储两个栈的数据元素*/ int top2； /*top数组为两个栈顶*/ DseqStack；,3.1.2 栈操作的实现（续）,下面是二栈共享的一些操作算法。 初始化操作void InitStack(DseqStack *S) S-top0= 0； /*第一个栈的栈顶初值为*/ S-top1=M-1； /*第二个栈的栈顶初值为M-1*/ ,3.1.2 栈操作的实现（续）, 进栈操作/*将数据元素x压入i号堆栈，图3.4中 i=0 、1分别表示两个栈。*/int Push(DseqStack *S, elemtype x, int i) if(S-top0+1=S-top1-1) /*栈满*/ return FALSE； switch(i) case 0: S-StackS-top0=x； /*从第一个入栈*/ S-top0+； break； case 1: S-StackS-top1=x； /*从第二个入栈*/ S-top1-；break； default: return FALSE； /*参数错误*/ return TRUE ；,3.1.2 栈操作的实现（续）, 出栈操作int Pop(DseqStack *S, elemtype *x, int i) /* 从i 号堆栈中弹出栈顶元素并送到x中 */ switch(i) case 0:if(S-top0=) return FALSE； /*从左边出栈*/ *x=S-StackS-top0-1； S-top0- -； break； case 1:if(S-top1=M-1) return FALSE；/*从右边出栈*/ *x=S-StackS-top1+1； S-top1+； break； default:return FALSE； /*参数错误*/ return TRUE；,3.1.2 栈操作的实现（续）,3.1.2.2栈的链式存储结构栈的链式存储结构如图3.5所示，是一个单链表结构。栈顶指针是链表的的第一个结点，栈底指针指向链表的最后一个结点。类型说明如下：typedef struct node elemtype data； /*数据域 */ struct node *next；/*指针域 */ *LinkStack；,3.1.2 栈操作的实现（续）,对于链式结构一般不会有溢出，只有内存可用空间都被占满，malloc()过程无法实现才会产生上溢。因此,多个链栈共享空间很容易。下面给出链链式栈的基本操作算法： 进栈操作int Push(LinkStack top, elemtype x) /* 将数据元素x压入栈顶为top的链式栈中 */ temp=(LinkStack)malloc(sizeof(struct node)；/*创建结点*/ if(temp=NULL) return FALSE；/*申请空间失败结束，返回假值*/ temp-data=x； temp-next=top； /* 新结点压入栈顶 */ top=temp； /* 修改当前栈顶指针 */ return TRUE；,3.1.2 栈操作的实现（续）, 出栈操作int Pop(LinkStack top, elemtype *x) /*将链栈的栈顶top元素弹出，存储到x*/ temp=top； /* 将栈顶指针存入temp中*/ if(temp=NULL) return FALSE；/*栈空，返回假值*/ top=temp-next； /*栈顶指针下移*/ *x=temp-data； /*栈顶元素赋值给x*/ free temp； /* 释放存储空间 */ return TRUE；,3.1.2 栈操作的实现（续）,栈是一种操作上受限制的线性表，插入和删除不能随机进行（只能在一端）。从线性表顺序和链式存储结构的特点看，栈的顺序存储结构的操作与实现比链式存储结构有较大的优势。当多栈共享空间时，可以使用静态链表结构，能较好地解决问题。读者可以自己分析。,3.2 队列,在我们的生活中经常有这样的数据一端作为进端，另一端作为出端，如:排队等车。这种数据也是一种线性结构，但操作上不同于线性表，下面我们介绍这种数据结构。3.2.1 队列及其抽象数据类型 队列是一种操作受限的线性表，所有的插入都在表的一端进行，所有的删除都在表的另一端进行。进行删除的一端叫队列的头（front）称为队头，进行插入的一端叫队列的尾（rear）称为队尾。 ，如图3.8,3.2.1 队列及其抽象数据类型（续）,队列同现实生活中买东西排队相仿。后来的总是加入到队尾，每次离开的总是在队列头进行的。因此队列也称“先进先出线性表（First In First Out）。,队头 队尾 a1 a2 an 出队 入队 图3.8 队列示意图,3.2.1 队列及其抽象数据类型（续）,队列在程序设计中也经常出现。一个最典型的例子就是操作系统中的作业排队。在多道程序运行的计算机系统中，同时有几个作业运行。如果运行结果都需要通过通道输出，那就要按请求输出的先后次序排队。凡是请求输出的作业都是从队尾进入队列的。 队列的操作与栈的操作类似，下面给出队列的抽象数据类型定义：,ADT Queue数据元素D：可以是任意类型的数据，但必须属于同一个数据 对象。数据关系R：队列中数据元素之间是线性关系。 基本操作： (1) InitQueue(Q)：初始化操作。 设置一个空队列。(2) EmptyQueue(Q)：判空操作。若队列为空则返TRUE，否则 FALSE。(3) ClearQueue(Q)：队列置空操作。将队列Q置为空队列。(4) DestroyQueue(Q)：队列销毁操作。释放队列的空间。(5) GetHead（Q, x）：取队头元素操作。用x取得队元素的值。 操作成功，返回值为TRUE，否则返回值为FALSE。,3.2.1 队列及其抽象数据类型（续）,(6) QueueLength (Q): 队列Q已经存在，队列返回中元素个数。(7) EnterQueue(Q，x)：进队操作。在队列Q的队尾插入x。 操作成功，返回值为TRUE， 否则返回值为FALSE。 (8) DeleteQueue(Q, x)：出队操作，并用x返回值。成功，返TRUE，否则FALSE。 ADT Queue 队列也可以有两种存储形式，即顺序存储表示和链式存储表示，下面先来看队列的链式存储结构的形式及操作。,3.2.2 队列的链式存储结构,我们知道，对于使用中数据元素变动较大的数据结构，采用链式存储结构比顺序存储结构更有利。链队列就是这样一种数据结构。 用链表表示的队列需要两个指针，分别指示队头和队尾。如图3.9所示。,队头 Q1 Q2 Q n 队尾,图3.9 链队列示意图,3.2.2 队列的链式存储结构（续）,为了操作方便，和单链表一样，我们也给链队列添加一个哨兵结点，并令队头指针指向哨兵结点。队尾指针指向当前最后一个元素。由此，空的队列的判别条件为头指针和尾指针均指向哨兵结点。下面给出链队列数据类型：typedef struct Node elemtype data; /*数据域*/ struct Node next; /*指针域*/ LinkQueueNode; typedef struct LinkQueueNode *front; LinkQueueNode *rear; *LinkQueue;,3.2.2 队列的链式存储结构（续）,链队列的操作与单链表操作极为相似，只是插入、删除分别修改头指针、尾指针。一般来说，只要可用空间不被占满，链队列不会发生上溢情况。图3.10所示描述了一个带哨兵结点队列的创建、插入、删除操作过程。,3.2.2 队列的链式存储结构（续）,队列基本操作算法如下：(1).初始化操作。 int InitQueue(LinkQueue *Q)/* 将Q初始化为一个带哨兵的空链队 */ *Q-front=(LinkQueueNode *)malloc(sizeof(LinkQueueNode); /*开辟哨兵*/ if(*Q-front!=NULL) *Q-rear=*Q-front; /*队头、队尾都指向哨兵结点！*/ *Q-front-next=NULL; return OK; else return FALSE ; /*哨兵结点开辟失败！*/,3.2.2 队列的链式存储结构（续）,(2).入队操作int EnterQueue(LinkQueue *Q, elemtype e) /* 将数据元素e插入到带哨兵队列Q中 */ NewNode=(LinkQueueNode * )malloc(sizeof(LinkQueueNode); /*开辟新结点*/ if(NewNode!= NULL) NewNode-data=e; /*将新结点中赋e值*/ NewNode-next=NULL; *Q-rear-next=NewNode; /* 插入队尾 */ *Q-rear=NewNode; return TRUE ; else return FALSE ; /* 没开辟出新结点*/,3.2.2 队列的链式存储结构（续）,(3). 出队操作 int DeleteQueue(LinkQueue * Q, Elemtype *e) /* 将队列Q的队头元素出队， 并存放到e所指的存储空间中 */ LinkQueueNode *p; if(*Q-front=*Q-rear) return FALSE; /*空队列取队尾失败*/ p= *Q-front-next; /* 从队头取出结点p */ *Q-front-next=p-next; /* 队头元素p出队 */ if(*Q-rear=p) /*如果队中只有一个元素p，则p出队后成为空队*/ *Q-rear=*Q-front; *e=p-data; /* 结果作为变参返回*/ free(p); return TRUE; 其他算法，如队列的长度、取队头元素等，如何实现？。,3.2.3 队列的顺序存储结构-循环队列,虽然链队列很方便，但由于每个结点都有指针域，因此比顺序存储多占用内存空间。所以在有些情况下仍需要用顺序存储结构来表示队列。 在队列的顺序存储结构中，可以用一组地址连续的存储单元依次存放从队头到队尾的元素，还要设置两个指针分别指向队头元素和队尾元素的位置，并约定队头指针指示队列中第一个元素的位置，尾指针指示队尾元素位置的后一个位置。如图3.11所示。由于队列中队头和队尾的位置都是动态变化的，如果不加以约束，队头和队尾在数组中的位置是不断移动的如图3.11(b)、3.11(c)。图3.11(d)当队尾移动到最后位置时，不能再入队。但队头为3前面还有单元是空的。如果将顺序的数组看成一个环状的空间，即最后一个单元的后继为第一个单元。因此顺序存储的队列中，将所开辟空间地址的首、尾位置是连接起来形成一个环状结构称为循环队列，如图3.12所示。,3.2.3 队列的顺序存储结构-循环队列（续）,假设开辟了MAXSIZE个空间,初始化队列时，令frontrear0；入队时，直接将新元素送入尾指针rear所指的单元，然后尾指针增1,出队时，直接取出队头指针front所指的元素，然后头指针增1。显然，在非空顺序队列中，队头指针始终指向当前的队头元素，而队尾指针始终指向真正队尾元素后面的单元。随着入队和出队的进行当frontrear时，循环队列有两种情况，一种为队满；一种为队空。可见，frontrear无法判别队列的状态是“空”还是“满”。 对于这个问题，有两种处理方法：,3.2.3 队列的顺序存储结构-循环队列（续）,一种方法是少用一个元素存储空间。当队尾指针所指向的空单元的后继单元是队头元素所在的单元时，则停止入队。这样一来，队尾指针永远追不上队头指针，所以队满时不会有frontrear。这时队列“满”的条件为(rear十1)mod MAXSIZEfront。判队空的条件不变，仍为rearfront。 另一种方法是增设一个标志量的方法，以区别队列是“空”还是“满”。,3.2.3 队列的顺序存储结构-循环队列（续）,循环队列的类型定义如下： define MAXSIZE 50 / *队列的最大长度* / typedef struct elemtype elem MAXSIZE;/*队列的元素空间*/ int front,rear; /*头、尾指针*/ SeqQueue; 基本操作实现： 前面我们介绍了入队时，队满队空状态的两种处理方法，下面采用多用一个空闲空间的方法。,3.2.3 队列的顺序存储结构-循环队列（续）,(1) 入队操作int EnterQueue(SeqQueue *Q, elemtype e) /*将元素e加入队列Q*/ if(Q-rear+1)%MAXSIZE=Q-front) return FALSE; /* 队列满，返回假值结束*/ Q-elem Q-rear=e; /* 将e加入队尾*/ Q-rear=(Q-rear+1)%MAXSIZE; /* 重新设置队尾指针 */ return TRUE ; /* 操作成功*/,3.2.3 队列的顺序存储结构-循环队列（续）,（2）出队操作int DeleteQueue(SeqQueue *Q, elemtype *e) /*队列Q的队头元素出队， 用e返回其值*/ if（Q-front=Q-rear） return FALSE; /*队列为空，返回假值结束*/ *e=Q-elem Q-front; Q-front=(Q-front+1)%MAXSIZE;/*重新设置队头指针*/return TRUE; /*操作成功*/ ,3.2.3 队列的顺序存储结构-循环队列（续）,除了上述队列外，还有一种限定性数据结构，是双端队列（Deque）如图3.13所示 。双端队列是限定插入、删除在表的两端进行的线性表。这两端分别称作端点， 记作end1和end2。可以用一个铁轨转轨网络来比喻双端队列，如图3.13 (a)所示。,端点1 端点2a1 a2 an入队 出队 出队入队 (b)图3.13 双端队列,尽管双端队列看起来似乎比栈和队列更灵活，但实际上在程序系统中，不如栈和队列应用广泛，故在此不作详细讨论。,3.2.3 队列的顺序存储结构-循环队列（续）,3.3 栈和队列的应用,1、数制转换 假设要将十进制数N转换为d进制数，一个简单的转换算法是重复下述两步，直到N等于零。步骤一：X = N mod d (其中mod为求余运算)步骤二：N = N div d (其中div为整除运算)算法如下：,void Conversion(int N,int d)/*将N进制数， 转换为d进制数*/ Stack S； int x； /* S为顺序栈或链栈 */ InitStack( while( N 0) x=N % d； /*x依次得到最低位值、次低位值*/ Push(&S, x)； /*将转换后的数字压入栈S，低位在栈低 */ N= N / d； while(！EmptyStack(S)/*栈不空，输出高位到低位的d进制的值*/ Pop(&S,&x)； printf(%d,x)； ,3.3 栈和队列的应用(续),2. 括号匹配问题 假设表达式中包含三种括号：圆括号、方括号和花括号，它们可互相嵌套，要求它们在表达式中必须成对出现。如：( ( ) )或( ( ( ) ) )等均为正确的格式，而 ) 或 ( ) 或( )均为不正确的格式。在检验算法中可设置一个栈，每读入一个括号，若是左括号，则直接入栈，等待相匹配的同类右括号；若读入的是右括号，且与当前栈顶的左括号同类型，则二者匹配，将栈顶的左括号出栈，否则属于不合法的情况。另外，如果输入序列已读尽，而栈中仍有等待匹配的左括号，或者读入了一个右括号，而栈中已无等待匹配的左括号，均属不合法的情况。当输入序列和栈同时变为空时，说明所有括号完全匹配。,3.3 栈和队列的应用(续),void BracketMatch(char *str) /* str中为输入的字符串，利用堆栈技术来检查该字符串中的括号是否匹配*/ SeqStack S；int i；char ch； InitStack(&S)； for (i=0；stri!=0；i+) /*对字符串中的字符逐一扫描*/ switch(stri) case (: case : case : Push(&S,stri)； Break； case ): case : case : if(EmptyStack(S) printf(n右括号多余!)； return； else GetTop(&S,&ch)； if (Match(ch,stri) /*检查两个括号是否匹配*/ Pop(&S,&ch)； /*已匹配的左括号出栈*/ else printf(n对应的左右括号不同类!)；return； if (EmptyStack(S) printf(n括号匹配!)； else printf(n左括号多余!)；,int Match(char ch1,char ch2) /*判断两个括号ch1和ch2是否匹配*/ flag=0; /*flag为标志位，0表示不匹配，1表示匹配*/ switch (ch1) case (:if (ch2=)flag=1;break; case :if (ch2=)flag=1;break; case :if (ch2=)flag=1; return flag; ,3.3 栈和队列的应用(续),3表达式求值 表达式求值是程序设计语言编译中的一个最基本问题。它的实现是栈应用的一个典型例子。这里介绍一种简单直观、广为使用的算法，通常称“算符优先法”。 要把一个表达式翻译成正确求值的一个机器指令序列，或者直接对表达式求值，首先要能够正确解释表达式，例如，要对下面的算术表达式：42310/5求值。首先要了解算术四则运算的规则。即：先乘除，后加减；从左算到右；先括号内，后括号外。算符优先法就是根据这个运算俦关系的规定来实现对表达式的编译或解释执行的。 任何一个表达式都是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。一般地，操作数既可以是常数也可以是被说明为变量或常量的标识符；运算符可以分算术运算符、关系运算符和逻辑运算符等三类；基本界限符有左右括号和表达式结束符等。为了叙述的简洁，我们仅讨论简单算术表达式的求值问题。这种表达式只含加、减速、乘除四种运算符。读者不难将它推广到更一般的表达式上。,3.3 栈和队列的应用(续),我们把运算符和界限符统称为运算符，它们构成的集合命名为OP。根据上述三条运算规则，在运算的每步中，任意两个相继出现的算符1和2之间的优先关系至多是下面三种关系之一： 12：1操作的优先级别高于2表3.1定义了算符之间的这种优先关系。在表中1是在栈内的算符，2是在表达式中从左到右依次读入的算符。由规则我们知道，+、*和/为1时的优先级低于（，3.1表中为2时，栈内优先级高于栈外优先级表示为。还有一种情况是运算符间无优先关系，这是因为表达式中不允许它们相继出现，一旦遇到这种情况，则可以认为出现了语法错误，3.1表中无值。,3.3 栈和队列的应用(续),表3.1 运算符优先关系比较,3.3 栈和队列的应用(续),为实现算符优先算法，可以使用现使用两个工作栈。一个称做OPTR，用以寄存运算符；另一个称做OPND，用以寄存操作数或运算结果。算法的基本思想是： 首先置操作数栈为空栈，表达式起始符 为运算符栈的栈底元素； 依次读入表达式中每个字符，若是操作数则进OPTR栈，若是运算符，则和OPTR栈的栈顶运算符比较优先级后作相应操作，直到整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为#）表达式求值算法如下。,3.3 栈和队列的应用(续),Optype EvaluateExpression( ) /* Optype运算结果类型，OPTR和OPND分别为运算符栈和运算数栈*/ IniStack(OPTR); Push(OPTR, #)； IniStack (OPND)； c=getchar( )； While (c!= #| GetTop(OPTR)!= #) if (c=0& c=0 break； return OK； /*正确返回*/,4. 栈与递归的实现 栈非常重要的一个应用是在程序设计语言中用来实现递归。递归是指在定义自身的同时又出现了对自身的调用。如果一个函数在其定义体内直接调用自己，则称其为直接递归函数；如果一个函数经过一系列的中间调用语句，通过其它函数间接调用自己，则称其为间接递归函数。 例：n阶Hanoi塔问题：假设有三个分别命名为X、Y和Z的塔座， 在塔座X上插有n个直径大小各不相同、依小到大编号为1， 2, ， n的圆盘。现要求将X轴上的n个圆盘移至塔座Z上并仍按同样顺序叠排，圆盘移动时必须遵循下列原则： 每次只能移动一个圆盘； 圆盘可以插在X、 Y和Z中的任何一个塔座上； 任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。 图3.6 为三个盘子的Hanoi塔问题移动过程递归算法如下：,3.3 栈和队列的应用(续),3.3 栈和队列的应用(续),void hanoi(int n,char X,char Y,char Z) /*将塔座X上按直径由小到大且至上而下编号为1至n的n个圆盘*/ /*按规则搬到塔座Z上，Y可用作辅助塔座 */ if(n=1) move(X,1,Z)；/* 将编号为1的圆盘从X移动Z */ else hanoi(n-1,X,Z,Y)； /* 将X上为1至n-1号盘移到Y,Z作辅助 */ move(X,n,Z)； /* 将编号为n的圆盘从X移到Z */ hanoi(n-1,Y,X,Z)； /* 将Y上1至n-1号盘移动到Z，X作辅助 */ ,3.3 栈和队列的应用(续),当三个盘子移动时hanoi(3, X, Y, Z) 递归调用流程，如图3.7所示。,图3.7 三个盘子递归调用流程,XZ,(3,X,Y,Z),(2,X,Z,Y),(1,X,Y,Z),(2,Y,X,Z),XZ,XY,(1,Z,X,Y),ZY,(1,Y,Z,X),YX,YZ,(1,X,Z,Y),XZ,3.3 栈和队列的应用(续),hanoi(1,X,Y,Z) move(X-Z)move(X-Y)hanoi(1,Z,X,Y) move(Z-Y)hanoi(1,Y,Z,X) move(Y-X) move(Y-Z) hanoi(1,X,Y,Z) move(X-Z),hanoi(3,X,Y,Z),对应理解程序执行hanoi(3,X,Y,Z)递归展开过程如下:,hanoi(2,X,Z,Y) move(X-Z) hanoi(2,Y,X,Z),3.3 栈和队列的应用(