Queues

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

在这一章中，我们要探讨计算机科学中最贴近生活的资料结构之一：队列 (Queue)。如果你曾经在排队买咖啡，或是等候打印机打印你的作业，那么你已经完全理解队列是如何运作的了！我们将一起看看电脑如何处理这些资料“队伍”，让一切保持井然有序且公平。

1. 什么是队列？

队列是一种抽象资料类型 (Abstract Data Type, ADT)，它遵循先进先出 (First-In, First-Out, FIFO) 的原则。这意味着最先进入队列的资料，也会最先被移出。想像它就像电影院的排队队伍：最早到的人，就是第一个买到票的人。

核心术语：

• 前端 (Front 或 Head)：队列中移除项目的位置。
• 后端 (Rear 或 Tail)：队列中加入新项目的位置。

现实生活例子：“打印队列”。当五个人同时发送文件到打印机时，打印机会先处理第一份收到的文件，然后才处理第二份。这既公平又合乎逻辑！

重点笔记：队列就是 FIFO。先进者，先出！

2. 静态与动态队列

在深入了解不同类型的队列之前，我们需要先了解它们是如何在电脑内存中建立的。别担心这些名词听起来很深奥；它们的区别其实非常简单！

静态资料结构 (Static Data Structures)

静态队列的大小是固定的，在程序编写时就已经决定。它通常使用数组 (Array) 来实现。
• 优点：内存是预先分配好的，所以程序在执行时不需要花时间“寻找”额外的内存空间。
• 缺点：如果空间用完了，你就不能再加入新项目（这称为溢出，Overflow）。此外，如果队列大部分是空的，内存空间就会被浪费。

动态资料结构 (Dynamic Data Structures)

动态队列可以在程序执行时根据需求扩展或缩减大小。它通常使用指针 (Pointers) 来实现。
• 优点：它只使用真正需要的内存量。
• 缺点：编写程序会较为复杂，而且如果整台电脑的 RAM 用尽，可能会导致系统崩溃（堆溢出，Heap overflow）。

记忆小撇步：Static (静态) 保持 Same (相同) 大小。Dynamic (动态) 则会 Develop (变化) 大小。

3. 线性队列 (Linear Queues)

线性队列是最简单的版本。它就像一条排成直线的队伍。当有新项目加入时，后端 (Rear) 指针向后移动；当项目移除时，前端 (Front) 指针向后移动。

问题所在：想像一个由 5 个空间组成的数组建立的线性队列。你加入了 5 个项目，然后移除了 3 个。即使前端现在有 3 个空位，后端 (Rear) 指针依然停在数组末端！电脑会误以为队列已满。这造成了严重的空间浪费。

快速回顾：线性队列很容易理解，但如果我们不将数据向前移动（这很慢）或使用更好的结构，它会变得非常“占空间”。

4. 环状队列 (Circular Queues)

为了解决线性队列的“浪费空间”问题，我们可以使用环状队列。想像数组的末端被“粘”回开头，形成一个圆圈。

当 后端 (Rear) 指针到达数组的最后一个索引时，下一个加入的项目如果发现第一个索引（索引 0）是空的，就会绕回到开头。

运算原理：

我们使用模数 (Modulo) 运算符 \( \% \) 来计算下一个位置。如果数组大小为 \( 5 \)，计算下一个位置的公式为：
新位置 = (目前位置 + 1) MOD 5

你知道吗？环状队列被广泛用于“缓冲区 (Buffers)”，例如 YouTube 视频载入（缓冲）时。它会不断重复使用同一块内存！

重点笔记：环状队列比线性队列更节省空间，因为它们可以“绕圈”使用空间。

5. 优先队列 (Priority Queues)

有时候，“先到先得”并不是最好的方式。在优先队列中，项目是根据其重要性而非到达先后顺序来排列的。

类比：医院的急诊室 (A&E)。如果一个人因为轻微擦伤走进来，但随后有人因腿部骨折送医，腿部骨折的人会优先得到诊治。他们拥有更高的优先级。

• 较高优先级的项目会被移到前端。
• 如果两个项目优先级相同，则遵循标准的 FIFO 原则。

6. 基本队列操作

在考试中，你可能会被要求描述如何对队列执行这四项基本操作。别被名称吓到了；它们只是“加入”、“移除”、“检查是否为空？”和“检查是否已满？”的专业术语。

1. Enqueue（加入项目）

步骤 1：检查队列是否已满（避免溢出，Overflow）。
步骤 2：如果没满，将 后端 (Rear) 指针移动到下一个空位。
步骤 3：在 后端 (Rear) 位置插入资料。

2. Dequeue（移除项目）

步骤 1：检查队列是否为空（避免下溢，Underflow）。
步骤 2：复制 前端 (Front) 位置的资料。
步骤 3：将 前端 (Front) 指针移动到下一个项目。

3. 检查队列是否为空

在许多实现中，如果 前端 (Front) 和 后端 (Rear) 指针处于相同位置（或者独立的计数变量为 0），则队列为空。

4. 检查队列是否已满

如果 后端 (Rear) 指针位于最后一个可用位置（在环状队列中，则需判断它后面的空间是否已被 前端 (Front) 占用），则队列已满。

常见错误：当你执行 Dequeue（移除项目）时，资料其实还留在内存插槽中！我们只是移动了 前端 (Front) 指针，让电脑“忽略”该资料。只有当新的资料写入并覆盖它时，该资料才算真正被“删除”。

总结检查清单

• 你能定义 FIFO 吗？（先进先出）
• 你知道静态与动态之间的区别吗？
• 你能解释为什么环状队列比线性队列更好吗？
• 你记得优先队列是基于重要性来排序的吗？
• 你能列出 Enqueue 和 Dequeue 的步骤吗？

如果一开始觉得有点难也不要担心！只要在脑海中保持“超市排队”的类比，逻辑自然就会通了。