sko.kr

算法 - 9. 队列

algorithmsdata-structuresqueuelinked-list
By sko•10/7/2025•11 min read

何时使用队列

当需要按先进先出（FIFO）顺序处理项目时使用队列 - 第一个添加的项目是第一个被移除的。虽然最常用于任务调度，但在以下情况下是必不可少的：

  • 广度优先搜索（BFS）（经典用例）
  • 任务调度（按到达顺序处理）
  • 消息队列系统（维护消息顺序）
  • 打印缓冲区（按提交顺序处理打印作业）
  • 呼叫中心系统（按接收顺序处理电话）
  • 任何需要公平排序的问题，其中项目必须按到达顺序处理

示例问题

客户服务系统：咖啡店需要按照顾客到达的顺序为他们服务。顾客在不同时间加入队列，必须公平地接受服务。

  • 顾客A在上午9:00到达
  • 顾客B在上午9:02到达
  • 顾客C在上午9:05到达
  • 顾客D在上午9:07到达

答案：使用队列确保顾客A首先被服务，然后是B，然后是C，然后是D - 通过FIFO排序维持完美的公平性。

最重要的洞察

队列通过分离添加点（rear）和移除点（front）来维持顺序 - 通过使用两个指针来跟踪两端，我们在保证项目以进入的确切顺序退出的同时实现O(1)操作。

心智笔记：队列的天才之处在于它的双指针设计。我们只在移除（出队/shift）时与front交互，在添加（入队/push）时与rear交互。这种关注点的分离意味着我们永远不需要遍历或重组 - 结构本身通过其双端访问模式自动维护顺序。

决策框架

使用虚拟节点模式，操作变得非常一致：

  • Push：总是添加到rear - 完全没有特殊情况！
  • Shift：总是从dummyHead.next移除（如果存在）
  • 边缘情况简化：只需要一个检查 - dummyHead.next是否为null？（空队列）

代码

// 队列中的每个顾客是一个包含其值和下一个人的"节点"
class ListNode {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

// 使用虚拟节点的更清晰实现 - 不需要null检查！
class Queue {
  constructor() {
    // 创建一个始终存在的虚拟节点（就像"队列从这里开始"的标志）
    this.dummyHead = new ListNode(null);
    this.rear = this.dummyHead; // 最初，rear指向虚拟节点
  }

  // 在队列后面添加新顾客
  push(value) {
    const newCustomer = new ListNode(value);

    // 步骤1：将当前最后一个人连接到新顾客
    this.rear.next = newCustomer;

    // 步骤2：更新我们的rear指针以指向新的最后一个人
    // 把它想象成将"最后一个人"的标志移动到新顾客
    this.rear = newCustomer;
    // 现在this.rear指向新的最后节点，而不是旧的
  }

  // 为前面的顾客服务并从队列中移除他们
  shift() {
    // 决策框架：检查队列是否为空（虚拟节点后面没有人）
    if (this.dummyHead.next === null) {
      return undefined;
    }

    // 第一个真实的顾客总是在dummyHead.next
    const firstCustomer = this.dummyHead.next;
    const servedValue = firstCustomer.value;

    // 将队列向前移动 - 跳过第一个顾客
    // 这使得dummyHead直接指向第二个顾客（如果没有则为null）
    this.dummyHead.next = firstCustomer.next;
    // 我们本质上是从链中"剪掉"firstCustomer

    // 决策框架：如果我们移除了最后一个顾客，更新rear
    if (this.dummyHead.next === null) {
      this.rear = this.dummyHead; // 空时将rear重置为虚拟节点
    }

    return servedValue;
  }

  // 查看下一个人而不为他们服务
  peek() {
    if (this.dummyHead.next === null) {
      return undefined;
    }
    return this.dummyHead.next.value;
  }

  // 检查队列是否为空
  isEmpty() {
    return this.dummyHead.next === null;
  }

