队列与单调队列

讲解

队列是先进先出（FIFO）的结构，与栈恰好对偶。它的主场是「按到达顺序处理」：任务调度、消息队列、以及算法里最重要的应用——BFS 的逐层扩散（BFS 一章会大量使用）。JS 里没有原生队列，数组 push + shift 能用但 shift 是 O(n)；性能敏感时用「头指针 + 数组」或两个栈来模拟。

「用栈实现队列」和「用队列实现栈」是两道经典设计题，思想比代码重要。栈实现队列：两个栈分工，入栈只管进，出栈时把入栈整体倒进出栈（顺序恰好翻转成 FIFO）；倒的动作只在出栈为空时发生，每个元素最多倒一次，均摊 O(1)。队列实现栈：单队列即可，push 后把前面的元素依次转出再转回队尾，让新元素总是排在队首——pop 即栈顶。这两个互相模拟证明了一件事：LIFO 和 FIFO 的表达力是等价的，代价是一次顺序翻转。

单调队列是单调栈的窗口版：队内存放下标，对应值保持单调（求窗口最大值用递减队列），队首永远是当前窗口的最值。每次窗口滑动做三件事：队首过期就出队、队尾比新元素小就出队（它们永远不可能是答案了）、新下标入队。每个元素进出各一次，总复杂度 O(n)，把滑动窗口最大值从 O(nk) 拉下来。它和单调栈的区别只在「过期淘汰」这一端。

示例

两道设计题加单调队列的招牌应用——滑动窗口最大值：

import assert from 'node:assert/strict';

// 两个栈实现队列：倒序一次，LIFO 变 FIFO
class MyQueue {
  constructor() {
    this.inStack = [];
    this.outStack = [];
  }
  push(x) {
    this.inStack.push(x);
  }
  shift_() {
    if (this.outStack.length === 0) {
      while (this.inStack.length > 0) this.outStack.push(this.inStack.pop());
    }
  }
  pop() {
    this.shift_();
    return this.outStack.pop();
  }
  peek() {
    this.shift_();
    return this.outStack[this.outStack.length - 1];
  }
  empty() {
    return this.inStack.length === 0 && this.outStack.length === 0;
  }
}

// 单队列实现栈：push 后把旧元素全部转到新元素之后
class MyStack {
  constructor() {
    this.queue = [];
  }
  push(x) {
    this.queue.push(x);
    const n = this.queue.length;
    for (let i = 0; i < n - 1; i++) {
      this.queue.push(this.queue.shift());
    }
  }
  pop() {
    return this.queue.shift();
  }
  top() {
    return this.queue[0];
  }
  empty() {
    return this.queue.length === 0;
  }
}

// 单调递减队列求每个窗口的最大值
function maxSlidingWindow(nums, k) {
  const deque = []; // 存下标，对应值从队首到队尾递减
  const result = [];
  for (let i = 0; i < nums.length; i++) {
    while (deque.length > 0 && deque[0] <= i - k) deque.shift(); // 过期淘汰
    while (deque.length > 0 && nums[deque[deque.length - 1]] <= nums[i]) deque.pop(); // 不可能再是答案
    deque.push(i);
    if (i >= k - 1) result.push(nums[deque[0]]); // 队首即窗口最大值
  }
  return result;
}

const q = new MyQueue();
q.push(1);
q.push(2);
assert.strictEqual(q.peek(), 1);
assert.strictEqual(q.pop(), 1);
assert.strictEqual(q.empty(), false);

const st = new MyStack();
st.push(1);
st.push(2);
assert.strictEqual(st.top(), 2);
assert.strictEqual(st.pop(), 2);
assert.strictEqual(st.empty(), false);

assert.deepStrictEqual(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3), [3, 3, 5, 5, 6, 7]);
assert.deepStrictEqual(maxSlidingWindow([1], 1), [1]);

console.log('队列示例全部通过');

注意单调队列里「队尾弹出」的论证：新元素更大且更晚进窗口，那么所有比它小的旧元素在它存在的任何窗口里都不可能是最大值——可以放心丢弃，永远不会漏解。

常见坑

• 用 shift 当正常队列的 pop：数据量大时 O(n) 的 shift 会拖出 O(n²) 总复杂度，BFS 大数据量下要换头指针写法。
• 用栈实现队列时每次都倒：只有出栈为空才倒，否则顺序会乱，均摊复杂度也会退化。
• 单调队列忘记过期淘汰：只维护单调性不清过期下标，队首会留着窗口外的旧值。
• 队尾弹出条件写成 < 还是 <=：相等元素弹出旧的是安全的（新的下标更大、更晚过期），写成 < 保留旧值也对但队列更长；选定一种保持一致。
• 窗口边界 off-by-one：i - k 是否过期、i >= k - 1 才开始记录答案，用最小例子（k = 1）手推一遍验证。

小结

队列 = FIFO；栈队列互相模拟的核心是一次顺序翻转；单调队列 = 单调性 + 过期淘汰，O(n) 拿下滑动窗口最值。下一章转入算法思想层面：递归与分治。