《数据结构》课件第3章

第3章栈和队列3.1栈3.2队列本章小结习题三实训3-1栈的应用实训3-2队列的应用

【教学目标】栈和队列是两种特殊并且非常重要的线性表。通过对本章学习，掌握栈和队列的概念和特征，掌握栈和队列的顺序存储结构和链式存储结构，掌握栈和队列的基本操作的实现算法——进栈、出栈、判断栈空、入队、出队、判断队列空和队满，并能熟练地运用栈和队列解决实际问题。栈和队列是两种重要的数据结构，也是两种特殊的线性结构。从数据的逻辑结构角度来看，栈和队列是线性表；从操作的角度来看，栈和队列的基本操作是线性表操作的子集，是操作受限制的线性表。栈和队列在操作系统、编译原理、大型应用软件系统中得到了广泛的应用。3.1栈3.1.1栈的定义和基本操作

1.栈的定义栈(Stack)是一种限定性的线性表，是将线性表的插入和删除运算限制在表的一端进行。通常将表中允许进行插入、删除操作的一端称为栈顶(Top)，因此栈顶的当前位置是动态变化的，它由一个称为栈顶指针的位置指示器指示。同时表的另一端被称为栈底(Bottom)，栈底是固定的。非空栈如图3.1(a)所示。当栈中没有元素时称为空栈，如图3.1(b)所示。栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。图3.1栈结构示意图(a)非空栈；(b)空栈假设有一个栈S=(a1,a2,…,ai-1,ai,ai+1,…,an)，如果a1先进栈，则an最后进栈。因为进栈和出栈元素都只能在栈顶一端进行，所以每次出栈的元素总是当前栈中栈顶的元素，它是最后进栈的元素，而最先进栈的元素要到最后才能出栈。在日常生活中，有许多类似栈的例子。例如将洗净的盘子放入消毒桶时，总是一个接一个地往上摞(相当于进栈)；取出盘子时，则是从最上面一个接一个地往外拿(相当于出栈)，最后取出的是最先放进去的那个盘子。因此，栈又被称为后进先出(LastInFirstOut,LIFO)的线性表。

2.栈的基本操作栈的基本操作主要有以下七种：

(1) InitStack(S)。操作前提：S为未初始化的栈。操作结果：将S初始化为空栈。

(2) ClearStack(S)。操作前提：栈S已经存在。操作结果：将栈S置成空栈。

(3) IsEmpty(S)。操作前提：栈S已经存在。操作结果：判栈空函数，若S为空栈，则函数值为TRUE或1，否则为FALSE或0。

(4) IsFull(S)。操作前提：栈S已经存在。操作结果：判栈满函数，若S栈已满，则函数值为TRUE或1，否则为FALSE或0。

(5) Push(S,x)。操作前提：栈S已经存在。操作结果：在S的顶部插入(亦称压入)元素x；若S栈未满，将x插入栈顶位置，若栈已满，则返回FALSE或0，表示操作失败，否则返回TRUE或1。

(6) Pop(S)。操作前提：栈S已经存在。操作结果：删除(亦称弹出)栈S的顶部元素，返回该值；若栈为空，返回值为NULL，表示操作失败。

(7) GetTop(S)。操作前提：栈S已经存在。操作结果：取栈S的顶部元素。与Pop(S)不同之处在于GetTop(S)不改变栈顶的位置。3.1.2栈的顺序存储结构顺序栈是用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时由于栈的操作的特殊性，还必须附设一个位置指针top(栈顶指针)来动态地指示栈顶元素在顺序栈中的位置。通常以top=-1表示空栈。顺序栈的存储结构可以用C语言中的一维数组来表示。栈的顺序存储结构定义用C语言描述如下：#defineMAXSIZE50#defineElemtypeint /*栈中元素类型，此处以int为例*/typedefstruct{Elemtypedata[MAXSIZE]; /*用来存放栈中元素的一维数组*/inttop; /*用来存放栈顶元素的下标*/}SeqStack;SeqStack*S； /*定义指向栈的指针*/