  // 可视化队列（对调试有帮助）
  display() {
    const items = [];
    let current = this.dummyHead.next;

    while (current !== null) {
      items.push(current.value);
      current = current.next;
    }

    return items.join(" → ");
  }
}

// 示例：咖啡店队列
const coffeeLine = new Queue();

// 早晨高峰 - 顾客加入队列
coffeeLine.push("Alice");
coffeeLine.push("Bob");
coffeeLine.push("Charlie");

console.log("队列:", coffeeLine.display()); // 'Alice → Bob → Charlie'
console.log("队列第一个:", coffeeLine.peek()); // 'Alice'

// 开始为顾客服务（FIFO顺序）
console.log("正在服务:", coffeeLine.shift()); // 'Alice'
console.log("队列:", coffeeLine.display()); // 'Bob → Charlie'

// 服务期间新顾客到达
coffeeLine.push("Diana");
console.log("队列:", coffeeLine.display()); // 'Bob → Charlie → Diana'

console.log("正在服务:", coffeeLine.shift()); // 'Bob'
console.log("正在服务:", coffeeLine.shift()); // 'Charlie'
console.log("正在服务:", coffeeLine.shift()); // 'Diana'
console.log("正在服务:", coffeeLine.shift()); // undefined (空)

理解指针重新分配

当我们执行this.rear = newCustomer时，我们移动rear指针以指向不同的节点：

push('Alice')之前：
dummyHead → null
rear ↑ (指向dummyHead)

this.rear.next = newCustomer之后：
dummyHead → Alice → null
rear ↑ (仍然指向dummyHead)

this.rear = newCustomer之后：
dummyHead → Alice → null
            rear ↑ (现在指向Alice)

关键洞察：this.rear只是一个引用/指针，告诉我们"哪个节点当前是最后的"。当我们写this.rear = newCustomer时，我们没有改变任何节点 - 我们只是更新引用以指向新的最后节点。这就像将"队列最后"的标志从一个人移动到另一个人。

理解shift的指针旁路

当我们执行this.dummyHead.next = firstCustomer.next时，我们绕过第一个顾客：

shift()之前：
dummyHead → Alice → Bob → Charlie → null
            ↑ firstCustomer指向这里

const firstCustomer = this.dummyHead.next之后：
我们保存对Alice的引用

this.dummyHead.next = firstCustomer.next之后：
dummyHead → Bob → Charlie → null
(Alice被绕过了 - 不再在链中！)

this.dummyHead.next = firstCustomer.next这行代码是说："无论Alice指向什么（Bob），让虚拟节点直接指向那个。"这有效地从链中移除了Alice - 她已经"被服务"并且不再在队列中。

为什么虚拟节点使代码更清晰

虚拟节点就像一个永远不会移动的"队列从这里开始"的标志。这消除了特殊情况：

没有虚拟节点：

  • 在添加第一个元素之前必须检查队列是否为null
  • 必须处理front和rear都为null的情况
  • 第一个元素与后续元素需要不同的逻辑

有虚拟节点：

  • 虚拟节点始终存在，所以不需要对结构本身进行null检查
  • 添加始终相同：连接到rear，更新rear
  • 移除始终相同：从dummyHead.next获取
  • 唯一需要的检查是队列是否为空（dummyHead.next === null）

疑虑消除

常见疑虑："为什么队列使用链表？我们不能只使用数组并跟踪索引吗？那不会更简单吗？"

这是一个很好的问题，它突出了一个关键的性能考虑因素。让我们检查两种方法。

为什么你可能认为数组更简单

考虑用数组实现队列：

  • "数组提供索引访问 - 看起来更直接"
  • "我们可以只使用push()来添加和shift()来移除"
  • "不需要管理节点指针和next引用"

为什么这种想法错过了一个关键问题

关键认识：基于数组的队列有一个隐藏的性能陷阱！

让我们追踪数组实现中发生的事情：

初始：[1, 2, 3, 4, 5]

出队（从前面移除）：
步骤1：移除索引0处的元素：[_, 2, 3, 4, 5]
步骤2：将所有剩余元素向左移动：[2, 3, 4, 5]
        - 索引1的元素移动到索引0
        - 索引2的元素移动到索引1
        - 索引3的元素移动到索引2
        - 索引4的元素移动到索引3

性能灾难：每次出队操作都需要移动所有剩余元素，使其成为O(n)而不是O(1)！

具体示例：性能比较

让我们比较对包含1000个项目的队列的操作：

基于数组的队列：

  • 入队：O(1) - 只需追加到末尾
  • 出队：O(n) - 必须移动999个元素！
  • 处理所有1000个项目：总共O(n²)操作

链表队列：

  • 入队：O(1) - 更新rear指针
  • 出队：O(1) - 更新front指针
  • 处理所有1000个项目：总共O(n)操作

循环数组替代方案

"但是等等，"你可能会说，"使用带有front和rear索引的循环数组怎么样？"

class ArrayQueue {
  constructor(capacity) {
    this.items = new Array(capacity);
    this.front = 0;
    this.rear = -1;
    this.size = 0;
    this.capacity = capacity;
  }
}

这种方法有其自身的问题：

  • 固定容量：必须预先确定最大大小
  • 浪费空间：未使用的数组槽消耗内存
  • 调整大小复杂性：扩展队列需要复制所有元素
  • 索引环绕逻辑：使用模运算的更复杂的心智模型

为什么链表是最佳选择

链表实现优雅地解决了所有这些问题：

  1. 恒定时间操作：入队和出队都始终是O(1)
  2. 动态大小：根据需要增长和缩小
  3. 内存高效：只分配实际使用的内容
  4. 简单的心智模型：用于移除的front指针，用于添加的rear指针
  5. 没有移动或复制：节点保持原位；只有指针改变

保证：由于我们只接触结构的末端（而不是中间），并且指针更新是O(1)操作，我们在只使用所需内存的同时为所有核心操作维持恒定的时间复杂度。

双指针链表设计不仅仅是一个实现细节 - 它是使队列对其预期FIFO目的高效的基本机制！

← Back to Blog