第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．消除递归不一定需要使用栈，此说法是否正确。 正确