Linux环境下的C语言编程（三十八）

一、队列的概念

1. 先进先出（FIFO）

队列遵循FIFO原则，这是队列最基本的特性。

特征为

• 先来的人先服务：最早加入队列的元素最早被处理

• 保持顺序不变：元素的出队顺序完全由入队顺序决定

2. 线性结构

队列是一种线性数据结构，元素按照严格的线性顺序排列，每个元素最多有一个直接前驱和一个直接后继。

3. 操作受限的访问

与数组可以随机访问不同，队列对元素的访问有严格限制：

• 只能从一端（队头）删除元素

• 只能从另一端（队尾）添加元素

• 不能直接访问或修改队列中间的元素

4. 动态增长与收缩

队列的大小在运行时动态变化：

• 入队时增加元素，队列变长

• 出队时移除元素，队列变短

• 队列可能为空，也可能达到最大容量

二、队列的抽象图示

1. 队列的基本结构

入队方向 (Enqueue) → [][][][][][] ← 出队方向 (Dequeue) ↑ ↑ 队尾 队头 (Rear) (Front)

图示说明：

• 水平方向表示队列，左边是队尾（插入端），右边是队头（删除端）

• 新元素总是从队尾加入

• 元素总是从队头离开

• 箭头方向表示数据的流动方向

2. 队列操作动态演示

初始状态（空队列）：

队尾 → | | ← 队头 空队列

步骤1：元素A入队

队尾 → | A | ← 队头 队头/队尾都指向A

步骤2：元素B入队

队尾 → | B | A | ← 队头 ↑ ↑ 队尾 队头

步骤3：元素C入队

队尾 → | C | B | A | ← 队头 ↑ ↑ 队尾 队头

步骤4：元素A出队

队尾 → | C | B | | ← 队头 ↑ ↑ 队尾 队头 （元素A已出队）

步骤5：元素D入队

队尾 → | D | C | B | | ← 队头 ↑ ↑ 队尾 队头

3. 循环队列的抽象图示

当使用数组实现队列时，常用循环队列来解决空间浪费问题：

初始状态：

索引: 0 1 2 3 4 [ ] [ ] [ ] [ ] [ ] ↑ ↑ front rear (都指向0)

入队A、B、C后：

索引: 0 1 2 3 4 [A] [B] [C] [ ] [ ] ↑ ↑ front rear

出队A后：

索引: 0 1 2 3 4 [ ] [B] [C] [ ] [ ] ↑ ↑ front rear

入队D、E后（rear绕回起点）：

索引: 0 1 2 3 4 [E] [B] [C] [D] [ ] ↑ ↑ rear front （rear在front前面表示队列已满或循环）