队列 — 计算机科学
1. 核心概念与FIFO特性 ★★☆☆☆ ⏱ 3 min
所有标准队列操作都限制在两端进行。与链表或数组不同，默认情况下你不能访问或修改队列中间的元素。这个限制保证了FIFO特性得以维持。
Exam tip: 跟踪操作时始终明确标记哪一端是队首哪一端是队尾：交换二者是CIE考试中最常见的错误。
2. 标准队列操作 ★★☆☆☆ ⏱ 4 min
所有有效的队列实现都支持以下核心操作，每个操作的期望时间复杂度均为$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)
3. 常见队列实现 ★★★☆☆ ⏱ 5 min
队列最常使用两种底层结构实现，对比如下：
定长基于数组的队列
使用连续数组存储队列元素，用整数指针记录队首和队尾索引。
基于链表的队列
使用链表节点，分别用指针指向链表的队首节点和队尾节点。
循环队列是一种改进的定长数组实现，解决了删除后数组前端留下空槽无法使用的问题。当队尾索引到达数组末尾后，会环绕回数组起始位置，重复利用空槽。
Exam tip: CIE经常考察循环队列实现：记住总会留出一个空位，用于区分满队列和空队列状态。
4. 队列的应用 ★★☆☆☆ ⏱ 3 min
- **进程调度**: 操作系统使用队列按到达顺序排序等待CPU的进程
- **打印机假脱机**: 打印任务排队，第一个发送的任务第一个打印
- **广度优先搜索（BFS）**: 图遍历使用队列跟踪接下来要访问的节点
- **数据缓冲**: 队列处理异步数据传输（例如视频流，IO缓冲区）
Common Pitfalls
Why: 学习者经常混淆哪一端支持哪一种操作，破坏了FIFO特性
Why: 如果所有槽都被填满，队首等于队尾，这和空队列的条件一致，会导致逻辑错误
Why: Learners often assume elements must be shifted in array implementations, which is only true for naive non-pointer implementations
Why: 这是BFS和DFS需求的常见混淆