top指针是在栈上进行插入或删除操作的依据，S->top = -1表示栈空，S->top = MAXSIZE-1表示栈满，这是在顺序栈的基本操作中必须考虑到的两个重要条件。假设MAXSIZE为6，栈中最多可存放6个元素，即S->data[0]至S->data[5]。栈顶指针S->top在元素进栈时做加1运算，元素出栈时做减1运算。图3.2说明了顺序栈进出操作时栈中元素和栈顶指针的关系。其中，图(a)表示空栈状态，图(b)表示一个元素A入栈后的状态，图(c)表示栈满状态，图(d)表示栈满后再删除元素F之后的状态。图3.2顺序栈进出操作示意图(a)空栈；(b)元素A进栈；(c)栈满；(d)元素F出栈以下是C语言描述的在顺序栈上实现栈的几个基本操作的算法：

(1)初始化空栈。voidinitStack(SeqStack*S)

/*顺序栈初始化为一个空栈*/{ S->top=-1;}

(2)判栈空。intisEmpty(SeqStack*S)

/*判栈S为空栈时返回值为真，反之为假*/{return(S->top==-1?1:0);}

(3)判栈满。intisFull(SeqStack*S){return(S->top==MAXSIZE-1?1:0);}

(4)进栈。intpush(SeqStack*S,Elemtypex)

/*元素x入栈*/{

if(S->top==MAXSIZE-1)

{printf(“栈满\n”);

/*栈上溢，提示出错*/

return(0);}

else

{

S->top++;

/*栈顶指针加1*/

S->data[S->top]=x;

/*给栈顶元素赋值*/

return(1);

}}

(5)出栈。intpop(SeqStack*S,Elemtype*x){/*将栈S的栈顶元素弹出，其值复制到x所指的存储空间中*/if(S->top==-1) /*栈为空*/return(0);

else{*x=S->data［S->top］;S->top--; /*修改栈顶指针*/return(1);}}

(6)取栈顶元素。intgettop(SeqStackS,Elemtype*x){/*将栈S的栈顶元素值复制到x所指的存储空间中，但栈顶指针保持不变*/

if(S->top==-1) /*栈为空*/ return(0);

else

{

*x=S->data［S->top］;

return(1);

}}3.1.3栈的链式存储结构栈也可以用链式存储结构表示，这种存储结构的栈称为链栈。在一个链栈中，为方便进行插入和删除操作，一般指定链表头为栈顶，链尾为栈底。链栈的数据类型用C语言描述如下：#defineElemtypeint

/*栈中元素类型，此处以int为例*/typedefstructsnode{

Elemtypedata;

structsnode*next;

｝LinkStackNode；typedefLinkStackNode*LinkStack;

top是栈顶指针，它是指针类型变量，top唯一地确定一个链栈。对于不带头结点的链栈，栈顶元素为top，当top = NULL时，该链栈为空栈；带头结点的链栈的栈顶元素为top->next，栈为空的条件是top->next = NULL，如图3.3所示。图3.3带头结点的链栈示意下面讨论在带头结点的链栈上实现进栈和出栈操作的算法。

1.进栈操作算法分析：当要将一个新元素x插入链栈时，可动态地向系统申请一个结点p的存储空间，将新元素x写入新结点p的数据域，然后将p结点插入在top的后继位置。算法用C语言描述如下：intpush(LinkStacktop,Elemtypex)/*将数据元素x压入栈top中*/{ LinkStackNode*p; p=(LinkStackNode*)malloc(sizeof(LinkStackNode)); if(p==NULL)return(0); /*申请空间失败*/ p->data=x; p->next=top->next; /*新结点插入在top的后继位置*/ top->next=p; return(1);}

2.出栈操作算法分析：当栈顶元素p出栈时，先取出p的值，再删除p。算法用C语言描述如下：intpop(LinkStacktop,Elemtype*x){/*将栈top的栈顶元素弹出，放到x所指的存储空间中*/

LinkStackNode*p;

p=top->next; /*p指向栈顶元素*/

if(p==NULL) /*栈为空*/

return(0);

top->next=p->next; /*从链中删除p结点*/*x=p->data;

free(temp); /*释放存储空间*/

return(1);}3.1.4栈与递归的实现栈非常重要的一个应用是在程序设计语言中实现递归。递归是指在定义自身的同时又出现了对自身的调用。如果一个函数在其定义体内直接调用自己，则称其为直接递归函数；如果一个函数经过一系列的中间调用语句，通过其它函数间接调用自己，则称其为间接递归函数。

1.递归的定义递归就是一个事件或对象部分地由自己组成，或者由它自己定义。例如，求阶乘就是递归的一个典型的例子：斐波那契数列也是一个典型例子：或n = 2递归算法包括递推和回归两部分：

(1)递推就是将复杂问题的求解“推到”对较简单问题的求解，如将求n!推到求(n-1)!，(n-2)!……使用递推时应注意到，递推应有终止之时，如求n!时，以n=0，0!＝1为递推的终止条件。

(2)回归就是指当“简单问题得到解后，回归到原问题的解上”。例如在求n！时，当计算完(n-l)！后，回归到计算n × (n-1)!上。常见的递归方法有两种:

(1)直接递归就是函数直接调用本身，如图3.4(a)所示。

(2)间接递归就是一个函数如果在调用其它函数时，又产生了对自身的调用，如图3.4(b)所示。图3.4递归调用(a)直接递归；(b)间接递归

2.递归的实现

1)递归实现的优点递归既是强有力的数学方法，也是程序设计中一个很有用的工具。其特点是对递归问题描述简捷，结构清晰，程序的正确性容易证明。

