1.4　栈和队列

考点1　栈及其基本运算

（1）栈的定义

栈是限定在一端进行插入与删除的线性表。

（2）栈的特点：

①允许插入和删除的一端称为栈顶，不允许插入与删除的一端称为栈底。栈顶元素总是最后被插入的元素，也是最先被删除的元素；栈底元素总是最先被插入也是最后被删除的。

②栈遵循“先进后出”或“后进先出”的原则，具有记忆功能。

③通常用指针top来指示栈顶位置，用指针bottom指向栈底，栈顶指针top动态反映了栈中元素的变化情况。

（3）栈的顺序存储及其运算

在栈的顺序存储空间S（1：m）中，top＝0表示栈空；top＝m表示栈满。

栈的三种运算：

①入栈运算

入栈运算是指在栈顶位置插入一个新元素。操作过程如下：

a．首先判断栈顶指针是否已经指向存储空间的最后一个位置。如果是，则说明栈空间已满，不可能再进行入栈操作（这种情况称为栈“上溢”错误），算法结束。

b．然后将栈顶指针进一（即top加1）。

c．最后将新元素x插入栈顶指针指向的位置。

②退栈运算

退栈运算是指取出栈顶元素并赋给一个指定的变量。操作过程如下：

a．首先判断栈顶指针是否为0。如果是，则说明栈空，不可能进行退栈操作（这种情况称为栈“下溢”错误），算法结束。

b．然后将栈顶元素（栈顶指针指向的元素）赋给一个指定的变量。

c．最后将栈顶指针退一（即top减1）。

③读栈顶元素

读栈顶元素是指将栈顶元素赋给一个指定的变量。操作过程如下：

a．首先判断栈顶指针是否为0。如果是，则说明栈空，读不到栈顶元素，算法结束。

b．然后将栈顶元素赋给指定的变量y。

这个运算不删除栈顶元素，只是将它的值赋给一个变量，栈顶指针不会变。

【真题演练】

1支持子程序调用的数据结构是（　　）。[2013年9月真题]

A．栈

B．树

C．队列

D．二叉树

【答案】A

【解析】在高级语言中，函数的调用是通过栈来实现的。在进行函数调用时，系统将所需的信息压入栈中，如函数的局部变量、返回值等。每个函数的状态是由函数中的局部变量、函数参数值、函数的返回值地址决定的，存储这些信息的数据区域称为活动记录，或叫做栈帧，它是运行时系统栈上分配的空间。答案选择A选项。

2下列与栈结构有关联的是（　　）。[2013年3月真题]

A．数组的定义域使用

B．操作系统的进程调度

C．函数的递归调用

D．选择结构的执行

【答案】C

【解析】函数的递归调用是指函数调用函数本身，直到满足特定条件时终止，然后从最后被递归调用处返回。递归函数是通过栈来实现的，所以调用原则和栈的实现相一致。所以递归函数是通过栈来实现的。答案选择C选项。

3设栈的顺序存储空间为S（1：50），初始状态为top=0。现经过一系列入栈与退栈运算后，top=20，则当前栈中的元素个数为（　　）。[2014年3月真题]

A．30

B．29

C．20

D．19

【答案】C

【解析】栈按照“先进后出”的原则组织数据，插入与删除操作被限制在栈顶一端进行，入栈使栈顶位置进1，退栈使栈顶退1。top=0表示栈为空，在运算过程中，指针始终指向栈顶元素。top=20，说明当前栈中有20个元素。答案选择C选项。

4一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（　　）。[2013年9月真题]

A．12345ABCDE

B．EDCBA54321

C．ABCDE12345

D．54321FDCBA

【答案】B

【解析】栈是按照“先进后出”的原则组织数据的，入栈的顺序为12345ABCDE，则依次出栈的顺序应为其逆序，即EDCBA54321。答案选择B选项。

考点2　队列及其基本运算

（1）什么是队列

队列（Queue）是指允许在一端进行插入、而在另一端进行删除的线性表。

（2）队列的特点

①允许插入的一端称为队尾，用队尾指针指向队尾元素；允许删除的一端称为队头，用排头指针指向排头元素的前一个位置。

②最先插入的元素最先被删除，最后插入的元素最后被删除，遵循“先进先出”或“后进后出”原则。

