1.4　栈和队列

视频二维码（扫码观看）

一、栈及其基本运算

1什么是栈

【定义】限定在一端进行插入与删除的线性表

【说明】

①允许插入与删除的一端称为栈顶（指针top），而不允许插入与删除的另一端称为栈底（指针bottom）。

②栈是按照“先进后出”（FILO）的原则组织数据。

③栈具有记忆作用。

④往栈中插入一个元素称为入栈运算，从栈中删除一个元素（即删除栈顶元素）称为出栈运算。

图1-6　栈示意图

2栈的顺序存储及其运算

图1-7（a）是容量为10的栈顺序存储空间，栈中已有6个元素；图1-7（b）与图1-7（c）分别为入栈与退栈后的状态。

图1-7　栈在顺序存储结构下的运算

（1）入栈运算

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

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

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

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

（2）退栈运算

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

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

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

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

（3）读栈顶元素

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

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

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

【注意】这个运算不删除栈顶元素，只是将它的值赋给一个变量，因此，在这个运算中栈顶指针不会改变。

【考题】下列关于栈的叙述中正确的是（　　）。

A．在栈中只能插入数据

B．在栈中只能删除数据

C．栈是先进先出的线性表

D．栈是先进后出的线性表

E．栈是一种非线性结构

【答案】D

【解析】在栈中，只允许在栈顶一端进行插入和删除，所以A、B错误；队列是“先进先出”的线性表，栈是“先进后出”的线性表，所以C、E错误，D正确。

二、队列及其基本运算

1什么是队列

加入的元素总是插入到线性表的末尾，并且又总是从线性表的头部取出（删除）元素。这种线性表称为队列。

【说明】

①允许插入的一端称为队尾（rear），允许删除的一端称为队头（front）。

②在队列中按照“先进先出”的原则进行操作。

图1-8　具有6个元素的队列示意图

图1-9　队列运算示意图

【考题】下列关于队列的叙述中正确的是（　　）。

A．在队列中只能插入数据

B．在队列中只能删除数据

C．队列是先进先出的线性表

D．队列是先进后出的线性表

【答案】C

【解析】在队列中，只允许在一端进行插入，在另一端进行删除，所以A、B错误；队列是“先进先出”的线性表，栈是“先进后出”的线性表，所以D错误，选择C。

2循环队列及其运算

【定义】循环队列是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。

图1-10　循环队列存储空间示意图

用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置。

在实际使用循环队列时，为了能区分队列满还是队列空，通常还需增加一个标志s，s值的定义如下：

由此可以得出队列空与队列满的条件如下：

队列空的条件为s＝0；

队列满的条件为s＝1且front＝rear。

图1-11　循环队列运算示意图

（1）入队运算

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

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

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

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

（2）退队运算

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

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

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

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

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

【考题】设循环队列为Q（1：m），其初始状态为front＝rear＝m。经过一系列入队与退队运算后，front＝30，rear＝10。现要在该循环队列中作顺序查找，最坏情况下需要比较的次数为（　　）。

A．19

B．20

C．m－19

D．m－20

【答案】D

【解析】在该循环队列中作顺序查找，最坏情况下需要比较的次数，实际上就是求循环队列中元素的个数。元素的个数＝（rear－front＋m）mod m＝（10－30＋m） mod m＝m－20，选项D正确。