第3章｜栈与队列

Unit 00 · 栈、队列与待处理状态

U00
Stack & Queue FundamentalsOrder · Pending State · Access Rule

数据结构不只是“装东西”，
它决定谁先被处理。

栈让最近进入、尚未解决的对象先离开；队列让等待最久的对象先离开。本单元不背 API，而是通过操作动画建立“进入顺序—离开顺序—待处理状态”的统一模型。

本单元认知目标

  • 从具体操作中区分 LIFO 与 FIFO，而不是只记中文翻译；
  • 说明容器里保存的是“仍待处理的状态”，不一定是全部历史；
  • 区分查看与删除：top/front 不修改状态，pop/dequeue 会修改状态；
  • 理解空容器访问、Python 队列实现与基本复杂度。

统一操作模型

Stack: push(x) → top() → pop() Queue: enqueue(x) → front() → dequeue() 关键问题： 谁进入？从哪里离开？离开时确定了什么？
Stack · LIFO

后进先出。栈顶是最近进入且尚未离开的对象，典型场景包括撤销、嵌套与最近未匹配状态。

Queue · FIFO

先进先出。队首是等待时间最长的对象，队尾接收新任务，典型场景包括排队、缓冲与任务调度。

Pending State

容器通常只保存尚未解决、尚未消费或未来仍有用的对象，而不是无差别保存全部输入历史。

Underflow

空栈或空队列不存在可移除对象。执行 pop/dequeue 前必须明确空状态如何处理。

CHAPTER 03 / THE COGNITIVE ATLAS

第 3 章 · 认知梯度全景图

栈与队列：理解待处理状态，掌握栈、队列与单调结构。

13 个后续单元
贯穿本章的统一框架保存尚未完成的状态 → 等待触发条件 → 局部解决并归约。先解释栈顶或队首代表什么，再选择操作。

从基础到复合任务，每一步增加一种决策

这里的梯度描述认知任务的递进，不等同于题库的难度标签。点击题目可进入对应单元。

起点 · Unit 00　栈、队列与待处理状态。先理解状态、操作与不变量，再沿下列路线练习。
  1. 01

    局部归约

    从最近未闭合对象到已化简前缀，再到子表达式求值。

    U01#20 有效的括号U02#1047 删除字符串中的所有相邻重复项U03#150 逆波兰表达式求值
  2. 02

    接口与摘要

    用辅助最值与惰性转移，把结构行为封装成接口。

    U04#155 最小栈U05#232 用栈实现队列U06#232 用栈实现队列（重制版）
  3. 03

    单调候选

    值、索引、边界依次增加；每次弹出都对应一个被解决的旧任务。

    U07#496 下一个更大元素 IU08#739 每日温度U09#84 柱状图中最大的矩形U10#239 滑动窗口最大值
  4. 04

    复合状态

    把优先级、嵌套上下文与几何边界纳入同一待处理状态思路。

    U11#347 前 K 个高频元素U12#394 字符串解码U13#42 接雨水

每道题在框架中的具体形式

用同一组问题定位每个单元，再观察迁移题改变了哪个条件。进入写代码环节后，学习地图会收起，留出独立思考的空间。

UNIT 01局部归约

#20 有效的括号

待处理状态
尚未匹配的左括号栈。
触发与归约
右括号只与最近一个未匹配左括号配对。
结构不变量
栈底到栈顶按出现顺序保存全部未闭合左括号。
输出与边界
空栈遇右括号即失败，最终栈必须为空。
迁移 · #921 使括号有效的最少添加最少添加括号把失败改为补充缺失括号并统计数量。
先说清契约，再独立实现进入本单元 ↗
UNIT 02局部归约

#1047 删除字符串中的所有相邻重复项

待处理状态
已扫描前缀经过消除后的结果栈。
触发与归约
当前字符与栈顶相同就消除，否则保留。
结构不变量
栈恰好是已读前缀的完整化简结果。
输出与边界
消除可能形成新的相邻关系，不能只删除原始相邻对。
迁移 · #1209 删除字符串中的所有相邻重复项 II删除 k 个相邻重复项改为保存字符与连续次数。
先说清契约，再独立实现进入本单元 ↗
UNIT 03局部归约

#150 逆波兰表达式求值

待处理状态
已经求值、尚未被外层消费的子表达式结果栈。
触发与归约
数值进入栈；运算符消费最近两个结果并归约为一个。
结构不变量
每个栈值都代表完整子表达式的值。
输出与边界
区分左右操作数，除法按向零截断处理。
迁移 · #227 基本计算器 II中缀表达式增加优先级；先处理乘除再归约加减。
先说清契约，再独立实现进入本单元 ↗
UNIT 04接口与摘要

