栈
栈（Stack）是一种**后进先出（LIFO，Last In First Out）的受限线性表——只允许在栈顶（top）**一端进行插入和删除，最后压入的元素最先弹出。所有操作（push 入栈、pop 出栈、peek 查看栈顶）都是 O(1)。它既是数组（顺序栈）和链表（链式栈）在「单端」上的受限应用，也是计算机系统里最基础的控制结构——函数调用栈、表达式求值、括号匹配、浏览器前进后退、撤销（undo）操作都以它为底层。
栈的全部考点都源于一个核心性质：LIFO 后进先出 ⇒ 单端操作 O(1)。由此衍生出三大主题：①栈本身的实现与权衡（顺序栈用数组尾部做栈顶 / 链式栈用链表头结点做栈顶 / 栈溢出与函数调用栈）；②栈的经典应用（括号匹配、后缀表达式求值、中缀转后缀、浏览器/撤销的「双栈」模型）；③单调栈——一种「栈内元素保持单调」的特殊用法，是面试高频套路，专门解决「下一个更大元素」「柱状图最大矩形」「接雨水」等「维护左/右首个满足某条件元素」的问题。
评价
优点
- 核心操作全部 O(1)：
push、pop、peek只动栈顶，不搬移其他元素——这是 LIFO 受限带来的常数优势 - 实现极简：顺序栈用数组尾部 + 一个
top指针；链式栈用链表头插/头删——两种实现都不过十几行 - 天然适合「回溯」「撤销」「嵌套」语义：函数调用栈、递归、DFS、括号匹配、表达式求值、撤销操作，栈是这些场景的「语义载体」
- 单调栈把「找下一个更大/更小」从 O(n²) 降到 O(n)：每个元素最多入栈出栈各一次
缺点
- 访问受限：只能操作栈顶，不能随机访问中间元素（要访问必须先弹出其上的元素）——这是 LIFO 的代价
- 顺序栈可能栈溢出：固定容量数组实现时，超过容量会 stack overflow；动态数组实现有扩容开销
- 不是万能容器：需要 FIFO（先进先出）的场景要用队列，需要随机访问的场景要用数组
本叶地图
- 入门 —— LIFO 定义、push/pop/peek O(1)、顺序栈 vs 链式栈、栈溢出、函数调用栈、与队列对比、JS 数组当栈
- 栈的经典应用 —— 括号匹配、后缀表达式求值、中缀转后缀、函数调用栈与递归、浏览器前进后退、撤销操作
- 单调栈 —— 单调栈原理、下一个更大元素、每日温度、柱状图最大矩形、接雨水
- 参考 —— 栈 API 速查、复杂度表、各语言栈对照、单调栈套路、易错点
交互演示
- 栈可视化演示 —— 栈的 LIFO 操作与单调栈过程