第3章 栈和队列(1-10已排版)

第3章 栈和队列

栈和队列在程序设计中应用十分广泛。栈和队列的逻辑结构和线性表相同，但它们是一种特殊的线性表。其特殊性在于运算受到了限制，插入和删除仅在表的一端或两端进行。因此栈和队列又称操作受限的线性表。栈按“后进先出”的规则进行操作，队按“先进先出”的规则进行操作。本章主要学习栈和队列的逻辑结构、存储结构及运算操作的实现，以及栈和队列在软件设计中的应用。

3.1 知识点串讲

3.1.1 知识结构图

本章主要知识点的关系结构如图3.1所示。

图3.1 栈和队列的知识结构图

3.1.2 相关术语

(1) 栈顶、栈底、队尾、队头 (2) 入栈、出栈 (3) 入队、出队 (4) 顺序栈、链栈

(5) 循环队列、链式队列

3.1.3 栈和队列的存储结构

栈和队列的存储与一般的线性表的实现类似，也有两种存储方式：顺序存储和链式存储。

1. 栈的顺序存储——顺序栈

顺序栈类似于顺序表，要分配一块连续的存储空间存放栈中的元素。这样需要用一个足够长度的一维数组来实现。栈底位置可以固定设置在数组的任一端(一般在下标为0的一端)，而栈顶是随着插入和删除操作而变化，用一个top 变量指明当前栈顶的位置。通常将data和top封装在一个结构体中，顺序栈的数据结构类型描述如下：

#define MAXSIZE 100 /*栈的最大容量*/ typedef struct{

DataType data[MAXSIZE]; /*栈的存储空间*/ int top;

}SeqStack, *PSeqStack; 要点：

(1) 静态分配存储空间。

(2) 插入与删除操作仅在栈顶处执行。 (3) 注意顺序栈的溢出现象。 (4) “后进先出”规则。 2. 栈的链式存储——链栈

链栈结点结构与单链表的结构相同。即结点结构为： typedef struct node{

DataType data;

struct node *next; }StackNode, *PStackNode;

因为栈的主要运算是在栈顶进行插入、删除操作，显然在链表的头部作为栈顶的处理最方便，而且没有必要同单链表那样为了运算方便附加一个头结点。为了方便操作和强调栈顶是栈的一个属性，链栈的数据结构描述如下：

typedef struct {

PStackNode top; }LinkStack, *PLinkStack; 要点：

(1) 链栈动态分配存储空间，无栈满问题，空间可扩充。 (2) 插入与删除仅在栈顶处执行。 (3) 链栈的栈顶在链头。 (4)“后进先出”规则。

3. 队列的顺序存储——顺序队

顺序队列和顺序栈一样，要分配一块连续的存储空间来存放队列里的元素。但由于队列的队头和队尾都是活动的，因此需要用两个变量指针来指示队头和队尾位置，这一点和顺序栈不同。这里约定队头指向实际队头元素所在的位置的前一位置，队尾指向实际队尾元素所在的位置。

顺序队的类型定义如下：

#define MAXSIZE 100 /*队列的最大容量*/ typedef struct{

DataType data[MAXSIZE]; /*队列的存储空间*/ int front, rear; /*队头、队尾指针*/ }SeqQueue,*PSeqQueue;

要点：

(1) 静态分配存储空间。

(2) 入队操作是在队尾进行，出队操作是在队头进行。

(3) 注意顺序栈的溢出和“假溢出”现象。可以用循环队列解决“假溢出”问题。 (4) 注意队列空和满的条件。 (5)“先进先出”规则。 4. 队列的链式存储——链队

链队就是用一个单链表来表示队列。为了操作上的方便，需要设置一个头指针和尾指针分别指向队头和队尾元素。

链队的描述如下： typedef struct node{ DataType data;

struct node *next;

} Qnode, *PQNode; /*链队结点的类型*/ typedef struct {

PQNnode front,rear;

}LinkQueue, *PLinkQueue; /*将头尾指针封装在一起的链队*/ 要点：

(1) 动态分配存储空间。

(2) 队头在链头，队尾在链尾。

(3) 链队在进队时无队列满问题，但有队列空问题。注意队列空的条件。 (4) “先进先出”规则。

3.2 典型例题详解

3.2.1 选择题

1．栈与一般线性表的区别在于____________。

A．数据元素的类型不同 B．运算是否受限制

C．数据元素的个数不同 D．逻辑数据不同

分析：该题目主要考查栈的定义。栈属于特殊的线性表，特殊性在于其删除和插入操作只能够在栈顶进行，是一种运算受到限制的线性表。答案为Ｂ。 2．一个顺序栈—旦被声明，其占用空间的大小____________。

A．已固定 B．可以改变 C．不能固定 D．动态变化 分析：该题目主要考查顺序栈存储结构的特点。顺序栈用数组实现，因此一旦顺序栈被声明，则其空间大小固定。答案应选择A。

3．设有—顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s4,s3,s6,s5,s1，则栈的容量至少应该是____________。

