Queues

欢迎来到队列（Queue）的世界！

你好！本章我们将深入探讨队列 (Queue)，这是计算机科学中最基础且最有用的数据结构之一。如果你有过排队等公交或买咖啡的经历，那你其实已经理解了队列的核心概念！

队列之所以必不可少，是因为它们能以高度受控、有序的方式管理进程和数据流。我们将一起探索队列的工作原理、必须遵循的特定规则，以及如何在代码中高效地实现它们，同时还会解决一些常见的实现难题。

3.2.3 理解队列数据结构

核心原则：FIFO（先进先出）

队列最重要的规则就是它的处理策略：FIFO，即 First-In, First-Out（先进先出）。

类比： 想象一下超市排队结账的场景。排在队首的人总是第一个被服务并离开队列的。新的元素（人）总是从队尾加入，而元素总是从队首被移除。

这种严格的排序机制定义了队列，也将它与其他结构（如栈，即后进先出，LIFO）区分开来。

关键要点：FIFO 规则

数据进入队列的顺序，正是它离开队列的顺序。

队列的基本操作

队列需要特定的方法（操作）来管理其内容。在处理队列时，我们使用专门的术语来表示数据的添加和移除。

1. 入队 (Enqueue)

入队 (Enqueue) 是用于向队列中添加元素的操作。

• 元素放在哪里？它总是被添加到队列的 队尾 (Rear/Back)。
• 在具体实现中，这通常涉及更新一个指针或索引（通常称为 队尾指针/Rear pointer），使其指向新的最后一个元素。

2. 出队 (Dequeue)

出队 (Dequeue) 是用于从队列中移除元素的操作。

• 从哪里移除元素？它总是从队列的 队首 (Front) 被移除。
• 出队操作会返回被移除元素的值。
• 在具体实现中，这涉及更新 队首指针 (Front pointer)，使其指向队列中新的第一个元素。

常见错误警示： 同学们经常搞混这两个术语。记住：“E”代表 Enqueue (Enter/进入) 到队尾，“D”代表 Dequeue (Depart/离开) 从队首。

描述队列的应用场景

每当资源需要公平且顺序地处理，确保没有任何请求被无限期搁置或忽略时，就会使用队列。

当你需要以下功能时，就应该使用队列数据结构：

• 任务调度： 操作系统 (OS) 管理多个等待 CPU 处理的任务或进程。队列确保最先申请 CPU 时间的任务最先获得资源。
• 输入/输出缓冲 (I/O Buffering)： 当数据传输时（例如流媒体播放或将文件发送到打印机），数据会存储在缓冲区（即队列）中，以处理处理速度上的差异。数据必须按照到达的顺序进行处理。
• 模拟： 对现实世界系统进行建模，如交通流量、客户服务排队或制造流水线。

你知道吗？

“打印队列”是队列数据结构在软件应用中的完美例子。第一个发送给打印机的文档，就是第一个被打印出来的文档。

使用一维数组实现队列

虽然某些编程语言提供了内置的队列库（你应该有使用它们的经验！），但了解如何从零开始构建队列至关重要，这通常使用 一维数组 来实现。

我们在数组内部使用两个主要指针（或索引）来管理队列：

• 队首 (Front)： 指向第一个元素（下一次出队发生的地方）。
• 队尾 (Rear)： 指向最后一个元素（下一次入队发生的地方）。

线性队列的实现

在简单的 线性队列 (Linear Queue) 中，执行入队时，队尾指针加 1；执行出队时，队首指针加 1。

线性队列的问题：

想象一个大小为 5 的数组。如果我们添加了 5 个元素（填满数组），然后移除了 4 个元素，此时队首指针位于索引 4，而队尾指针位于索引 5。前 4 个槽位（索引 0 到 3）现在虽然是空的，但我们却无法添加新元素，因为队尾指针已经到达了数组的末尾。这种做法效率低下，会导致数组开头产生 空间浪费。

解决方案：循环队列

循环队列 (Circular Queue) 通过允许指针（队首和队尾）在到达末尾时“绕回”数组的开头，从而解决了线性队列的问题。

类比： 想象数组是一个甜甜圈或环。当队尾指针到达最后一块时，下一块又是开头的第一块（如果是空的话）。

循环队列如何工作（绕回机制）

为了实现指针的绕回，我们通常使用 模运算 (MOD)。

如果数组大小为 \(N\)，那么在更新指针（假设为 P）时：

新 \(P\) = (\(P\) + 1) MOD \(N\)

如果 \(N\) = 10，且队尾位于索引 9，则 (9 + 1) MOD 10 = 0。指针绕回到了索引 0。这最大限度地利用了固定的数组空间。

测试队列状态：空还是满？

使用数组实现时（无论是线性的还是循环的），在执行操作前，我们必须始终检查队列的状态，以避免错误（例如试图从空队列中出队）。

1. 测试队列是否为空

如果队首和队尾指针指向同一个位置，说明它们之间没有存储任何元素，此时队列为空。

• 判空规则： 当 队首 = 队尾 时，队列为空。
• 注意： 有时初始化队列时，队首和队尾会被设为 sentinel 值（如 -1 或 0），但在使用过程中，判断为空的主要标志是它们再次汇合。

2. 测试队列是否已满（对于循环数组至关重要）

判断循环队列是否已满更具挑战性，因为 队首 = 队尾 也是判断“空”的条件。为了区分已满和为空，数组实现通常会保留一个永久不使用的槽位。

当队尾指针的下一个位置是队首指针时，队列被视为 已满。

• 判满规则： 当 (队尾 + 1) MOD N = 队首 时（其中 N 是数组大小），队列已满。

这一规则确保了队首和队尾之间始终至少留有一个空位，从而让算法能准确识别队列是空，还是已经完全填满。

如果循环队列的数学逻辑起初看起来很复杂，不必担心。试着用一个小数组（大小为 5 或 6）练习追踪指针，重点观察到达最大索引时会发生什么，MOD 运算符的使用很快就会变得清晰易懂！

请记住： 你还应该积累使用标准编程语言库中提供的内置队列数据结构的经验，因为它们已经为你处理了循环分配和指针管理的复杂细节！