2)用递归算法求解问题的要素递归函数又称为自调用函数，函数(或过程)直接或间接调用自己的算法，称为递归算法。递归过程是利用栈的技术来实现的，只不过这个过程是系统自动完成的。递归算法的要点如下：

(1)所需解决的问题可以转化成另一个问题，而解决新问题的方法与原始问题的解决方法相同，只是处理的对象不同，并且它们的某些参数是有规律地变化的。

(2)必须具备终止递归的条件。程序中不应该出现无终止的递归调用，在某一特定的条件下，可以得到定解，而不再使用递归定义。

3)设计递归算法的方法

(1)寻找方法，将问题化为原问题的子问题求解(例如n! = n × (n-1)!)。

(2)设计递归出口，确定递归终止条件(例如求解n!，当n = 1时，n!= 1)。

3.递归的实现机制在一个程序的运行期间调用另一个过程函数时，在运行被调用过程函数之前，计算机系统必须先完成以下工作：

(1)为被调用的过程函数分配数据区。函数的数据区中包括了函数所需的各种局部变量，如函数的形参、函数执行过程中所需的临时变量等。举一个简单例子，在计算表达式x+y+z时，系统就要分配一个临时的变量w存放x＋y的值，再把w和z的值相加。

(2)将所有的实在参数、返回地址等信息传递给被调用的过程函数保存。

(3)把控制权转移到被调用过程函数的入口。在被调用的过程函数运行结束后返回到调用函数之前，也必须完成以下工作：

(1)保存被调用过程函数的计算结果。

(2)释放被调用过程函数占用的数据区。

(3)恢复被调用过程函数保存的返回地址，并把控制权转移到调用函数中的调用语句的下一条语句。上面是一个非递归的函数调用过程。在递归函数的调用和返回过程中是满足先调用后返回的执行次序的，即最先开始调用的递归函数需要最后返回。所以，支持递归的程序设计语言系统其递归函数的数据区应设计成栈的形式。这样每次递归调用时都把当前的调用参数、返回地址等压入栈形式的递归函数数据区；当本次调用结束时，系统退栈，并转移控制权到调用函数继续执行，直到栈空退出递归函数，返回调用函数。所以，计算机在执行递归算法时，系统首先为递归调用建立一个栈，称为递归工作栈。该栈的元素包括参数、局部变量和调用后的返回地址等信息。在每次调用递归之前，把本次算法中所有的参数、局部变量的当前值和调用后的返回地址等压入栈顶。在每次执行递归调用结束之后，又把栈顶元素的信息弹出，分别赋给相应的参数和局部变量，以便它恢复到调用前的状态，然后返回地址所指定的位置，继续执行后续的指令。下面介绍子程序的调用，子程序的调用与返回处理是利用栈完成的。当要去执行调用的子程序前，先将下一条指令的地址(返回地址)保存到栈中，然后再执行子程序。当子程序执行完成后，再从栈中取出返回地址。其过程如图3.5所示，当主程序A调用子程序B时，首先将返回地址b压入栈中，同样，在子程序B调用子程序C时，需将返回地址c压入栈中，当子程序C执行完毕后，就从栈中弹出返回地址c，回到子程序B，当子程序B执行完毕后，就从栈中弹出返回地址b，回到主程序A。图3.5递归调用中栈的变化过程下面用求n! 为例来说明递归的实现。使用递归方法求n!的算法，根据阶乘的定义它可以表示为：由n! 的定义可以看出它是一种递归的定义，当n=0时，是递归子程序的终止条件。用C语言描述的递归算法如下：