A．3 B．4 C．5 D．6 分析：该题目主要考查顺序栈的存储空间定义。当s2出栈时，则栈的容量为2(s1,s2在栈中)；当s4出栈时，则栈的容量为3(s1,s3,s4在栈中)；当s6出栈时，则栈的容量为3(s1,s5,s6在栈中)；因此栈的最小容量应为3。答案应选择A。 4． 从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，执行________。 A．x=top->data；top=top->next； B．top=top->next；x=top； C．x=top->data； D．x=top；top=top->next；

分析： 该题目主要考查链栈的具体操作。首先将指针变量x保存被删除结点，然后调整栈

顶指针(top=top->next)。选项A中，x=top->data操作目的是将栈顶结点的元素值赋给x，故无法满足题目要求。选项B中，首先进行栈顶指针top调整，则x保存的不是当前删除的结点，而是栈调整后的栈顶元素。因此答案应选择D。

5．在—个栈顶指针为top的链栈中，将一个s指针所指的结点入栈，执行____________。 A．top->next＝s： B．s->next=top->next; top->next=s;

C．s->next=top; top＝s； D．s->next=top; top=top->next;

分析：该题目主要考查链栈的具体操作。根据链栈入栈操作定义，即可得到答案。答案为C。从选择题4、5可以看出，链栈的入栈和出栈操作实质上是对没有头结点的单链表进行插入与删除操作。

6．链栈和顺序栈相比，有一个比较明显的优点，即____________。 A．插入操作更加方便 B．通常不会出现栈满的情况 C．不会出现栈空的情况 D．删除操作更加方便

分析： 该题目主要考查链栈和顺序栈的特点。栈的两种存储方式各有特点，即顺序栈所需存储空间较少，但栈的大小受数组的限制；链栈由于每个结点都包含数据域和指针域，则所需空间相对较大，但栈的大小不受限制(受内存容量的限制)。所以答案为B。对顺序栈而言，其插入操作(入栈)不需要大量地移动元素，故插入操作(入栈)则不是链栈的优点，因此A选项说法有问题。

7．用单链表表示的链式队列的队头在链表的____________位置。 A．链头 B．链尾 C．链中 D．任意位置

分析：该题目主要考查链式队列的存储结构，如图3.2所示。队列的队头是对队列元素进行删除的一端，链队列的队头在链表的链头位置。 (不考虑不包含数据元素的头结点)，答案为A。 front a2a1 an ∧ ……. rear

图3.2链式队列

8．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。该缓冲区应该是一个____________结构。

A．堆栈 B．队列 C．数组 D．线性表

分析：该题目主要考查队列的性质和应用。缓冲区中的数据应该是先到达的先打印，所以使用具有FIFO性质的队列来实现。答案为B。 9．做入栈运算时，应先判断栈是否为 (1) ，做出栈运算时，应先判断栈是否为 (2) 。当顺序栈中元素为n个，做入栈运算时发生上溢，则说明该栈的最大容量为 (3) 。为了增加内存空间的利用率和减少发生上溢的可能性，由两个顺序栈共享一片连续的内存空间时，应将两栈的 (4) 分别设在这片内存空间的两端，这样，只有当 (5) 时，才产生上溢。

(1)、(2)A．空 B．满 C．上溢 D．下溢 (3) A．n-l B．n C．n＋1 D．n／2 (4) A．长度 B．深度 C．栈顶 D．栈底 (5) A．两个栈的栈顶同时到达栈空间的中心点 B．其中一个栈的栈顶到达栈空间的中心点 C．两个栈的栈顶在栈空间的某一位置相遇

D．两个栈均不为空,且一个栈的栈顶到达另一个栈的栈底

分析：该题目主要考查栈的性质、结构和操作。答案为：(1)B (2)A (3)B (4) D (5) C

10．若已知一个栈的入栈序列是l,2,3,?,30，其输出序列是p1,p2,p3,?,pn，若p1＝30，则p10为____________。

A． 11 B． 20 C． 30 D． 2l

分析：该题目主要考查栈的性质、结构和操作。已知数据的入栈序列是l，2，3，?，30，出栈序列的第1个元素是30，因此可以确定，所有元素是按入栈序列顺序全部入栈之后才开始出栈的。也就是说，出栈序列与入栈序列刚好相反，可求得出栈序列的第10个元素为21，即D答案正确。

11．循环队列A[m]存放其元素，用front和rear分别表示队头及队尾，则循环队列满的条件是_________。

A．(Q->rear+1)%m==Q->front B．Q->rear==Q->front+1 C．Q->rear+1==Q->front D．Q->rear==Q->front 分析：该题目主要考查循环队列的存储结构以及队满的判断条件。循环队列的引入是为了解决队列存在的“假溢出”问题，但在循环队列中会出现队满和队空的判断条件相同而导致无法判断，通常采用少用一个元素空间的策略来解决该问题(其它策略讲解请参考配套教材)。使队尾指针Q->rear无法赶上Q->front，即队尾指针加1就会从后面赶上队头指针，这种情况下队满的条件是：(Q->rear+1) %m== Q->front。答案是A。

12．设数组data[m]作为循环队列sq的存储空间，front 为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为_________。

