学习指南

队列

计算机科学· 第10单元：数据类型与结构· 15 分钟阅读

1. 核心概念与FIFO特性★★☆☆☆⏱ 3 min

📘 定义

队列

Often denoted

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

例:

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

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

📐 例题

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

  1. 1

    步骤1：初始状态：空队列，队首和队尾均为空。入队(10)后：

  2. 2

    Queue = , front = 10, rear = 10

  3. 3

    步骤2：入队(25)后：25添加到队尾。

  4. 4

    Queue = , front = 10, rear = 25

  5. 5

    步骤3：出队()后：10从队首被移除。

  6. 6

    Queue = , front = 25, rear = 25

  7. 7

    步骤4：入队(30)后：30添加到队尾。

  8. 8

    Queue = , front = 25, rear = 30

  9. 9

    步骤5：Peek()返回队首元素的值（25），不改变队列。

  10. 10

    步骤6：出队()后：25从队首被移除。最终状态：

  11. 11

    Queue = , front = 30, rear = 30

Exam tip:

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

2. 标准队列操作★★☆☆☆⏱ 4 min

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

  • 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

    显示答案
    Enqueue —

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

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

    显示答案
    $O(1)$ —

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

📐 例题

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

  1. 1

    对于这种常见实现，当frontIndex等于rearIndex时队列为空，因为两个指针之间没有元素。

  2. 2

    该函数最终伪代码为：

  3. 3
    \begin{algorithm} \FUNCTION{isEmpty()}{} \RETURN frontIndex = rearIndex \ENDFUNCTION \end{algorithm}
  4. 4

    如果你的实现跟踪单独的elementCount变量，等价伪代码为RETURN elementCount = 0。只要逻辑一致，两种写法在CIE考试中都可接受。

3. 常见队列实现★★★☆☆⏱ 5 min

方法对比

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

定长基于数组的队列

使用连续数组存储队列元素，用整数指针记录队首和队尾索引。

+ 优点: 实现简单，队首/队尾访问为常数时间

− 缺点: 最大长度固定，朴素线性实现会浪费内存

基于链表的队列

使用链表节点，分别用指针指向链表的队首节点和队尾节点。

+ 优点: 长度动态，不会预先分配浪费内存

− 缺点: 节点指针带来更高的内存开销

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

📐 例题

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

  1. 1

    步骤1：当前状态：索引4之后的位置环绕回数组起始处（循环环绕）。

  2. 2

    步骤2：入队(10)将新元素添加到索引0，因此rearIndex从4递增到0，frontIndex保持为2。

  3. 3

    步骤3：出队()移除队首索引2处的元素，因此frontIndex从2递增到3，rearIndex保持为0。

  4. 4

    Final state: frontIndex = 3, rearIndex = 0

Exam tip:

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

4. 队列的应用★★☆☆☆⏱ 3 min

  • 进程调度: 操作系统使用队列按到达顺序排序等待CPU的进程

  • 打印机假脱机: 打印任务排队，第一个发送的任务第一个打印

  • 广度优先搜索（BFS）: 图遍历使用队列跟踪接下来要访问的节点

  • 数据缓冲: 队列处理异步数据传输（例如视频流，IO缓冲区）

📐 例题

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

  1. 1

    打印机假脱机要求文档按照它们被打印机接收的精确顺序打印。

  2. 2

    队列的FIFO特性满足这个要求：第一个加入队列的文档第一个被处理和打印。

  3. 3

    新文档可以添加到队列尾部，同时打印机从队首处理任务，消除多用户之间的冲突。

5. 常见陷阱

错误做法:

入队/出队操作交换队首和队尾

原因:

学习者经常混淆哪一端支持哪一种操作，破坏了FIFO特性

正确做法:

入队添加到队尾，出队从队首移除，始终遵循FIFO顺序

错误做法:

忘记循环队列需要留出一个空位来区分满/空状态

原因:

如果所有槽都被填满，队首等于队尾，这和空队列的条件一致，会导致逻辑错误

正确做法:

循环数组需要留出一个空位，或者单独跟踪元素数量以避免歧义

错误做法:

Claiming enqueue/dequeue are 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 time complexity for core operations

错误做法:

深度图遍历使用队列

原因:

这是BFS和DFS需求的常见混淆

正确做法:

BFS使用队列，DFS使用栈，分别匹配它们的FIFO/LIFO特性

6. 速查表

特性

详情

排序原则

先进先出（FIFO）

插入端

队尾/后端

删除端

队首

核心操作

入队、出队、Peek、isEmpty、isFull

核心操作时间复杂度

常见实现

定长数组、循环数组、链表

核心应用

BFS、CPU调度、打印机假脱机、缓冲

7. 常见问题

栈和队列的核心区别是什么？

栈遵循**LIFO（后进先出）顺序，最后添加的元素会先被移除。队列遵循FIFO（先进先出）**顺序，最早添加的元素会先被移除。

真题中的出现

AI 根据考纲规律估算的考点位置,请对照官方真题核实准确性。仅作复习重点参考。

  • 2022 · 1

    队列实现题目

  • 2023 · 2

    队列应用描述题目

深入阅读

下一步

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