考点4 栈和队列

1.栈及其基本运算

（1）栈的基本概念。

栈实际上也是线性表，只不过是一种特殊的线性表。在这种特殊的线性表中，其插入运算与删除运算都只在线性表的一端进行。

在栈中，允许插入与删除的一端称为栈顶（top），另一端称为栈底（bottom）。若栈中没有元素称为空栈，栈也被称为“先进后出”表，或“后进先出”表。

（2）栈的特点。

根据栈的上述定义，栈具有以下特点。

●栈顶元素总是最后被插入的元素，也是最早被删除的元素。

●栈底元素总是最早被插入的元素，也是最后才能被删除的元素。

●栈具有记忆作用。

●在顺序存储结构下，栈的插入和删除运算都不需要移动表中其他数据元素。

●栈顶指针top动态反映了栈中元素的变化情况。

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

栈的状态如图1.1所示。

根据栈的状态，可以得知栈的基本运算有以下3种。

●入栈运算：在栈顶位置插入一个新元素。

●退栈运算：取出栈顶元素并赋给一个指定的变量。

●读栈顶元素：将栈顶元素赋给一个指定的变量。

2.队列及其基本运算

（1）队列的基本概念。

队列是指允许在一端进行插入，而在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个称为尾指针（rear）的指针指向队尾元素；允许删除的一端称为排头，通常用一个头指针（front）指向头元素的前一个位置。

因此，队列又称为“先进先出”（FIFO-First In First Out）的线性表。插入元素称为入队运算，删除元素称为退队运算。

队列的基本结构如图1.2所示。

（2）循环队列及其运算。

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

真考链接

考核概率为90%，此部分属于必考知识点。该考点较为基础，考生要理解栈和队列的概念和特点，掌握栈和队列的运算。

在循环队列中，用尾指针（rear）指向队列的尾元素，用头指针（front）指向头元素的前一个位置。因此，从头指针（front）指向的后一个位置，直到尾指针（rear）指向的位置之间所有的元素均为队列中的元素。循环队列的初始状态为空，即rear=front。

循环队列的基本运算主要有两种：入队运算与退队运算。

●入队运算是指在循环队列的队尾加入一个新的元素。

●退队运算是指在循环队列的排头位置退出一个元素，并赋给指定的变量。

小提示

栈是按照“先进后出”或“后进先出”的原则组织数据，而队列是按照“先进先出”或“后进后出”的原则组织数据。这就是栈和队列的不同。

真题精选

【例1】下列对队列的叙述正确的是______。

A）队列属于非线性表

B）队列按“先进后出”原则组织数据

C）队列在队尾删除数据

D）队列按“先进先出”原则组织数据

【答案】D

【解析】队列是一种特殊的线性表，它只能在一端进行插入，在另一端进行删除。允许插入的一端称为队尾，允许删除的另一端称为队头。队列又称为“先进先出”或“后进后出”的线性表，体现了“先到先服务”的原则。

【例2】下列关于栈的描述正确的是______。

A）在栈中只能插入元素而不能删除元素

B）在栈中只能删除元素而不能插入元素

C）栈是特殊的线性表，只能在一端插入或删除元素

D）栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素

【答案】C

【解析】栈是一种特殊的线性表。在这种特殊的线性表中，其插入和删除操作只能在线性表的一端进行。