A．front=front+1 B．front=(front+1)%(m-1) C．front=(front-1)%m D．front=(front+1)%m 分析：该题目主要考查循环队列的存储结构和出队操作。队列的头指针指向队首元素的实际位置，因此出队操作后，头指针需向上移动一个元素的位置。根据第11题的解答可知，循环队列的容量为m，所以头指针front加1以后，需对m取余，使之自动实现循环，即当front取到最大下标(m-1处)以后，自动循环回来取0值。所以答案是D。 13．由两个栈共享一个向量空间的好处是_________ 。

A．减少存取时间，降低下溢发生的机率 B．节省存储空间，降低上溢发生的机率 C．减少存取时间，降低上溢发生的机率 D．节省存储空间，降低下溢发生的机率 分析：该题目主要考查对顺序栈存储结构的理解。两个栈无论是共享向量空间还是单独分配空间，对它们的操作所需的时间没有影响。两个栈共享向量空间，主要是为了节省存储空间，降低上溢的发生机率，因为当一个栈中的元素较少时，另一个栈可用空间可以超过向量空间的一半。答案应选择B。

14．若用单链表来表示队列，则应该选用___________。

A．带尾指针的非循环链表 B．带尾指针的循环链表 C．带头指针的非循环链表 D．带头指针的循环链表

分析：本题主要考查读者对循环单链表存储结构和队列定义的理解。设尾指针rear，则通过rear可以访问队尾，通过rear->next可以访问队头，因此带尾指针的循环链表较适合。答案应选择B。

3.2.2 判断题

1．消除递归不一定需要使用栈，此说法是否正确。 正确

分析：该题目主要考查栈在递归中的应用。对于尾递归可以将其转化成递推，不需栈。所以这种说法是正确的。

尾递归是指一个递归函数的递归调用语句是递归函数的最后一句可执行语句。 例如下面是一个输出数组元素的递归函数。

void RPrintArray(int list[],int n) {

if(n>=0)

{

printf(“%d”,list[n]); RPrintArray(list,--n);

} }

此程序是尾递归程序，消除尾递归很简单，只需首先计算新的n值，n=n-1，然后程序转到函数的开始处执行就行了，可以使用while语句来实现。

相应非递归函数如下：

void PrintArray(int list[],int n) {

while (n>=0)

{

printf(“%d”,list[n]); --n; } }

2．栈和队列都是限制存取点的线性结构。 正确

分析：该题目主要考查栈和队列的定义。它们都只能在一端或两端存取数据的线性结构。见选择题第1题解答。

3．入栈操作、出栈操作算法的时间复杂性均为O(n)。 错误

分析：该题目主要考查栈的操作算法。入栈与出栈操作都在确定的栈顶位置进行，算法的时间复杂性均为O(1)。所以这种说法是错误的。

4．队列逻辑上是一个下端和上端既能增加又能减少的线性表。 错误 分析：该题目主要考查队列的逻辑结构和操作。队列是上端只能进行入队操作(即增加操作)，下端只能进行出队操作(即减少操作)。

5．用I代表入栈操作，O代表出栈操作，栈的初始状态和栈的最终状态都为空，则使用栈的入栈和出栈可能出现的操纵序列为IOIOIOOI。 错误

分析：该题目主要考查栈的操作和“溢出”问题。在栈的操作中，保证出栈前提是栈中有元素，否则会造成栈的下溢，IOIOIOOI会出现下溢。 6．任何一个递归过程都可以转换为非递归过程。 正确 分析：该题目主要考查栈在递归过程非递归化中的应用。任何一个递归过程都可以按照一定的步骤机械地转换为非递归过程。由于栈的后进先出特性吻合递归算法的执行过程，因而可

以用非递归算法替代递归算法。递归过程转换为非递归过程的实质就是将递归中隐含的栈机制转化为由用户直接控制的栈，利用堆栈保存参数。

3.2.3 填空题

1．已知一个栈ｓ的输入序列为abcd，判断下面两个序列能否通过栈的Push_Stack和Pop_Stack操作输出：

(1)dbca (1) (2)cbda (2) 答案：(1)不能 (2)能

分析：该题目主要考查栈的操作。(1)不能，因为弹出d时，abc均已依次压入栈，下一个弹出的元素只能是c而不是b。(2)能，Push_Stack (s,a)，Push_Stack (s,b)，Push_Stack (s,c)，Pop_Stack (s)，Pop_Stack (s)，Push_Stack (s,d), Pop_Stack (s), Pop_Stack (s)。 2．对循环队列Q(设循环队列空间大小为MAXSIZE)，如何修改队头指针? (1) ；

如何修改队尾指针? (2)

答案：(1)front=(front+1)% MAXSIZE (2)rear=(rear+1)% MAXSIZE

分析：该题目主要考查循环队列的操作。具体解答请参见选择题第11和12题。

3．设长度为n的链队列用单循环链表表示，若只设头指针，则入队列出队列操作的时间分别为 (1) 和 (2) ；若只设尾指针，则入队列出队列操作的时间分别为 (3) 和 (4) 。

答案：(1)O(n) (2)O(n) (3)O(1) (4)O(1)

