# 队列

> 计算机科学 · CIE A-Level 9618
> 来源: https://www.owlsprep.com/zh/study/cie-9618-u10-queues/

本子主题涵盖队列抽象数据结构、其核心FIFO原则、常见实现、标准操作和实际应用。你将学习如何跟踪和实现CIE A-Level考试题目中的队列操作。

**先修:** [线性数据结构](https://www.owlsprep.com/zh/study/cie-9618-u10-linear-data-structures/); [链表](https://www.owlsprep.com/zh/study/cie-9618-u10-linked-lists/)

## 学习目标

- 解释队列抽象数据类型的FIFO特性
- 使用数组和链表实现队列
- 跟踪标准队列操作（入队、出队、查看队首）
- 识别队列常见的计算应用和实际应用

## 核心概念与FIFO特性

**队列** — 一种遵循先进先出（FIFO）排序原则进行插入和删除的线性抽象数据类型。元素从一端（尾部/后端）添加，从另一端（头部）移除。

*记法:* Often denoted $Q$

*例:* 收银台的顾客队列：第一个加入的顾客第一个被服务。

所有标准队列操作都限制在两端进行。与链表或数组不同，默认情况下你不能访问或修改队列中间的元素。这个限制保证了FIFO特性得以维持。

**例题:** 队列初始为空。跟踪以下操作后队列的状态：Enqueue(10), Enqueue(25), Dequeue(), Enqueue(30), Peek(), Dequeue()。列出队列最终内容和Peek操作返回的值。

1. 步骤1：初始状态：空队列，队首和队尾均为空。入队(10)后：
2. Queue = $[10]$, front = 10, rear = 10
3. 步骤2：入队(25)后：25添加到队尾。
4. Queue = $[10, 25]$, front = 10, rear = 25
5. 步骤3：出队()后：10从队首被移除。
6. Queue = $[25]$, front = 25, rear = 25
7. 步骤4：入队(30)后：30添加到队尾。
8. Queue = $[25, 30]$, front = 25, rear = 30
9. 步骤5：Peek()返回队首元素的值（25），不改变队列。
10. 步骤6：出队()后：25从队首被移除。最终状态：
11. Queue = $[30]$, front = 30, rear = 30

> **考试提示:** 跟踪操作时始终明确标记哪一端是队首哪一端是队尾：交换二者是CIE考试中最常见的错误。

## 标准队列操作

所有有效的队列实现都支持以下核心操作，每个操作的期望时间复杂度均为$O(1)$：

- `enqueue(item)`: 向队列尾部添加新元素
- `dequeue()`: 从队列头部移除并返回元素
- `peek()` / `front()`: 返回队首元素的值，不将其移除
- `isEmpty()`: Return `True` if the queue has no elements, else `False`
- `isFull()`: Return `True` if the queue has no remaining space (fixed-size implementations only)

**概念自测**

测试你对核心操作特性的理解：

1. 哪个操作向队列添加新元素？

   - Dequeue
   - Enqueue
   - Peek
   - isEmpty

   *解析:* 正确：入队添加到队尾，出队从队首移除。

2. 正确实现的入队操作的时间复杂度是多少？

   - $O(1)$
   - $O(n)$
   - $O(\log n)$
   - $O(n^2)$

   *解析:* 正确：入队仅修改队尾指针，因此以常数时间运行。

**例题:** 为跟踪`frontIndex`和`rearIndex`的定长数组队列编写`isEmpty()`操作的伪代码。

1. 对于这种常见实现，当`frontIndex`等于`rearIndex`时队列为空，因为两个指针之间没有元素。
2. 该函数最终伪代码为：
3. $$\begin{algorithm}
\FUNCTION{isEmpty()}{}
\RETURN frontIndex = rearIndex
\ENDFUNCTION
\end{algorithm}$$
4. 如果你的实现跟踪单独的`elementCount`变量，等价伪代码为`RETURN elementCount = 0`。只要逻辑一致，两种写法在CIE考试中都可接受。

## 常见队列实现

**方法对比**

队列最常使用两种底层结构实现，对比如下：

- **定长基于数组的队列** — 使用连续数组存储队列元素，用整数指针记录队首和队尾索引。
  - 优点: 实现简单，队首/队尾访问为常数时间
  - 缺点: 最大长度固定，朴素线性实现会浪费内存

- **基于链表的队列** — 使用链表节点，分别用指针指向链表的队首节点和队尾节点。
  - 优点: 长度动态，不会预先分配浪费内存
  - 缺点: 节点指针带来更高的内存开销

循环队列是一种改进的定长数组实现，解决了删除后数组前端留下空槽无法使用的问题。当队尾索引到达数组末尾后，会环绕回数组起始位置，重复利用空槽。

**例题:** 一个循环队列定长为5，数组索引为0到4。当前状态：frontIndex = 2，rearIndex = 4。求入队(10)和出队操作后的新索引。

1. 步骤1：当前状态：索引4之后的位置环绕回数组起始处（循环环绕）。
2. 步骤2：入队(10)将新元素添加到索引0，因此rearIndex从4递增到0，frontIndex保持为2。
3. 步骤3：出队()移除队首索引2处的元素，因此frontIndex从2递增到3，rearIndex保持为0。
4. Final state: frontIndex = 3, rearIndex = 0

> **考试提示:** CIE经常考察循环队列实现：记住总会留出一个空位，用于区分满队列和空队列状态。

## 队列的应用

- **进程调度**: 操作系统使用队列按到达顺序排序等待CPU的进程
- **打印机假脱机**: 打印任务排队，第一个发送的任务第一个打印
- **广度优先搜索（BFS）**: 图遍历使用队列跟踪接下来要访问的节点
- **数据缓冲**: 队列处理异步数据传输（例如视频流，IO缓冲区）

**例题:** 解释为什么队列是多用户打印机假脱机的理想数据结构。

1. 打印机假脱机要求文档按照它们被打印机接收的精确顺序打印。
2. 队列的FIFO特性满足这个要求：第一个加入队列的文档第一个被处理和打印。
3. 新文档可以添加到队列尾部，同时打印机从队首处理任务，消除多用户之间的冲突。

## 常见错误

- **错误做法:** 入队/出队操作交换队首和队尾
  - 原因: 学习者经常混淆哪一端支持哪一种操作，破坏了FIFO特性
  - 正确做法: 入队添加到队尾，出队从队首移除，始终遵循FIFO顺序
- **错误做法:** 忘记循环队列需要留出一个空位来区分满/空状态
  - 原因: 如果所有槽都被填满，队首等于队尾，这和空队列的条件一致，会导致逻辑错误
  - 正确做法: 循环数组需要留出一个空位，或者单独跟踪元素数量以避免歧义
- **错误做法:** Claiming enqueue/dequeue are $O(n)$ for correctly implemented queues
  - 原因: Learners often assume elements must be shifted in array implementations, which is only true for naive non-pointer implementations
  - 正确做法: All correctly implemented queues with front/rear pointers have $O(1)$ time complexity for core operations
- **错误做法:** 深度图遍历使用队列
  - 原因: 这是BFS和DFS需求的常见混淆
  - 正确做法: BFS使用队列，DFS使用栈，分别匹配它们的FIFO/LIFO特性

## 速查表

| 特性 | 详情 |
| --- | --- |
| 排序原则 | 先进先出（FIFO） |
| 插入端 | 队尾/后端 |
| 删除端 | 队首 |
| 核心操作 | 入队、出队、Peek、isEmpty、isFull |
| 核心操作时间复杂度 | $O(1)$ |
| 常见实现 | 定长数组、循环数组、链表 |
| 核心应用 | BFS、CPU调度、打印机假脱机、缓冲 |

## 下一步

队列是CIE 9618大纲中许多高级主题都会用到的基础线性数据结构，包括图算法、操作系统调度和系统设计。队列实现和应用的考试题目经常出现在试卷1和试卷2中，因此掌握核心概念和常见实现的边界情况对于取得高分至关重要。接下来你可以学习依赖队列的相关数据结构和高级主题。

- [栈](https://www.owlsprep.com/zh/study/cie-9618-u10-stacks/)
- [树](https://www.owlsprep.com/zh/study/cie-9618-u10-trees/)
- [图](https://www.owlsprep.com/zh/study/cie-9618-u10-graphs/)

---

来自 [OwlsPrep](https://www.owlsprep.com) —— A-Level / IB / AP / IGCSE 免费学习指南，依据官方考纲编写。原页面：https://www.owlsprep.com/zh/study/cie-9618-u10-queues/