longfac(intn) /*递归调用函数*/{if(n<0)return(0);elseif(n==0)return(1);elsereturn(fac(n-1)*n);}3.2队列3.2.1队列的定义及基本操作队列(Queue)也是一种特殊的线性表。它只允许在表的一端插入元素，而在另一端删除元素，允许删除操作的一端称为队头(front)，允许插入操作的一端称为队尾(rear)。上述规定决定了先进队列的元素先出队列，就如平时排队买东西一样。因此队列又称做先进先出(FirstInFirstOut)的线性表，简称FIFO表。假设有队列Q = (a1,a2,…,an)，则队列中的元素是按a1,a2,…,an的次序进队，而第一个出队列的元素是a1，第二个出队列的是a2，只有在ai-1出队列后，ai才可以出队列(1≤i≤n)。当队列中没有元素时称为空队列。队列结构示意图如图3.6所示。图3.6队列结构示意图队列的基本操作主要有以下七种：

(1) InitQueue(&Q)。初始化操作。设置一个空队列。

(2) IsEmpty(Q)。判空操作。若队列为空，则返回1，否则返回0。

(3) EnterQueue(&Q，x)。进队操作。在队列Q的队尾插入x。操作成功，返回值为1，否则返回值为0。

(4) DeleteQueue(&Q,&x)。出队操作。使队列Q的队头元素出队，并用x带回其值。操作成功，返回值为1，否则返回值为0。

(5) GetHead(Q,&x)。取队头元素操作。用x取得队头元素的值。操作成功，返回值为1，否则返回值为0。

(6) ClearQueue(&Q)。队列置空操作。将队列Q置为空队列。

(7) DestroyQueue(&Q)。队列销毁操作。释放队列的空间。3.2.2队列的顺序存储

1.顺序队列队列的顺序存储结构称为顺序队列。和顺序栈不同的是，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放所有元素之外，由于队列的插入和删除分别在队列的两端进行，队头和队尾的位置是变化的，因此需附设两个指针front和rear，分别用来指示队头和队尾的位置。在初始化队列时，队列为空，在C语言中为了描述方便，通常约定front = rear = -1，如图3.7所示；每当插入新的队尾元素时“尾指针增1”，即rear++，如图3.8所示；每当删除队头元素时“头指针增1”，即front++，如图3.9所示。在非空队列中，头指针front总是指向当前队头元素的前一个位置，尾指针rear总是指向当前的队尾元素的位置。顺序队列为空的条件是front = rear。图3.7空顺序队列图3.8插入4个元素后的顺序队列图3.9删除2个元素后的顺序队列从图3.9中可以看出，顺序队列为空的条件是front = rear，假设顺序队列的最大长度为MAXSIZE，则顺序队列为满的条件是rear = MAXSIZE-1，队列长度len = rear-front。注意，判断顺序队列是否已满，能否进行插入操作，不是看队列长度是否达到最大，而是只看rear + 1的值是否越界。顺序队列的数据类型用C语言描述如下：#defineElemtypeint#defineMAXSIZE50