分析：该题目主要考查链队列和单循环链表的综合知识。当只设头指针时(如图3.3(a)所示)，入队相当于在an结点之后执行结点插入操作，根据链表的插入操作特点可知，插入操作前必须知道结点a1和an的地址，获取结点an的地址的时间复杂度为O(n)；出队则相当于删除结点a1的操作，因此必须获取结点an的地址，同样其时间复杂度为O(n)。若设置尾指针(如图3.3(b)，入队相当于在结点a1之前和an之后执行结点插入操作，通过rear和rear->next可以获得结点an和a1的地址，则其时间复杂度为O(1)；出队则相当于删除结点a1的操作，同样其时间复杂度为O(1)。

head

a1 a2 ??. an

(a)

a1 a2 ??. an rear

(b)

图3.3单循环链表表示的链队列示意图

4．对于循环向量中的循环队列，写出求队列中元素个数的公式___________。 答案： (rear-front＋MAXSIZE)% MAXSIZE，其中MAXSIZE表示队列的存储空间。 分析：该题目主要考查循环队列的存储结构特点。

5．向顺序栈插入新元素分为三步：第一步，进行 (1) 判断，判断条件是 (2) ；第二步是修改 (3) ；第三步把新元素赋给 (4) 。同样从顺序堆栈删除元素分为三步；第一步，进行 (5) 判断，判断条件是 (6) ；第二步是把 (7) 值返回；第三步 (8) 。

答案：(1)栈是否满(2)s->top= MAXSIZE -1(3)栈顶指针(top++)(4)栈顶对应的数组元

素(5)栈是否空(6)s—>top=-1(7)栈顶元素(8)修改栈顶指针(top--)

分析：该题目是考虑栈的运算规则及其入出栈的实现步骤。入栈时一般考虑判断栈满否，条件是是否超出最大空间。如果没有超出应该修改栈顶指针，然后将元素压入堆栈。出栈时，应首先考虑堆栈是否空。如果不空，先保留栈顶元素，然后修改栈顶指针。

6．在将中缀表达式转换成后缀表达式和计算后缀表达式的算法中，都需要使用栈。对于前者，进入栈的元素为表达式中的 (1) ，而对于后者，进入栈的元素为 (2) 。中缀表达式(a+b)/c-(f-d/e)所对应的后缀表达式是 (3) 。 答案：(1)运算符 (2)操作数 (3)ab+c/fde/--

分析：该题目主要考查栈的应用。中缀表达式就是将运算符写于参与运算的操作数的中间，操作数依原序排列。后缀表达式就是将运算符列于参与运算的操作数之后，操作数的排列依原序。因此计算后缀表达式值的过程为：从左向右扫描后缀表达式，遇到操作数就进栈，遇到运算符就从栈中弹出两个操作数，执行该运算符所规定的运算，并将所得结果进栈。如此下去，直到表达式结束。所以对于计算后缀表达式，进栈的元素为操作数。

7．假设以S和X分别表示入栈和出栈操作，则对输入序列a，b，e，d，e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为_______。 答案：bceda

分析：该题目主要考查入栈和出栈操作。入栈和出栈操作只能在栈顶位置进行。根据操作序列，首先a，b进栈，然后b出栈；接着c进栈、c出栈；d、e相继进栈，栈顶元素为e，最后e、d、a相继出栈。这样，得到出栈序列为bceda。

3.2.4 应用题

1．将整数1、2、3、4依次入栈或出栈，请回答下述问题： (1)当入、出栈次序为Push_Stack(S，1)、Pop_Stack(S)、Push_Stack(S，2)、Push_Stack(S，x3)、Pop_Stack(S)、Push_Stack(S，4)、Pop_Stack(S)，出栈的数字序列为何？ (2)能否得到出栈序列1423和1432？并说明为什么不能得到或者如何得到。

(3)设有n个数据元素的序列顺序进栈，试给出可能输出序列的个数和不可能输出序列的个数。当n=4(1、2、3、4)有24种排列，哪些序列是可以通过相应的入出栈操作得到的。 分析与解答：该题目主要考查栈的性质、结构和操作。

(1) 出栈序列为l、3、4。

(2) 序列1、4、2、3不可能得到。因为4和2之间隔了3，当4出栈后，栈顶元素是3，而2在3的下面。序列1、4、3、2可以得到：Push_Stack(S，1)、Pop_Stack(S)、Push_Stack(S，2)、Push_Stack(S，3)、Push_Stack(S，4)、Pop_Stack(S)、Pop_Stack(S)、Pop_Stack(S)。

(3) 设有n个数据元素的序列(假设这个序列为1，2，3，4，5??n)顺序进栈，那么输出序列个数f(n)可以递推求出：为讨论方便, 设n=0, f(0)=1，当，

n=1：显然f(1)=1 n=2：容易得知f(2)=2

n=3：1最后出栈的序列有f(2)种，2最后出栈的序列有f(1)* f(1)种，3最后出栈的序列有f(2)种，所以 f(3)=2* f(2)+f(1)*f(1)=5

n=4：1最后出栈的序列有f(3)种，2 最后出栈的序列有f(1)* f(2)种，3最后出栈的序列有f(2)*f(1)种，4最后出栈的序列有f(3)种，所以f(4)= 2*f(3)+ f(1)* f(2)+ f(2)* f(1)=14

可以看出i(i=1,2,3,??n)最后出栈的序列有f(i-1)*f(n-i)

所以f(n)=f(0)*f(n-1)+ f(1)*f(n-2)+f(2)*f(n-3)+f(3)*f(n-4)+?? + f(n-1)*f(0)，

用数学方法可得到

f(n)= Cn??2n?! 11?C2n??nn?1n?1n!?2n?n?!对有n个数据元素的序列，全部可能的排列个数为：Pn=n!

所以，不可能输出序列的个数为：Pn-Cn。 因此4个元素的出栈序列数为： C4?18！??14 4?14!?4!这14种出栈序列如下：

1234 1243 1324 1342 1432 2134 2143 2314 2341 2431 3214 3241 3421 4321

Cn??2n?! 1?n?1?n!?22．试说明下述运算的结果

(1) Pop_Stack(Push_Stack(S，A))； (2) Push_Stack(S，Pop_Stack(S))；

(3) Push_Stack(S，Pop_Stack(Push_Stack(S，B))) 分析与解答：该题目主要考查栈的操作。

(1) 首先要实现运算Push_Stack(S，A)，其结果是将元素A压入栈S中。若栈S满，则出现上溢现象的处理；否则把元素A压入栈顶，且元素个数加1。然后作Pop_Stack(S)运算， 将栈顶元素弹出，且元素个数减1。

(2) 首先作Pop_Stack(S)运算。若栈A为空，则作下溢处理；否则弹出栈顶元素。然后再进行压入运算，将刚才弹出的元素压入栈S中。

(3) 这种复合运算复杂一些，在(1)、(2)的基础上可知，这种运算的结果使栈S增加了一个栈顶元素B。

3．何谓队列的上溢现象，一般有几种解决方法，试简述之。 分析与解答：该题目主要考查队列的存储结构。

在队列的顺序存储结构中，设队列指针为front，队尾指针为rear，队列的容量(即存储的空间大小)为MAXSIZE。当有元素要加入队列(即入队)时，若rear==MAXSIZE-1，则队列已满，此时就不能将该元素加入队列。对于队列，还有一种“假溢出”现象，队列中尚余有足够的空间，但元素却不能入队，一般是由于队列的存储结构或操作方式的选择不当所致，可以用循环队列解决。

一般地，要解决队列的上溢现象可有以下几种方法：

(1) 可建立一个足够大的存储空间以避免溢出，但这样做往往会造成空间使用率低，

浪费存储空间，一般不采用这种方法。

(2) 采用移动元素的方法，每当有一个新元素入队，就将队列中已有的元素向对头移

动一个位置，假定空余空间足够。每当删去一个队头元素，则可依次移动队列中的元素总是使front指针指向队列中的第一个位置。

(3) 采用循环队列方式。将队头、队尾看作是一个首尾相接的循环队列，利用一维

数组顺序存储并用取模运算实现。

4．设栈S={1,2,3,4,5,6,7},其中7为栈顶元素。请写出调用 algo(&S)后栈S的状态。

void algo(PseqStack S) { int x;

PseqQueue Q； PseqStack T；

Q=Init_SeqQueue( )； T=Init_SeqStack( )； while(!Empty_SeqStack(S))

{ Pop_ SeqStack(S,&x);

if (x/2!=0) Push_SeqStack(T，x)；

else En_SeqQueue(Q，x)； }

while(!Empty_SeqQueue(Q)) { Out_ SeqQueue(Q,&x); Push_SeqStack(S，x)； }

while(!Empty_SeqStack(T)) { Pop_ SeqStack(T,&x); Push_SeqStack(S，x)； } }

分析与解答：本函数的功能是将顺序栈S中递增有序的整数中的所有偶数调整到所有奇数之前，并且要求偶数按递减序排列，奇数按递增序排列。

算法首先设置并初始化中间栈T和中间队列Q，然后将S栈中的整数出栈，若整数为奇数，入栈T,若为偶数，入队列Q。这样S=Φ,T={7,5,3,1},其中1为栈顶元素,Q={6,4,2},其中6为队头元素。然后，将Q中整数出队列并入栈S, 这样S={6,4,2},其中2为栈顶元素,再将T中元素出栈，并入栈S, 这样S={6,4,2,1,3,5,7},其中7为栈顶元素。

最后S栈的状态如图3.4所示。

top

1 6 2 4 3 2 4 1 5 3 6 5 7 7 8 9 10 图3.4 调用algo(&S)后栈S的状态

5．假设两个队列共享一个循环向量空间(如图3.5所示)，其类型Queue2定义如下：

rear[1] front[1] …

typedef struct{

DateType data[MAXSIZE]; int front[2],rear[2]; } Queue2;

front[0] … rear[0] 图3.5双循环队列示意图 对于i=0或1，front[i]和rear[i]分别为第i个队列的头指针和尾指针。请对以下算法填空，实现第i个队列的入队操作。

int EnQueue (Queue2 *Q, int i, DateType x)

{ /*若第i个队列不满，则元素x入队列，并返回1；否则返回0*/

10. 循环队列存储在数组A[0..m]中，则入队时队尾的操作为( )。

A. rear=rear+1 B. rear=(rear+1)%(m-1) C. rear=(rear+1) % m D. rear=(rear+1)%(m+1) 参考答案： 1 C 2 C 3 D 4 C 5 C 6 A 7 D 8 B 9 C 10 D 3.3.2 填空题

1. 队列是 的线性表，其运算遵循 的原则。 2. 是限定仅在表尾进行插入或删除操作的线性表。

3. 用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为 。

4. 当两个栈共享一存储区时，存储区用一维数组stack(1,n)表示，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为 ，栈2空时 ，top[2]为 ，栈满的条件是 。

5. 在链式队列中，判定只有一个结点的条件是 。 6. 循环队列的引入，目的是为了克服 。

7. 已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是 。 8. 循环队列满与空的条件是 和 。

9. 一个栈的输入序列是12345，则栈不同的输出序列有 种。 10. 表达式23+((12*3-2)/4+34*5/7)+108/9的后缀表达式是 。 参考答案：

1. 限制在表的一端进行插入和在另一端进行删除 先进先出 2. 栈

3. SXSSXSXX

4. 0 n+1 top[1]+1==top[2]

5.(Q->rear==Q->front) && (Q->rear!=NULL) 6. 假溢出

7. node *p=(node *)malloc(node); p->data=x; p->next=NULL; if(r) { r->next=p; r=p; } else r=f=p;

8. (rear+1) % MAXSIZE==front rear==front。 9. 14

10. 23 12 3 * 2 – 4 /34 5 * 7 / + 108 9 / +

3.3.3 判断题

1. 消除递归一定需要使用栈。

2. 栈是实现过程和函数调用所必需的结构。

3. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 4. 用递归方法设计的算法效率高。

5. 栈与队列是一种特殊的线性表。

6. 队列逻辑上是一端既能增加又能减少的线性表。 7. 循环队列通常浪费一个存储空间。 8. 循环队列也存在空间溢出问题。

9. 栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。 10. 任何一个递归过程都可以转换成非递归过程。 参考答案： 1 错误 2 正确 3 正确 4 错误 5 正确 6 错误 7 正确 8 正确 9 正确 10 正确 3.3.4 应用题

1. 什么是栈、队列？栈和队列数据结构的特点，什么情况下用到栈，什么情况下用到队列？ 2. 什么是递归程序，递归程序的优、缺点是什么，递归程序在执行时，应借助于什么来完成？

3. 在什么情况下可以利用递归来解决问题，在写递归程序时应注意什么？

4. 试证明：若借助栈由输入序列1，2，? ，n得到输出序列为p1p2?pn (它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着i

6. 简要叙述循环队列的数据结构，并写出其初始状态、队列空、队列满的队条件。

7. 利用两个栈sl,s2模拟一个队列时，如何用栈的运算实现队列的插入，删除以及判队空运算。请简述这些运算的算法思想。

8. 当过程P递归调用自身时，过程P内部定义的局部变量在P的2次调用期间是否占用同一数据区？为什么？

9. 链队列队头和队尾分别是单链表的那一端，能不能反过来表示，为什么？ 10. 有如下递归函数：

int dunno(int m) {

int value;

if (m==0) value=3;

else value=dunno(m-1)+5; return(value); }

试给出dunno(3)的结果。 参考答案： 1. 略。 2. 略。

3. 该问题必须可以被分解为和该问题具有相同逻辑结构的子问题，即具有递归性质。书写递归程序的要点如下：

⑴问题与自身的子问题具有类同的性质，被定义项在定义中的应用具有更小的尺度。 ⑵被定义项在最小尺度上有直接解。

递归算法设计的原则是用自身的简单情况来定义自身，一步比一步更简单，确定递归的控制条件非常重要。设计递归算法的方法是：

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

⑵设计递归出口，确定递归终止条件(例如求解n!时，当n=1时，n!=1)。 4. 证明：根据题意，因为i < j < k，所以输出的次序为pi, pj, pk,

因为输入序列的值是由小到大递增的，又pj

若要求pi最后输入，最先输出，则先输入的pj, pk必存在栈中，等pi入栈并立即出栈后再输出。对于pj, pk，因已存入栈中，出栈序列不可能是pj, pk，否则不符合栈“后进先出”的要求。所以不可能得到输出序列pi, pj, pk。 5. 略。

6. 将队列的数据区data[0..MAXSIZE-1]看成头尾相接的循环结构，头尾指针的关系不变，将其称为“循环队列”。具体结构参见3.1.3节中循环队列的数据结构定义。

初始状态时front==0; rear==0; 队空时front== rear；队满时(rear+1) % MAXSIZE==front。

7. 参考3.2.5节第3题。

8. 过程P内部定义的局部变量在P的2次调用期间不占用同一数据区。当递归函数调用时，应按照“后调用的先返回”的原则处理调用过程，因此递归函数之间的信息传递和控制转移必须通过栈来实现。系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就为它在栈顶分配一个存储区，而每当从一个函数退出时，就释放它的存储区。因此过程P内部定义和P的第2次调用时不再一个存储区域。

9. 链队列队头指向单链表的首结点，而队尾则是指向单链表的最后一个结点。不能够反过来，因为在队尾删除操作时，需要遍历单链表找到队尾所指向结点的前一个结点，这样处理其时间效率将受到影响。

10. dunno(3)＝dunno(2)＋5； dunno(2)＝dunno(1)＋5；

dunno(1)＝dunno(0)＋5； dunno(0)＝3；

因此，dunno(3)＝18。

3.3.5 算法设计题

1. 假设称正读和反读都相同的字符序列为“回文”，例如，“abcddcba”、 “qwerewq”是回文，“ashgash”不是回文。是写一个算法判断读入的一个以‘@’为结束符的字符序列是否为回文。

2. 设以数组se[m]存放循环队列的元素，同时设变量rear 和front分别作为队头队尾指针，且队头指针指向队头前一个位置，写出这样设计的循环队列入队出队的算法。

3. 从键盘上输入一个逆波兰表达式，用写出其求值程序。规定：逆波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔,操作符只可能有+、-、*、/四种运算。例如：234 34+2*$

4. 假设以带头结点的循环链表表示一个队列，并且只设一个队尾指针指向尾元素结点(注意不设头指针)，试写出相应的置空队、入队、出队的算法。 5. 设计一个算法判别一个算术表达式的圆括号是否正确配对。

6. 两个栈共享向量空间v[m]，它们的栈底分别设在向量的两端，每个元素占一个分量，试写出两个栈公用的栈操作算法：push(i,x)和pop(i)，i=0和1用以指示栈号。

7. 线性表中元素存放在向量A[n]中，元素是整型数。试写出递归算法求出A中的最大和最小元素。

8. 已知求两个正整数m与n的最大公因子的过程用自然语言可以表述为反复执行如下动作：第一步：若n等于零，则返回m；第二步：若m小于n，则m与n相互交换；否则，保存m，然后将n送m，将保存的m除以n的余数送n。

(1)将上述过程用递归函数表达出来(设求x除以y的余数可以用x % y 形式表示)。 (2)写出求解该递归函数的非递归算法。 提示与解答：

1. 提示：将字符序列分别输入一个栈和一个队列，然后分别执行出栈和出队操作，并比较输出的字符，如果直到栈空并且队空时，输出的字符都相同，则是回文，否则不是。

可以参考3.2.5算法设计例题第2题。

2. 提示：在入队时首先要判断队是否满，在出队时首先要判断队是否为空。所以要正确写出循环队列的队满和队空的条件。在对队首指针加1和队尾指针加1时，要做模MAXSIZE运算。

3. 分析：下面是逆波兰表达式求值的算法，在下面的算法中假设，每个表达式是合乎语法的，并且假设逆波兰表达式已被存入一个足够大的字符数组A中，且以’$’为结束字符。算法描述如下：

typedef double DataType ;

int IsNum(char c) /*判断字符是否位操作数。若是返回1，否则返回0*/ { if(c>=′0 ′ && c<=′9 ′) return (1);

else return (0); }

double postfix_exp(char *A) /*本函数返回由逆波兰表达式A表示的表达式运算结果*/ { PSeq_Starck S ;

double result,a,b,c, operand=0; ch=*A++;

S=Init_SeqStack(); /*初始化栈*/ while ( ch != ‘$’ )

{ if(IsNum(ch)) /*当前字符是数字字符，计算出操作数*/

operand=operand*10+( ch - ′0 ′);

else

{ Push_SeqStack(S,operand); /*当前字符不是数字字符，表示操作数结束,要入栈*/

if (ch!=’’) /*当前字符还不是空格字符，则是运算符，要运算*/ { Pop_SeqStack(S,&b);

Pop_SeqStack(S,&a); /*取出两个操作数*/ switch (ch) {

case ′+ ′： c=a+b ; break ;

case ′- ′： c=a-b ; break ; case ′* ′： c=a*b ; break ; case ′/ ′： c=a/b ;

}

Push_SeqStack(S, c) ; /*运算结果入栈*/

} }

ch=*A++ ;

}

GetTop_SeqStack(S, result ) ; Destroy_SeqStack(&S); return result ;

}

4. 分析：由于不设置头指针，所以要设法确定队头的位置。如图3.7所示，由于有队尾指

针rear，所以根据循环链表的结构，队头指针front=rear->next->next。队空时，rear=rear->next。

e1

? en r

(b)空队列

rearear

(a)非空队列

图3.7 带队尾指针的循环链表表示的队列

算法描述如下：

typedef struct node{

DataType data; /*每个元素数据信息*/ struct node *next; /*存放后继元素的地址*/ } LNode，*Quenue；

void SetEmpty(Quenue rear) /*置队列为空*/ { LNode *h，*front； h= rear->next； /*循环链表头结点为队列尾指针后一个结点*/ while (h!= rear) /*当前队列不空*/

{

front =h->next; /*队列头结点为循环链表头结点后一个结点*/ h->next= front ->next;

/*队列中只有一个结点,则释放后,队列将为空,所以让队尾指针指向头结点*/

if (front ==rear) rear=h；

free front; /*释放队列头结点*/ }

}

void InQuenue(Quenue rear ,DataType data) /*数据data入队列*/ { LNode *new; new=( LNode *)malloc(sizeof(LNode)); new->data=data; new->next=rear->next; /*在rear后插入新的结点*/ rear->next=new; }

int OutQuenue(Quenue rear ,DataType &data) {

LNode *head,*front; head= rear->next;

if (head== rear) /*队列为空,出队列操作失败*/ return 0;

front =head->next; /*队列头结点为循环链表头结点后一个结点*/ data= front ->data; head->next= front ->next; if (front ==rear)/*队列中只有一个结点,则释放后,将为空,所以让队尾指针指向头结点*/ rear= head; free front; /*释放队列头结点*/ return 1; }

5. 分析：该题目主要考查栈的应用。假定表达式存放在字符串数组str中，对表达式字符进行扫描，遇到左括号则进栈，遇到右括号则判栈是否空；若空，说明圆括号不配对，若不空则出栈，最后，若栈空，说明圆括号配对，否则不配对。 算法描述如下：

void pair(char str[ ]) { PSeqStack S; char ch ,ch1;

int k=0 ;

S=Init_SeqStack( );

while( ( ch=str[k])!= ′\\0 ′) /*扫描表达式，直到′\\0 ′结束*/

{ if (ch= =′( ′) Push_SeqStack(S,ch); else if(ch==′)′)

{ if (Empty_SeqStack (S))

{ printf(“圆括号不配对”)； return; }

else Pop_SeqStack(S,&ch1)； /*栈顶的左括号出栈*/ } k++;

}

if (Empty_SeqStack(S)) printf(“圆括号配对”); else printf(“圆括号不配对”); }

6. 分析：设置两个指针分别指向两个栈顶。push(i,x)，i等于0时，指针要加1，而i等于1时，指针要减1；pop(i)，i等于0时，指针要减1，而i等于1时，指针要加1。另外，要注意判空和判满。 算法描述如下： #define m 100 typedef struct {

int v[m]; /*两个栈共用的连续存储区域*/ int top0, top1; /*分别为两个栈的栈顶位置*/ }BSeqStack, *PBSeqStack;

BSeqStack S;

int push(int i, int x)

{ if (S.top0+1= = S.top1) /*栈满不能入栈*/

return 0; /* 入栈失败 */ else

{ if (i==0) /*0号栈入栈*/

{ S.top0++; /*0号栈顶位置加1*/ S.v[S.top0]=x;

return 1; /* 入栈成功 */

}else if (i==1) /*1号栈入栈*/

{ S.top1--; /*1号栈顶位置减1*/

S.v[S.top1]=x;

return 1; /* 入栈成功 */

}

} }

int pop(int i)

{ if (i==0) /*0号栈出栈*/

{ if (S.top0= = -1) /*栈空不能出栈*/

{ printf(“栈空不能出栈”);

return 0;

}

else

return S.v[S.top0--]; /*返回栈顶元素，栈顶位置减1*/

}else if (i==1) /*1号栈出栈*/

{ if (S.top1= = m) /*栈空不能出栈*/ { printf(“栈空不能出栈”);

return 0; }

else

return S.v[S.top1++]; /*返回栈顶元素，栈顶位置加1*/

}

}

7. 分析：递归终止条件为只有一个元素时，最大和最小元素就为该元素；或没有元素时，没有最大和最小元素。递归式为GetMaxMin(A(0,..n))=max/min(GetMaxMin (A(n)), GetMaxMin(A(0,..n-1)))。 算法描述如下：

void GetMaxMin(int A[], int n, int &max, int &min) { if (n==0) { /*只有一个元素时，最大和最小元素就为这个元素 */ max=A[0];

min=A[0]; }

else {

/有n+1个元素时,先获得前n个数中的最大元素max,和最小元素min*/

GetMaxMin(A, n-1, max, min);

/*如果第n+1个元素大于max,则这n+1个元素中的最大元素为max*/

if (A[n]>max) max=A[n];

/*如果第n+1个元素小于min,则这n+1个元素中的最小元素为min*/

if (A[n]

8. 分析：(1)这是求最大公因子的辗转相除法。 算法描述如下：

int gcd(int m, int n) /*求两个正整数的最大公因子的递归函数*/ { int temp;

if (n= =0 ) return m;

if (m

(2)根据3.2.2判断题第1题，这是一个尾递归函数，消除递归可以不用栈，求解该递归函数gcd (int m,int n)的非递归算法描述如下：

int gcd1(int m, int n) /*求两个正整数的最大公因子的非递归函数*/ { int temp;

if (m

m=n; n=temp; }

while (n!=0) {

temp=m;

m=n; /*除数作为下次运算的被除数*/ n=temp% n; /*余数作为下次运算的除数*/ }

return m; }

本文来源：https://www.bwwdw.com/article/y1y.html