#155 最小栈

待处理状态
数据栈与每层对应的最小值摘要。
触发与归约
压入或弹出数据时同步维护同层摘要。
结构不变量
栈顶摘要等于当前数据栈的最小值。
输出与边界
重复最小值也须正确恢复；接口要求常数时间。
迁移 · #716 最大栈Max Stack 还需要删除最近的最大值，不能只把 min 改成 max。
先说清契约，再独立实现进入本单元 ↗
UNIT 05接口与摘要

#232 用栈实现队列

待处理状态
输入栈与输出栈，分别保存较新与较旧的元素。
触发与归约
仅当输出栈为空时，把输入栈元素整体反向转移。
结构不变量
输出栈非空时，栈顶就是队列最早加入的元素。
输出与边界
不能把新元素直接压到非空输出栈；区分单次与均摊成本。
迁移 · #225 用队列实现栈用队列实现栈改为维护最近入队元素优先被弹出的顺序。
先说清契约，再独立实现进入本单元 ↗
UNIT 06接口与摘要

#232 用栈实现队列（重制版）

待处理状态
双栈队列的重制练习：新元素区与待弹出区。
触发与归约
复核惰性搬运和连续查询，不因每次读取而重排。
结构不变量
两区的逻辑拼接顺序始终等于真实 FIFO 队列。
输出与边界
这是 Unit 05 的重制版本，复习时对照不同操作序列。
迁移 · #225 用队列实现栈队列模拟栈把操作成本前移到插入时的轮转。
先说清契约，再独立实现进入本单元 ↗
UNIT 07单调候选

#496 下一个更大元素 I

待处理状态
尚未找到右侧首个更大值的历史元素栈。
触发与归约
当前更大值到达时，连续解决较小栈顶的查询。
结构不变量
待解决值从栈底到栈顶严格递减。
输出与边界
无更大值时使用题目规定的缺省结果。
迁移 · #503 下一个更大元素 II循环数组增加第二次扫描，但不能重复创建原始查询。
先说清契约，再独立实现进入本单元 ↗
UNIT 08单调候选

#739 每日温度

待处理状态
尚未等到升温的日期索引栈。
触发与归约
更高温度到达时弹出旧日期，用索引差计算等待天数。
结构不变量
栈中日期递增，对应温度单调不增。
输出与边界
相等温度不能解决等待任务；结果保存天数而非温度。
迁移 · #901 股票价格跨度股票跨度把向右等候改为累计向左连续覆盖长度。
先说清契约，再独立实现进入本单元 ↗
UNIT 09单调候选

#84 柱状图中最大的矩形

待处理状态
尚未确定右侧更矮边界的柱子索引栈。
触发与归约
更矮柱到达时，弹出柱子并确定左右边界和矩形宽度。
结构不变量
栈内高度单调不减，未弹出的柱子仍可能继续向右扩展。
输出与边界
哨兵、等高柱与宽度的开区间边界要一致。
迁移 · #85 最大矩形最大矩形把每一行转成高度数组，反复复用柱状图求解。
先说清契约，再独立实现进入本单元 ↗
UNIT 10单调候选

#239 滑动窗口最大值

待处理状态
当前窗口中尚未被支配的候选索引双端队列。
触发与归约
队首删除过期索引，队尾删除不可能再成为最大值的候选。
结构不变量
索引递增、值递减且都位于当前窗口；队首给出最大值。
输出与边界
必须保存索引才能判断过期，不能只保存值。
迁移 · #1438 绝对差不超过限制的最长连续子数组最长合法区间同时维护最大值和最小值，并按差值收缩窗口。
先说清契约，再独立实现进入本单元 ↗
UNIT 11复合状态

#347 前 K 个高频元素

待处理状态
频次候选与容量为 k 的最小堆。
触发与归约
按频次保留最强的 k 个候选，堆顶作为淘汰边界。
结构不变量
处理过的候选中，堆内频次属于当前前 k 名。
输出与边界
原数组值与候选频次是不同优先级。
迁移 · #692 前 K 个高频单词高频单词还需处理频次相同时的字典序，比较规则必须一致。
先说清契约，再独立实现进入本单元 ↗
UNIT 12复合状态

#394 字符串解码

待处理状态
当前内层字符串与外层字符串、重复次数组成的栈帧。
触发与归约
进入嵌套时保存外层，闭合时恢复并按次数合并。
结构不变量
每个栈帧对应一个未闭合层，当前结果只属于最内层。
输出与边界
重复次数可能有多位，不能把每个数字独立处理。
迁移 · #1190 反转每对括号间的子串括号反转改变闭合层的合并规则，而非继续按次数重复。
先说清契约，再独立实现进入本单元 ↗
UNIT 13复合状态

