队列

副标题 / 摘要 层序遍历是二叉树 BFS 模板的起点。真正关键的不是“用队列”，而是“如何把同一层的节点切分出来”。本文按 ACERS 结构拆解 LeetCode 102 的按层处理方法、DFS 深度分桶备选方案，以及工程里常见的分层遍历场景。 预计阅读时长：10~12 分钟 标签：Hot100、二叉树、BFS、DFS、队列、层序遍历 SEO 关键词：Hot100, Binary Tree Level Order Traversal, 二叉树的层序遍历, BFS, 队列, LeetCode 102 元描述：系统讲透 LeetCode 102 的层序 BFS、层宽控制与 DFS 深度分桶思路，并延伸到组织树、菜单树和波次执行等工程场景。 目标读者 想把 BFS 模板真正固定下来的 Hot100 刷题读者 会普通遍历，但一到“按层输出”就容易把层边界写乱的开发者 需要按深度分组展示树形结构的工程师 背景 / 动机 LeetCode 102 是树题里最标准的 BFS 入门题之一。 它训练的不是“遍历所有节点”，而是两件更重要的事： 如何用队列维护“下一批待处理节点” 如何准确切出“这一层”和“下一层”的边界 很多 BFS bug 都来自这里： 在遍历当前层时直接用不断变化的 queue.length 一边弹当前层，一边把新孩子混进当前层结果 忘记空树处理，导致访问空指针 把 102 的模板写稳，后面的： 右视图 每层平均值 锯齿层序遍历 最小深度 / 最大深度的 BFS 写法 都会自然很多。 ...

副标题 / 摘要 只有队列（FIFO）时，也能实现栈（LIFO）。本文展示单队列旋转法，并分析复杂度与边界。 目标读者 刷题与面试准备的开发者 需要理解数据结构转换的人 初中级算法学习者 背景 / 动机 栈的后进先出与队列的先进先出相反。 “旋转队列”可以把最新元素移动到队头，从而模拟栈顶。 核心概念 队列（FIFO）：先进先出 栈（LIFO）：后进先出 队列旋转：把新元素转到队首 实践指南 / 步骤 入栈：将元素入队 旋转队列：把队首依次出队再入队，直到新元素位于队首 出栈：直接出队 取栈顶：查看队首 可运行示例 from collections import deque class MyStack: def __init__(self): self.q = deque() def push(self, x: int) -> None: self.q.append(x) for _ in range(len(self.q) - 1): self.q.append(self.q.popleft()) def pop(self) -> int: return self.q.popleft() def top(self) -> int: return self.q[0] def empty(self) -> bool: return not self.q if __name__ == "__main__": s = MyStack() s.push(1) s.push(2) print(s.top()) print(s.pop()) print(s.empty()) 解释与原理 每次 push 后旋转队列，使新元素位于队首。 这样 pop 就相当于弹出“栈顶”。 ...

副标题 / 摘要 当系统只提供栈（LIFO）时，如何构建队列（FIFO）？本文用双栈法给出清晰实现与工程要点。 目标读者 刷题与面试准备的开发者 需要理解数据结构转换的人 希望掌握复杂度分析的初中级工程师 背景 / 动机 队列的先进先出与栈的后进先出相反。 双栈法通过“翻转顺序”实现队列语义，是经典的结构变换题。 核心概念 栈（LIFO）：后进先出 队列（FIFO）：先进先出 双栈翻转：把输入顺序倒置为输出顺序 实践指南 / 步骤 入队：压入 in 栈 出队/取队首：若 out 栈为空，将 in 栈全部弹出并压入 out 栈 从 out 栈弹出：即为队首 保持延迟搬运：只在 out 为空时搬运 可运行示例 class MyQueue: def __init__(self): self._in = [] self._out = [] def push(self, x: int) -> None: self._in.append(x) def _move(self) -> None: if not self._out: while self._in: self._out.append(self._in.pop()) def pop(self) -> int: self._move() return self._out.pop() def peek(self) -> int: self._move() return self._out[-1] def empty(self) -> bool: return not self._in and not self._out if __name__ == "__main__": q = MyQueue() q.push(1) q.push(2) print(q.peek()) print(q.pop()) print(q.empty()) 解释与原理 in 栈负责“输入顺序”，out 栈负责“输出顺序”。 当 out 为空时，把 in 全部倒入 out，就实现了 FIFO 的逆序输出。 ...

副标题 / 摘要 滑动窗口最大值是“滑动窗口 + 单调队列”的经典组合题。本文按 ACERS 模板拆解思路，给出可复用的工程做法与多语言实现。 预计阅读时长：12~15 分钟 标签：滑动窗口、单调队列、数组 SEO 关键词：Sliding Window Maximum, 滑动窗口最大值, 单调队列, deque, O(n) 元描述：滑动窗口最大值的单调队列解法与工程应用，含复杂度分析与多语言代码。 目标读者 正在刷 LeetCode / Hot100 的同学 想建立“滑动窗口 + 单调队列”模板的中级开发者 做实时监控、日志分析、风控的工程师 背景 / 动机 连续窗口的最大值在工程里非常常见： 延迟监控、价格波动、温度报警、在线指标平滑等都需要“窗口最大值”。 暴力做法每次窗口重算最大值是 O(nk)，当 n 很大时会不可接受。 单调队列能把复杂度降到 O(n)，是最工程可行的方案之一。 核心概念 滑动窗口：固定长度 k 的连续区间 单调队列：队列中元素按值单调递减，队首永远是当前最大值 索引维护：用索引判断元素是否过期（离开窗口） A — Algorithm（题目与算法） 题目还原 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组最左侧移动到最右侧。 你只能看到窗口内的 k 个数字，窗口每次右移一位。 返回每个窗口中的最大值。 输入输出 名称 类型 描述 nums int[] 整数数组 k int 窗口大小 返回 int[] 每个窗口的最大值 示例 1 nums = [1,3,-1,-3,5,3,6,7], k = 3 输出 = [3,3,5,5,6,7] 示例 2 nums = [1], k = 1 输出 = [1] C — Concepts（核心思想） 方法类型 滑动窗口 + 单调队列（Monotonic Queue）。 ...