第 6 课 - 队列 (Queue)

课程：数据结构与算法 所属模块：基础概念难度：Beginner 标签：queue, enqueue, dequeue, fifo 上一课：栈 (Stack) 下一课：双端队列 (Deque)

1. 学习目标

通过本节课的学习，你将能够：

理解队列（Queue）数据结构的“先进先出”（FIFO）原则。
掌握队列的两个核心操作：入队（enqueue）和 出队（dequeue）。
运用 Python 语言实现一个基础的队列。
识别队列在现实世界和计算机科学中的典型应用场景。

2. 核心概念

想象一下你在超市结账时的队伍：第一个排进队伍的人，会第一个被收银员服务并离开。这种行为模式就是 先进先出 (First-In, First-Out, FIFO)。

队列是一种遵循 FIFO 原则的线性数据结构。

前端（Front）：队伍的最前面，等待被处理（出队）的元素所在的位置。
后端（Rear）：队伍的最后面，新加入（入队）的元素所在的位置。

两个核心操作：

入队（Enqueue）：将一个新元素添加到队列的后端。
出队（Dequeue）：从队列的前端移除并返回一个元素。

下图展示了一个队列的操作流程：

初始队列: [ ] (空队列)
入队1: [1]
入队2: [1, 2]
入队3: [1, 2, 3]
出队 (返回1): [2, 3]
出队 (返回2): [3]

3. 代码示例

下面我们用 Python 来实现一个简单的队列。最直观的方式是使用列表（List）来模拟队列。

class SimpleQueue:
    def __init__(self):
        """初始化一个空队列"""
        self.items = []

    def is_empty(self):
        """检查队列是否为空"""
        return len(self.items) == 0

    def enqueue(self, item):
        """将元素item添加到队列后端（入队）"""
        self.items.append(item)
        print(f"入队: {item} | 当前队列: {self.items}")

    def dequeue(self):
        """从队列前端移除并返回元素（出队）"""
        if self.is_empty():
            raise IndexError("队列为空，无法出队")
        # 列表的pop(0)操作会移除并返回第一个元素，符合队列的FIFO原则
        removed_item = self.items.pop(0)
        print(f"出队: {removed_item} | 当前队列: {self.items}")
        return removed_item

    def peek(self):
        """查看队列前端的元素，但不移除"""
        if self.is_empty():
            raise IndexError("队列为空")
        return self.items[0]

    def size(self):
        """返回队列中元素的数量"""
        return len(self.items)

# --- 使用示例 ---
if __name__ == "__main__":
    # 创建一个队列实例
    my_queue = SimpleQueue()
    
    # 模拟排队买票
    my_queue.enqueue("顾客A")
    my_queue.enqueue("顾客B")
    my_queue.enqueue("顾客C")
    
    print(f"\n队列最前面的顾客是: {my_queue.peek()}")
    print(f"队列中有 {my_queue.size()} 位顾客\n")
    
    # 开始服务（出队）
    my_queue.dequeue()  # 服务顾客A
    my_queue.dequeue()  # 服务顾客B
    
    # 再来一位新顾客
    my_queue.enqueue("顾客D")
    
    print(f"\n最终队列: {my_queue.items}")

输出：

入队: 顾客A | 当前队列: ['顾客A']
入队: 顾客B | 当前队列: ['顾客A', '顾客B']
入队: 顾客C | 当前队列: ['顾客A', '顾客B', '顾客C']

队列最前面的顾客是: 顾客A
队列中有 3 位顾客

出队: 顾客A | 当前队列: ['顾客B', '顾客C']
出队: 顾客B | 当前队列: ['顾客C']
入队: 顾客D | 当前队列: ['顾客C', '顾客D']

最终队列: ['顾客C', '顾客D']

重要提示：使用Python列表的 pop(0) 来实现出队，在队列很大时效率较低（因为需要移动所有后续元素）。Python 标准库 collections 模块提供了一个高效的双端队列 deque，它的 popleft() 操作非常高效。下面是使用 deque 的简化版：

from collections import deque

# 使用deque可以更高效地实现队列
queue_deque = deque()
queue_deque.append("任务1") # 入队 (后端)
queue_deque.append("任务2")
print(queue_deque)       # deque(['任务1', '任务2'])
first_item = queue_deque.popleft() # 出队 (前端)
print(first_item)        # 输出: 任务1
print(queue_deque)       # deque(['任务2'])

4. 实践练习

练习 1：基本队列操作

要求：创建一个队列，依次入队元素 [10, 20, 30]。然后进行两次出队操作，最后将结果列表打印出来。
预期输出：[30]

练习 2：撤销功能（结合栈）

要求：假设你正在设计一个文字处理软件的“撤销”功能。最近的操作应该最先被撤销。请使用一个队列来存储用户输入的句子（如 ["输入: Hello", "输入: World", "删除: World"]），再使用一个栈（回顾上一课）来模拟撤销操作，将队列中的句子依次压入栈中，再弹出栈顶元素并打印，模拟撤销最近一条操作。
预期输出：撤销操作: 删除: World

练习 3：打印机任务队列

要求：模拟一个简单的打印机任务队列。创建一个包含3个打印任务的队列（任务名为 "文档A", "文档B", "文档C"）。编写一个循环，只要队列不为空，就执行“打印”（即出队）操作，并打印出正在打印的任务名称。

预期输出：

正在打印: 文档A
正在打印: 文档B
正在打印: 文档C
所有任务已完成。

5. 常见错误

忘记检查空队列：在执行 dequeue() 或 peek() 操作前，必须先检查队列是否为空 (is_empty())，否则会导致 IndexError。
混淆入队/出队方向：初学者容易在 enqueue 时用 insert(0, item)，或在 dequeue 时用 pop()。这会导致队列变成“先进后出”（FILO），违背了队列的 FIFO 本质。记住：队尾进，队头出。
性能误区：使用列表的 pop(0) 作为出队操作在数据量小时没问题，但要知道其底层实现的局限性。在生产环境或处理大数据时，应优先使用 collections.deque。

6. 小结

本节课我们学习了队列这一基础数据结构：

核心原则：先进先出 (FIFO)，像排队一样。
关键操作：
- 入队 (Enqueue)：将元素添加到队列的后端。
- 出队 (Dequeue)：从队列的前端移除元素。
典型应用：任务调度（如操作系统进程、打印任务）、消息传递（如消息队列）、广度优先搜索 (BFS) 算法、缓冲区（如键盘输入缓冲区）。
实现选择：对于教学和简单场景，列表可以清晰地演示原理。对于性能要求高的实际应用，collections.deque 是更佳选择。

理解队列及其 FIFO 特性，是掌握后续更复杂数据结构（如优先队列）和算法（如图算法）的重要一步。下一课我们将学习双端队列 (Deque)，它允许从队列的两端进行插入和删除，是队列和栈的灵活结合体。

练习编辑器

rust