③队尾指针rear和排头指针front共同反映队列中元素变动情况。

④入队运算指只涉及队尾指针rear变化，退队运算只涉及排头指针front变化。

（3）循环队列及其运算

循环队列是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列中，用队尾指针rear指向队尾元素，用排头指针front指向排头元素的前一个位置，从排头指针front指向的后一个位置到队尾指针rear指向的位置均是队列中元素。队列空的条件是s＝0；队列满的条件是s＝1且front＝rear。

队列的两种运算

假设循环队列的初始状态为空，即：s＝0，且front＝rear＝m。

①入队运算

入队运算是指在循环队列的队尾加入一个新元素。操作过程如下：

a．首先判断循环队列是否满。当循环队列非空（S＝1）且队尾指针等于排头指针时，说明循环队列已满，不能进行入队运算。这种情况称为“上溢”。此时算法结束。

b．然后将队尾指针进一（即rear＝rear＋1），并当rear＝m＋1时置rear＝1。

c．最后将新元素x插入队尾指针指向的位置，并且置循环队列非空标志。

②退队运算

退队运算是指在循环队列的排头位置退出一个元素并赋给指定的变量。操作过程如下：

a．首先判断循环队列是否为空。当循环队列为空（s＝0）时，不能进行退队运算。这种情况称为“下溢”。此时算法结束。

b．然后将排头指针进一（即front＝front＋1），并当front＝m＋1时置front＝1。

c．再将排头指针指向的元素赋给指定的变量。

d．最后判断退队后循环队列是否为空。当front＝rear时置循环队列空标志（即s＝0）。

【真题演练】

1下列叙述中正确的是（　　）。[2013年9月真题]

A．栈是“先进先出”的线性表

B．队列是“先进后出”的线性表

C．循环队列是非线性结构

D．有序线性表既可以采用顺序存储结构，也可以采用链式存储结构

【答案】D

【解析】有序的线性表既可采用顺序存储结构，也可以采用链式存储结构。A项错误，栈是“先进后出”的线性表；B项错误，队列是“先进先出”的线性表；C项错误，循环队列是线性结构的，有序的线性表既可采用顺序存储结构，也可采用链式存储结构。答案选择D选项。

2下列叙述中正确的是（　　）。[2014年3月真题]

A．循环队列是顺序存储结构

B．循环队列是链式存储结构

C．循环队列是非线性结构

D．循环队列的插入运算不会发生溢出现象

【答案】A

【解析】A项正确，B项错误，循环队列是一种顺序存储结构的队列；C项错误，线性结构是一个非空序列：除第一个元素外，每个元素，有且只有一个前件；除最后一个元素外，每个元素有且只有一个后件，所以循环队列是线性结构；D项错误，当循环队列的元素个数等于存储长度后，入队会发生溢出现象，覆盖前面的数据。答案选择A选项。

3对于循环队列，下列叙述中正确的是（　　）。[2013年9月真题]

A．队头指针是固定不变的

B．队头指针一定大于队尾指针

C．队头指针一定小于队尾指针

D．队头指针可以大于队尾指针，也可以小于队尾指针

【答案】D

【解析】在循环队列中，用队尾指针（rear）指向队列中的队尾元素，用队头指针（front）指向队头元素的前一个位置。在循环队列中，一般情况下rear>front，当存储空间的最后一个位置被使用，而新元素要入队时，如果存储空间的第一个位置空闲，便可将元素插入到第一个位置，此时存储空间的第一个位置作为队尾，便有front>rear。所以答案选择D选项。

4下列叙述中正确的是（　　）。[2013年9月真题]

A．循环队列有队头和队尾两个指针，因此，循环队列是非线性结构

B．在循环队列中，只需要队头指针就能反映队列中元索的动态变化情况

C．在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况

D．循环队列中元素的个数是由队头指针和队尾指针共同决定

【答案】D

【解析】循环队列是顺序存储的线性结构，是队列常采用的形式，故A项错误。循环队列中的元素是动态变化的：每一次入队，队尾指针就进一；每一次出队，队头指针就进一，所以队头指针和队尾指针一起反映了队列中元素的动态变化情况，BC两项错误。从队头指针指向的后一个位置与队尾指针指向的位置之间的元素即为队列中所有的元素，答案选择D选项。