2.2.2 栈和队列_算法设计与问题求解（第2版）：计算思维培养-QQ阅读女频青春网

上QQ阅读APP看本书，新人免费读10天

设备和账号都新为新人

2.2.2 栈和队列

1．栈

栈是一种特殊的线性表，如图2-8所示。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。进行插入和删除的一端是浮动端，通常被称为栈顶，并用一个“栈顶指针”指示；另一端是固定端，通常被称为栈底。

图2-8 顺序栈

栈具有后进先出（Last In First Out，LIFO）的特点，因此栈被称为LIFO线性表。

很多活动都具有LIFO的特点，比如：家里吃饭的碗，通常在洗干净后一个一个地摞在一起存放，在使用时，若一个一个地拿，一般先拿走最上面的那个碗，最后拿走最下面的那只碗。又如，在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取。

栈结构的基本操作包括：

☢ 初始化栈，InitStack(S)。

☢ 入栈，Push(S,item)。

☢ 出栈，Pop(S,item)。

☢ 获取栈顶元素内容，GetTop(S, item)。

☢ 判断栈是否为空，StackEmpty(S)。

类似线性表，栈也有两种存储结构（或者说两种实现方式）：顺序存储和链式存储。

（1）栈的顺序存储

栈的顺序存储是用一组连续的存储单元依次存放栈中的每个数据元素，并用起始端作为栈底。其类型定义如下：

其中，StackEntry是数据元素类型的抽象表示，其结构体的定义需要具体问题具体分析。顺序栈的基本操作伪代码描述如下。

① 初始化栈S

② 入栈

③ 出栈

④ 获取栈顶元素内容

⑤ 判断栈S是否为空

由于栈的插入和删除操作具有它的特殊性，因此用顺序存储结构表示的栈并不存在插入删除数据元素时需要移动的问题，但栈容量是固定的，无法动态扩充。若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。

（2）栈的链式存储

人们将用链式存储结构表示的栈称为链栈。链栈通常用一个无头结点的单链表表示，如图2-9所示。

图2-9 链栈

由于栈的插入删除操作只能在一端进行，而对于单链表来说，在首端插入删除结点要比尾端相对容易一些，因此我们将单链表的首端作为栈顶，即将单链表的头指针作为栈顶指针。

链栈的结点定义如下：

其中，StackEntry是数据元素类型的抽象表示，其结构体的定义需要具体问题具体分析。然后，通过指定链表的头结点得到链栈的定义：

链栈的基本操作伪代码描述如下。

① 初始化栈S

② 入栈

③ 出栈

④ 获取栈顶元素内容

⑤ 判断栈S是否空

2．队列

队列也是一种特殊的线性表，它限定插入操作在线性表的一端进行，删除操作在线性表的另一端进行，如图2-10所示。

图2-10 队列

在队列中，插入端和删除端都是浮动的。通常，插入端被称为队尾，用“队尾指针”指示；删除端被称为队头，用“队头指针”指示。显然，在队列中先插入的元素将被先删除，即具有先进先出（First In First Out，FIFO）的特性，队列也被称为FIFO线性表。

很多活动都具有FIFO的特点，比如：到医院看病，先挂号的病人先就诊；乘坐公共汽车，排在前面的乘客先上车；又如，在Windows这类多任务的操作系统环境中，每个应用程序响应一系列的“消息”，如用户点击鼠标、拖动窗口这些操作都会导致向应用程序发送消息。为此，系统将为每个应用程序创建一个队列，用来存放发送给该应用程序的所有消息，应用程序的处理过程就是不断地从队列中读取消息，并依次给予响应。

队列结构的基本操作包括：

☢ 初始化队列，InitQueue(Q)。

☢ 入队，EnQueue(Q,item)。

☢ 出队，DeQueue(Q, item)。

☢ 获取队头元素内容，GetFront(Q, item)。

☢ 判断队列是否为空，QueueEmpty(Q)。

类似栈，队列也存在顺序存储和链式存储两种方式。

（1）顺序存储队列

顺序存储队列用一组连续的存储单元依次存放队列中的每个数据元素，并指定队头（Front）和队尾（Rear）指针，如图2-11所示。