栈与队列

栈：LIFO 与典型场景

栈适合 最近相关性：括号匹配、路径撤销、DFS 迭代、表达式求值。

有效括号：

def is_valid(s):
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    for ch in s:
        if ch in '([{':
            stack.append(ch)
        elif not stack or stack.pop() != pairs[ch]:
            return False
    return not stack

逆波兰表达式：遇数字入栈，遇运算符 pop 两个操作数计算再 push。

单调栈

维护栈内元素单调（增或减），用于 Next Greater Element、柱状图最大矩形、接雨水。

def daily_temperatures(temps):
    n = len(temps)
    ans = [0] * n
    stack = []  # 存下标，温度递减
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            ans[j] = i - j
        stack.append(i)
    return ans

每元素最多入栈出栈一次，总 O(n)。

队列与 BFS

队列 FIFO，用于 层序遍历、无权图最短路。

from collections import deque
def level_order(root):
    if not root:
        return []
    q = deque([root])
    out = []
    while q:
        level = []
        for _ in range(len(q)):
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        out.append(level)
    return out

记录 len(q) 可分层；多源 BFS 初始全部入队。

单调队列

滑动窗口最值： deque 存 下标，队头对应当前窗口最大值，入队前从队尾弹出更小元素。均摊 O(1)，总 O(n)。

适用于「滑动窗口最大值」「跳跃游戏 III 变体」。

栈与队列互实现

• 两个栈实现队列（见 flashcard）。
• 一个队列实现栈：入队后把前面元素依次移到队尾，使新元素在队头。

面试常考均摊分析，说明为何不是每次 O(n)。

与 Week 2 树章节衔接

week02-tree-dfs-bfs 中 DFS 可用栈模拟递归，BFS 即队列。图论 Week 3 week03-backtracking-graph 会扩展拓扑排序（入度 + 队列）。

练习建议

单调栈 3 题：每日温度、柱状图矩形、接雨水。BFS 2 题：二叉树层序、网格岛屿数量。写代码前先声明栈/队列存的是 值还是下标。

实战巩固与面试表达

本篇属于 8 周冲刺 week02-stack-queue 主题。复习时先闭卷回答 frontmatter 中三张 flashcard，再展开口述两个「为什么」：为什么这种方案能 work、边界失败时如何降级。与相邻章节对照：算法篇强调复杂度与模板，Go 篇强调工程默认写法，中间件篇强调线上故障案例。

动手与自检清单

用 25 分钟限时做 1 道相关练习题或画出一张架构/数据结构示意图；用 5 分钟写 STAR 片段说明你在项目里是否用过类似技术。记录 3 个面试追问及你的标准答法，存入 /zh/notebook/master-plan 笔记。若某点不熟，回到对应 /chapters 交互 Lab 重新走一遍流程，比死记卡片更有效。

易错点提醒

避免只背名词不会画图；避免只说优点不谈 trade-off（性能、一致性、运维成本至少提一项）；避免把学习 Demo 说成百万 QPS 生产。回答时使用「场景 → 方案 → 结果 → 反思」四段式，体现工程成熟度。