栈

栈是一种后进先出（LIFO）的数据结构，适合保存“最近进入但尚未完成”的状态；核心操作是 push、pop、peek/top，常用于匹配、嵌套上下文、撤销与延迟处理。

#algorithm #concept #growing #stack

[!info] related notes 算法面试题型 MOC 单调栈递归有效括号删除字符串中的所有相邻重复项逆波兰表达式求值基本计算器最小栈小行星碰撞每日温度柱状图中最大的矩形接雨水用栈实现队列用队列实现栈原地栈最长有效括号

栈

一句话定义

栈（Stack）是一种 Last In, First Out（LIFO，后进先出） 的数据结构。

它最稳定的心智模型不是“一摞盘子”，而是：

把最近进入、但还没有处理完的上下文保存起来；需要继续处理时，优先回到最新那一层。

核心操作

push(x)  → 把 x 放到栈顶
pop()    → 移除并返回栈顶
peek()   → 查看栈顶但不移除
empty()  → 是否为空

只允许从同一端进入和离开，是 LIFO 语义成立的关键。

为什么它适合“最近未完成状态”

例如括号：

([{}])

扫描到一个左括号时，它代表一个尚未闭合的上下文。

新的左括号会嵌套在旧上下文里面，因此闭合时必须先处理最近打开的那个：

push (
push [
push {
遇到 } → pop {
遇到 ] → pop [
遇到 ) → pop (

这就是栈比普通数组“碰巧能 push/pop”更重要的语义。

常见问题形态

匹配与嵌套

有效括号
表达式解析
HTML / AST 的嵌套结构

消除与回退

计算上下文

调用上下文

函数递归时，运行时也会维护调用栈。详见递归。

栈与递归

递归与显式栈常常可以互相改写：

递归
= Runtime 替你保存“接下来回到哪里、局部状态是什么”

显式栈
= 程序自己保存这些待恢复上下文

这不代表所有递归都应该机械改成栈，但它解释了 DFS、树遍历、表达式解析中两者为什么经常互换。

普通栈与单调栈

单调栈仍然使用 LIFO 容器，但额外维护“栈内元素具有单调性”的不变量，用于淘汰候选并寻找最近更大/更小或边界。

因此：

普通栈
→ 重点是最近未完成上下文

单调栈
→ 在 LIFO 之上再增加候选单调性约束

单调栈的方向、模板和边界题统一维护在单调栈，本页不复制第二份模板。

栈与队列

栈：LIFO，优先处理最近进入的未完成状态；
队列：FIFO，优先处理最早进入的待处理状态。

判断时不要只问“能不能实现”，而要问题目的自然处理顺序是什么。

边界与常见错误

空栈时直接读取栈顶；
只会背 push/pop，却没有说明栈里保存的对象代表什么；
遇到“最近更大/更小”仍在普通栈本体里硬套，应转到单调栈；
把栈当成“万能 DFS 工具”，却没有明确待恢复状态。

学习检查

不看正文回答：

LIFO 描述的究竟是什么约束？
为什么括号匹配天然适合保存“最近未完成上下文”？
递归调用与显式栈之间有什么结构对应关系？
普通栈与单调栈共享什么，又多出了什么不变量？
栈和队列的核心差异为什么不是 API 名称，而是处理顺序？
给一个消除类问题，说明栈里应该保存什么、什么时候 pop、pop 后为什么旧元素无需继续保留。
面对陌生题，能否先说清“栈顶代表什么未完成状态”，再决定是否使用栈？

栈