返回目录

§3.1 队列

§3.2.1 队列的基本概念

队列也是一种 运算受限的线性表，插入限定在表的某一端进行，删除限定在表的另一端进行。允许 插入 的一端称为 队尾，允许 删除 的一端称为 队头。

§3.2.2 队列的顺序存储结构

队列的顺序存储结构简称为 顺序队，组成：

  • 一维数组 data 用于存储队列中元素
  • 变量 front 指示队头元素的前一个位置
  • 变量 rear 指示队尾元素的当前位置

队空条件：front == rear。初始化队空 front = rear = 0，不是 -1。

对于队满，为了能够充分地使用数组中的存储空间，可以把数组的前端和后端连接起来，形成一个环形的表，即把存储队列元素的表 从逻辑上看成一个环，这个环形的表叫做 循环队列 或 环形队列。

队满条件：(rear + 1) % MaxSize == front，即试探进队，若达到队头指针位置，则认为队满。在这样设置的队满条件下，队满条件成立时队中还有一个空闲单元，也就是说这样的队中最多只能进队 MaxSize - 1 个元素。

另有判断队满的方法：

  • 设置一个计数器 count，这样队满条件是 count == MaxSize；
  • 设置变量 flag 表示队是否可能满，是否可能空，然后仍然用 front == rear 判断。

§3.2.3 队列的链式存储结构（不重要）

队列的链式存储结构简称为 链队。采用同时 带有 队头指针 front 和 队尾指针 rear 的单链表。

初始化：创建链队结点，并置该结点的 rear = front = nullptr。销毁：先像释放单链表一样释放队中所有数据结点，然后释放链队结点 Q。

队空条件：front == nullptr；队满条件：不考虑。

§3.2.4 用队列求解迷宫问题（广度优先搜索，代码重要）

栈和队列都是存放多个数据的容器。通常用于存放临时数据：

如果先放入的数据先处理，则使用队列；如果后放入的数据先处理，则使用栈。

解决迷宫问题使用的队列 不是循环队列。