/*队列的最大长度*/typedefstruct{

Elemtypedata[MAXSIZE]；

intfront，rear； /*确定队头、队尾位置的两个变量*/｝SeqQueue； /*顺序队列的类型*/

(1)初始化操作。initSeqQueue(SeqQueue*q)｛

q->front=-1;

q->rear=-1;｝

(2)出队操作。出队操作即删除队列的队头元素，front指针加1。算法用C语言描述如下：intdeleteSeqQueue(SeqQueue*q,Elemtype*x){

if(q->front==q->rear) /*队列空，不能删除*/

return(0);

else{

q->front++;*x=(q->data[q->front]);

return(1); /*删除成功*/｝}

(3)入队操作。入队操作即在队尾插入元素，将rear指针加1，数据存入rear指针指到的位置，见图3.10和图3.11。图3.10待插入队列图3.11在队尾添加元素G后的示意图队尾插入算法用C语言描述如下：intenterSeqQueue(SeqQueue*q,intx){

if(q->rear>=MAXSIZE-1)

return(0)； /*队列已满，插入失败*/

else

{

(q->rear)++;

q->data[q->rear]=x;

return(1)； /*插入成功*/｝}在顺序存储结构的队列中，必须要讨论顺序队列的数组越界(或上溢)问题，假设一个队列最多能存放MAXSIZE(MAXSIZE=9)个元素，如图3.12所示，队列中已有MAXSIZE个元素，即队列已满，如果在队列中再插入一个元素J，那么就出现了数组越界或上溢的现象。图3.12队列已满，长度达到最大上面是整个队列中已装满MAXSIZE个元素的情况。可是即使删除了队列头元素，当队列处于图3.13所示状态时，如果再继续插入新的队尾元素，也会出现数组越界或上溢的现象，这种溢出是一种假溢出，因为队列的可用空间并未占满。解决假溢出最常用的办法是使用循环队列。图3.13队列已满，长度未达到最大

2.循环队列循环队列是将存储队列的存储区域看成是一个首尾相连的圆环，即将表示队列的数组元素Q[0]看成是Q[MAXSIZE-1]的直接后继，如图3.14所示。在循环队列中，当rear = MAXSIZE-1时，只要Q[0]是空闲的，下一个元素就可放入Q[0]中。在循环队列中，可以用“求模”运算来实现队头指针和队尾指针的值的计算。图3.14循环队列示意图入队操作时，队尾指针加1可描述为：q->rear = (q->rear + 1)%MAXSIZE;出队操作时，队头指针加1可描述为：q->front = (q->front + 1)%MAXSIZE。如图3.15(a)所示的循环队列中，队列头元素是A，队列尾元素是C，之后D、E和F相继插入，则队列空间均被占满，如图3.15(b)所示，此时front=rear；反之，若A、B、C相继被从图3.15(a)所示的循环队列中删除，使队列呈“空”的状态，如图3.15(c)所示，此时亦存在关系式front=rear。图3.15循环队列的头尾指针(a)一般情况；(b)队列满时；(c)空队列由此可见，只根据等式front = rear无法判别循环队列是“空”还是“满”。解决方法主要有两种。一种是另设一个标志位flag以区别队列是空还是满。当插入一个元素后，如果出现front = rear的情况，表示队列已满，则flag = 1；当删除一个元素后，如果出现front=rear的情况，表示队列为空，则flag = 0。当出现front = rear时，只要看flag标记的值是0还是1，就可以判断目前实际的空满状态。另一种方法是少用一个元素空间，即不用front所指空间，以队尾指针加1等于队头指针为判断队满的条件，即当(rear + l)%MAXSIZE = front时表示队满，当front = rear时表示队空。图3.16是循环队列为满的示意图。图3.16循环队列为满的示意图在第二种方法中，当rear≥front时，循环队列的长度len = rear-front；当rear＜front时，len = rear-front+MAXSIZE。二者统一起来，即len = (rear + MAXSIZE-front)%MAXSIZE。下面给出循环队列的几种基本操作的实现算法。

(1)初始化队列。设front与rear分别为队头和队尾指针。采用少用一个元素空间的方法，即循环队列的front所指空间不用，队列中的第1个元素是front的后继，rear指向队尾元素。初始时，令front与rear为0。initQueue(SeqQueue*q){

q->front=q->rear=0;}

(2)判队空。intqueueEmpty(SeqQueue*q){

if(q->rear==q->front)

return1;

else

return0;}

(3)取队头元素。intgetHead(SeqQueue*q,Elemtype*x){

if(queueEmpty(q))

{

printf("SeqQueueisempty");

return0;}else{

*x=q->data[(q->front+1)%MAXSIZE];

return1;}}

(4)入队操作。

intenterQueue(SeqQueue*q,Elemtype*x)

/*将新元素x插入队列*q的队尾*/

{

if((q->rear+1)%MAXSIZE==q->front)

{

printf("SeqQueueisfull");return0；

}else{q->rear=(q->rear+1)%MAXSIZE;q->data[q->rear]=x;}}

(5)出队操作。删除队列的队头元素，并返回该元素的值。

intdeleteQueue(SeqQueue*q,Elemtype*x)

{

if(queueEmpty(q))

{

printf("SeqQueueisempty");

return0;

}else{

q->front=(q->front+1)%MAXSIZE;*x=q->data[q->front];

return1;}}如果用户的应用程序中没有循环队列，则必须为它设定一个最大队列长度；若用户无法预估所用队列的最大长度，则最好采用链队列。3.2.3队列的链式存储采用链式存储结构表示的队列简称为链队列。它是仅在表头删除和表尾插入的单链表。一个链队列要在表头删除和在表尾插入，显然需要两个分别指示队头和队尾的指针，所以链队列是一个带头指针和尾指针的单链表。为使用方便通常添加一个头结点。链队列用C语言可以描述如下：

#defineElemtypeint /*定义数据类型*/

typedefstructnode /*链表结点类型定义*/

{

Elemtypedata;

structnode*next;

}Node;typedefstruct{

Node*front,*rear;}LinkQueue;LinkQueue*q;当一个队列*q为空时，front=rear，其头指针和尾指针都指向头结点，如图3.17所示。非空链队列如图3.18所示。图3.17空链队列图3.18非空链队列判断链队列为空的条件是：头指针和尾指针均指向头结点。链队列的基本操作主要是入队列和出队列操作，其操作方法是对单链表进行插入和删除操作的特殊情况。图3.19是入队列和出队列操作的示意图。图3.19队列运算指针变化情况(a)空队列；(b)元素A1入队列；(c)元素A2入队列；(d)元素A1出队列；(e)元素A2出队列，队列空从以上分析可以看出，插入在表尾进行，rear = rear->next；删除在表头进行，但头指针front始终没有发生变化，变化的是front->next；而当删除最后一个结点(front->next = = rear)时，还要调整rear = NULL。下面给出链队列的几种基本操作的实现算法：

(1)初始化。

intinitQueue(LinkQueue*q)

/*将q初始化为一个空的链队列*/

{

q->front=(Node*)malloc(sizeof(Node));

if(q->front!=NULL)

{

q->front->next=NULL;q->rear=q->front;return(1);}elsereturn(0); /*溢出！*/}

(2)判空队。

intqueueEmpty(LinkQueue*q){

if(q->front==q->rear)

return(1);elsereturn(0);

｝

(3)入队操作。intenterQueue(LinkQueue*q,Elemtypex) /*将数据元素x插入到队列q中*/{

Node*s;

s=(Node*)malloc(sizeof(Node));

if(s!=NULL)

{ s->data=x; s->next=NULL; q->rear->next=s; q->rear=s; return(1);} else

return(0);

/*溢出！*/}

(4)出队操作。intdeleteQueue(LinkQueue*q,Elemtype*x)

/*将队列q的队头元素出队，并存放到x所指向的存储空间中*/{

Node*s;

if(q->front==q->rear)

return(0);

s=q->front->next;q->front->next=s->next;

/*队头元素s出队*/if(q->rear==s) /*如果队中只有一个元素s，则s出队后成为空队*/q->rear=q->front;*x=s->data;free(s); /*释放存储空间*/return(1);}本章小结栈和队列是两种常见的数据结构，它们都是操作受到限制的线性表。栈的插入和删除均是在栈顶进行，它是后进先出的线性表；队列的插入在队尾，删除在队头，它是先进先出的线性表。当解决具有先进先出(或后进先出)特性的实际问题时，可以使用队列(或栈)这类数据结构来求解。和线性表类似，依照存储表示的不同，栈有顺序栈和链栈，队列有顺序队列和链队列两种，而实际使用的顺序队列是循环队列。在队列中解决假溢出的方法有三种：一是每删除一个元素后就将整个队列的元素向队头移动一个位置；二是在发生假溢出时将整个队列中的元素向队头移动，直到front=-1为止；三是采用循环队列。在非循环的顺序队列中判断队空的条件是front = rear，判断队满的条件是rear = MAXSIZE-1；在循环队列中判断队空的条件是front = rear。而判断队满的方法有两种：一种是设置一个判断队满的标志位；另一种是少用一个元素空间，用front = (rear+l)％MAXSIZE作为队满的条件。本章还介绍了顺序栈、链栈、循环队列和链队列的一些基本操作的实现算法，并举出了栈和队列在实际应用中的例子。习题三

一、填空题

1.栈是限定仅在表尾进行

操作的线性表，表头端称为

，表尾端称为

，栈的操作特性是

。

2.队列是限定仅在表尾进行

和在表头端进行

的线性表，队列的操作特性是

。

3.以下定义了一个顺序栈：

#defineMAXSTACK500typedefstruct{chardata[MAXSTACK];inttop;}sqstack;sqstackss;栈空的条件是：

，栈满的条件是：

；栈顶元素的表达式是：

，栈底元素的表达式是：

。

二、简答题

1.设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序插入在入栈操作之间，请回答下述问题：

(1)若入、出栈次序为Push(1),Pop(),Push(2),Push(3),Pop(),Pop(),Push(4),Pop()，则出栈的数字序列是什么(这里Push(i)表示i进栈，Pop()表示出栈)?

(2)能否得到出栈序列1423和1432? 并说明为什么不能得到或者如何得到。

(3)请分析1，2，3，4的24种排列中，哪些序列可以通过相应的入、出栈操作得到。

2.循环队列的优点是什么?如何判别它的空和满?

三、算法设计题

1.回文是指正读反读均相同的字符序列，如"abba"和"abdba"均是回文，但"good"不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈。)

2.括号配对检查，输入一个只有左括号“(”和右括号“)”的序列，程序对括号配对的正确性进行检查并给出结果。提示：配对检查算法中用到栈结构。例如括号序列“(()())”、“()()(())”为正确配对，括号序列“()())”、“)()(”为不正确配对等。注意：输入序列中只能出现左括号“(”和右括号“)”，序列的语法正确性由用户保证。请给出完整的C程序描述。实训3-1栈的应用【实训目的】

1.掌握栈“后进先出”的特点。

2.学会栈的应用。【实训内容】将非负十进制整数转换成八进制。【实训要求】

1.要求设计一个程序，满足下列要求：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。

2.用顺序栈实现。【算法分析】十进制数N和其它d进制数的转换是计算机实现计算的基本问题，其解决方法有很多，其中一个简单算法基于下列原理：N = (NDIVd) × d + NMODd其中，DIV为整除运算，MOD为求余运算(取模)，d为进制数。一个非负十进制整数转换成八进制，即(1348)10 = (2504)8，其运算过程见表3-1。表3-1非负十进制整数转换成八进制数的运算过程基于上述原理，计算过程是从低位到高位顺序产生八进制数的各个数位，而打印输出一般来说应该从高位到低位进行，恰好和计算过程相反。因此，如果将计算过程中得到的八进制数的各位顺序进栈，则按照出栈序列打印输出的就是对应的八进制数。可以用非递归算法实现本操作，即采用栈结构，将待转换的十进制整数除以基数8得到的余数压入栈中，再将商除以基数8得到的余数压入栈中，如此继续下去，直到商为0为止。最后从栈中弹出的数据就是本题的结果。这是利用栈的“后进先出”特性的最简单的例子。【程序清单】#defineElemtypeint#defineMAXSIZE100#include<stdio.h>typedefstruct{ Elemtypedata[MAXSIZE]; inttop;}SeqStack;voidinitStack(SeqStack*s){/*顺序栈初始化*/ s->top=0;}ElemtypegetTop(SeqStack*s){/*返回栈顶元素*/

Elemtypex;

if(s->top==0)

{printf("栈空\n");

x=0;

}

else x=(s->data)[s->top];returnx;}intpush(SeqStack*s,Elemtypex){/*元素x入栈*/ if(s->top==MAXSIZE-1)

{

printf("栈满\n");

return0;}

else{

s->top++; (s->data)[s->top]=x; return1;

}}Elemtypepop(SeqStack*s){/*返回栈顶元素并删除栈顶元素*/ Elemtypex; if(s->top==0)

{

printf("栈空\n");

x=0;} else {

x=(s->data)[s->top];  s->top--;

}returnx;}main(){ SeqStackstack,*s; intn; s=&stack; initStack(s); n=0; printf("输入一非负整数(十进制)："); scanf("%d",&n); push(s,'#'); while(n!=0) {

push(s,n%8);/*%为求余数运算符,余数入栈*/ n=n/8;

} /*/为求整数商运算符,商不为零,继续运行*/ printf("\n\n对应的八进制数为："); while(getTop(s)!='#') printf("%d",pop(s)); printf("\n");

}如果将上面的算法用递归算法来实现，算法描述如下：#include<stdio.h>voidd_to_or(intx){/*非负十进制整数转换为八进制数的递归算法*/if(x/8!=0)d_to_or(x/8);printf("%d",x%8);}main(){

intx;

printf("输入一非负整数(十进制)：");

scanf("%d",&x);

printf("\n\n对应的八进制数为：");