11 · 队列与层序思想

目标：理解 FIFO 队列；会用数组正确模拟队列；通过「层序打印」建立 BFS「一层一层」的心智，为二叉树层序铺路。

为什么面试会考

队列和栈对称，考 FIFO（先进先出）：

• 滑动时间窗（933）：队头是最早的请求，过期就从队头扔掉。
• 用队列实现栈（225）：考你对两种结构的理解是否扎实。
• 树的层序遍历（下一阶段的 BFS）：核心就是「按层处理」——先入队的先被访问，同一批入队的属于同一层。

前端面试里，队列不一定单独出难题，但 BFS 层序几乎是二叉树必考点；本篇先把「一层一层」讲透。

零基础概念：队列是什么

操作	含义	理想复杂度
入队 enqueue	加到队尾	O(1)
出队 dequeue	从队头取出	O(1)
看队头 front	只看队头	O(1)

FIFO：先入队的，先出队。

零基础概念：JS 用数组模拟队列的坑

const q = [];
q.push(1);   // 入队：放队尾，O(1)
q.shift();   // 出队：取队头，但 shift 是 O(n)！

Array.prototype.shift 要把后面所有元素前移，长队列会 TLE。刷题常用两种写法：

写法 A：双指针（推荐）

class Queue {
  constructor() {
    this.data = [];
    this.head = 0;
  }
  enqueue(x) {
    this.data.push(x);
  }
  dequeue() {
    const x = this.data[this.head++];
    // 可选：head 很大时压缩数组
    if (this.head > this.data.length / 2) {
      this.data = this.data.slice(this.head);
      this.head = 0;
    }
    return x;
  }
  isEmpty() {
    return this.head >= this.data.length;
  }
  front() {
    return this.data[this.head];
  }
}

dequeue 均摊 O(1)。

写法 B：小数据量直接 shift

练习、窗口长度很小的题（如 933），shift 够用；面试要说得出性能差异。

JS 模板 / 套路

模板：层序处理（BFS 骨架）

const queue = [start];
while (queue.length) {
  const size = queue.length; // 当前层节点数
  for (let i = 0; i < size; i++) {
    const node = queue.shift(); // 或双指针 dequeue
    // 处理 node
    // 把下一层邻居入队
    for (const next of neighbors) queue.push(next);
  }
}

size 这一行是 「一层一层」的关键：本轮只处理当前层那么多，新入队的算下一层。

精讲 1：层序打印小例子

不用树，先用「图」建立直觉：从节点 0 出发，按层打印距离。

// graph[i] = i 的邻居列表
// 0 是第一层，0 的邻居是第二层，以此类推
function levelOrderPrint(graph, start = 0) {
  const queue = [start];
  const visited = new Set([start]);
  let level = 0;

  while (queue.length) {
    const size = queue.length;
    const row = [];
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      row.push(node);
      for (const nb of graph[node]) {
        if (!visited.has(nb)) {
          visited.add(nb);
          queue.push(nb);
        }
      }
    }
    console.log(`第 ${level} 层:`, row);
    level++;
  }
}

// 示例：0—1—3，0—2
levelOrderPrint([[1, 2], [0, 3], [0], [1]]);
// 第 0 层: [0]
// 第 1 层: [1, 2]
// 第 2 层: [3]

口述：「队列保证先发现的先处理；每轮固定 size，就把同一深度的节点成批处理完。」——二叉树层序（第 16、18 篇）只是把 graph[node] 换成 left/right。

精讲 2：LeetCode 933 · 最近的请求次数

题意：实现 RecentCounter：只统计最近 3000 毫秒内的请求次数。每次 ping(t) 追加时间 t（单调递增），返回窗口内请求数。

思路：队列存时间戳；新请求入队后，把队头 < t - 3000 的旧请求不断出队，队列长度即答案。

var RecentCounter = function() {
  this.q = [];
};

RecentCounter.prototype.ping = function(t) {
  this.q.push(t);
  while (this.q[0] < t - 3000) {
    this.q.shift();
  }
  return this.q.length;
};

• 每个时间戳最多入队、出队一次 → 均摊 O(1)。
• 本题窗口固定、数据量可控，shift 可接受；若被追问，改双指针队列。

精讲 3：LeetCode 225 · 用队列实现栈

题意：只用队列操作实现栈（push、pop、top、empty）。

思路：一个队列即可。push 时入队后，把前面 size-1 个元素依次出队再入队，让新元素「转」到队头，队头就是栈顶。

var MyStack = function() {
  this.q = [];
};

MyStack.prototype.push = function(x) {
  this.q.push(x);
  let n = this.q.length;
  while (n > 1) {
    this.q.push(this.q.shift());
    n--;
  }
};

MyStack.prototype.pop = function() {
  return this.q.shift();
};

MyStack.prototype.top = function() {
  return this.q[0];
};

MyStack.prototype.empty = function() {
  return this.q.length === 0;
};

• push 是 O(n)，pop 是 O(1)——和「用两个栈实现队列」对称，考的是结构转换，不是最优性能。

练习清单

题号	一句话提示
LeetCode 933. 最近的请求次数	队头扔掉过期，长度即答案
LeetCode 225. 用队列实现栈	push 后轮转，让新元素到队头
LeetCode 232. 用栈实现队列	两个栈：入栈 + 出栈，出栈空时倒入
LeetCode 102. 二叉树的层序遍历	下一篇树专题会精讲；本篇先理解 size 分层
LeetCode 637. 二叉树的层平均值	层序 + 每层求平均

今日验收 checklist

• [ ] 说清 shift 为什么是 O(n)，双指针队列如何均摊 O(1)
• [ ] 能默写层序模板里的 const size = queue.length 那一层循环
• [ ] 独立实现 933；能口述 225 的 push 轮转思路
• [ ] 向别人解释：「BFS 层序 = 队列 + 每层固定处理 size 个」

若你以前见过

C++ 的 queue 在 JS 里没有标准库，数组 + 双指针是主流写法。蓝桥 BFS 若做过，本篇是把「vis + 队列」翻译成 JS，并强调按层批处理——后面 16、18 篇二叉树层序会直接套用。