#42 接雨水

待处理状态
尚未完成水层结算的单调不增柱子索引栈。
触发与归约
更高右边界到达时，把弹出柱子作为凹槽底部结算水层。
结构不变量
剩余栈保存尚有机会被右边界包围的柱子。
输出与边界
弹出后没有左边界就不能蓄水；宽度不包含两侧边界。
迁移 · #11 盛最多水的容器盛最多水的容器只取一对边界，转向相向指针和短板原则。
先说清契约，再独立实现进入本单元 ↗
认知任务 1
先观察对象进入，再预测谁会最先离开
不要先套“栈”或“队列”的名称。先根据场景判断：系统更关心最近发生的操作，还是等待时间最长的任务？
顺序处理实验台等待播放当前状态

输入流 / 操作流

点击“播放状态变化”，让 A、B、C 按顺序进入当前容器。

容器内部状态

STACK底部 → 顶部
QUEUE队首 → 队尾
读取对象
判断规则
进入容器
访问出口
产生结果
当前尚未执行操作。动画完成后，右侧问题才具有确定答案。
已进入0
已离开0
当前大小0
可访问位置—
代码补全：把访问规则编译为 Python填写的是关键表达式，不需要从零重写整段代码。
# 1. 栈：新对象进入列表尾部
# 2. 栈：只查看最近进入对象，不删除
# 3. 栈：删除并返回最近进入对象
# 4. 队列：删除并返回等待最久对象 
from collections import deque

class Stack:
    def __init__(self):
        self._data = []

    def push(self, value):
        self._data.append(value)

    def top(self):
        if not self._data:
            raise IndexError("top from empty stack")
        return self._data[-1]

    def pop(self):
        if not self._data:
            raise IndexError("pop from empty stack")
        return self._data.pop()

    def empty(self):
        return not self._data


class Queue:
    def __init__(self):
        self._data = deque()

    def enqueue(self, value):
        self._data.append(value)

    def front(self):
        if not self._data:
            raise IndexError("front from empty queue")
        return self._data[0]

    def dequeue(self):
        if not self._data:
            raise IndexError("dequeue from empty queue")
        return self._data.popleft()

    def empty(self):
        return not self._data
代码与容器逐行联动点击代码行可跳转到第一次执行该行的状态。
1class Stack:
2 def __init__(self):
3 self._data = []
5 def push(self, value):
6 self._data.append(value)
8 def top(self):
9 if not self._data:
11 return self._data[-1]
13 def pop(self):
14 if not self._data:
16 return self._data.pop()
20class Queue:
21 def __init__(self):
22 self._data = deque()
24 def enqueue(self, value):
25 self._data.append(value)
27 def front(self):
28 if not self._data:
30 return self._data[0]
32 def dequeue(self):
33 if not self._data:
35 return self._data.popleft()

执行状态

当前对象 / 操作创建 Stack
stack._data
queue._data
返回值None
关键判断初始化为空
进入 Stack 类，准备创建内部列表。
完成代码联动后进入“匹配与排队”迁移练习代码正确、查看参考答案、一键填入或播放完整轨迹后解锁。

迁移实验：先判断“谁应该先被处理”

下面四个场景不只是关键词匹配。请先确定容器保存的对象，再判断出口应该指向“最近进入者”还是“等待最久者”。

下一题预演：只有一种括号时，如何判断是否有效？

扫描字符串时，栈只保存尚未匹配的左括号。右括号到达时必须消费最近一个左括号；空栈遇到右括号立即失败。

def valid_single_parentheses(s: str) -> bool:
    stack = []

    for char in s:
        if char == "(":
            stack.append(char)
        else:
            if not stack:
                return False
            stack.pop()

    return not stack

Unit 00 Skill：用访问顺序建模待处理状态

先不要问“这题是不是栈题”。先问：当前有哪些对象尚未解决？下一个应该被处理的是最近进入者，还是等待最久者？这一访问规则决定使用栈或队列。

题型顺序管理与待处理状态
触发信号撤销 / 嵌套 / 最近状态；排队 / 缓冲 / 到达顺序
核心表示stack 顶部或 queue 队首作为唯一出口
关键不变量容器顺序与仍待处理对象的优先顺序完全一致
核心操作push/pop/top；enqueue/dequeue/front
复杂度合理实现下，基本操作通常为 O(1)
常见错误空容器访问、混淆查看与删除、用 list.pop(0) 高频出队
可迁移题型括号匹配、表达式、撤销系统、任务调度
推荐下一题Unit 01 · LeetCode #20 有效的括号