如果说数组和链表是数据结构里的基础积木，那栈就是那个“说明书上一句话就能说完，实战里却最容易认不出来”的零件。后进先出，四个字，人人都会背；但真正在看题的时候，我们想到它了吗？去年我面试一位候选人，让他实现一个最小栈，push 和 pop 两分钟就写完了，getMin 要求 O(1) 时整个人卡住，绕了一大圈都没想起来“再开一个辅助栈”这种解法。我问他平时写代码有没有主动用过栈，他想了想说：好像编译器在用。
这就是大多数人的状态。栈从不冷门——函数调用、递归回溯、表达式求值、浏览器后退按钮，背后全是它。但正因为它太底层、太理所当然，我们反而在需要主动用它的时候认不出它。这期是优选算法专题的第十二篇，我想换个讲法：先从“为什么会有栈”说起，再手写两种栈实现，接着拆括号匹配和单调栈这两类最高频题型，最后落到栈帧、堆与栈这些系统级概念上。适合刷题遇瓶颈想回头补数据结构的人，也适合准备算法工程师面试、想系统过栈考点的同学。
1. 为什么栈是最简单也最容易认不出的数据结构
1.1 后进先出到底是一种什么能力
栈的规则确实简单：只能在栈顶插入和删除，最新进来的最先出去。用一摞盘子来想就行——你往最上面放盘子，也先从最上面拿盘子。但我想说的是另一个层面：后进先出本质上是在维护一种“最近的历史”。
这句话才是栈的灵魂。当一个问题需要优先处理“最近发生的事”时，它就指向栈。举个例子，浏览器的后退按钮：你访问 A、B、C 三个页面，回到上一页时回到的是 C 的前一页 B，而不是 A。为什么？因为浏览器把访问历史压进了一个栈，后退就是 pop。再比如编辑器里的 Undo：你依次做了三次操作，撤销时先撤销最后一次。栈结构天然适合这类“时间倒流”的用法。
这里顺便区分一个概念：栈和队列是一对好兄弟。队列先进先出，适合处理“按顺序等待”的任务，比如打印队列；栈后进先出，适合处理“最近优先”的任务。学算法到后面你会发现，很多题就是在两个极端之间选边站。
1.2 为什么很多人刷题时认不出栈
有个很反直觉的现象：大家学栈的时候都学得很快，但刷题时一遇到栈题就懵，或者绕远路用其他方法硬解。原因在于——认出题目需要栈，靠的不是背概念，而是对“数据流动方向”的敏感度。
举个例子，DFS（深度优先搜索）其实就是用栈来做的。递归版本靠的是系统调用栈，显式版本则是我们自己开一个栈。但很多题解只写“深度优先遍历”，几乎不提栈。同样，Tarjan 算法找强连通分量、回溯法做排列组合，底层全是栈。你如果只盯着“栈”两个字去找题，永远只能做那种题干里明说“用栈实现”的题；真正的考点，是那些题面里根本不说栈，但解题非它不可的问题。这种“识别能力”会在后面几节里反复练习。先记一句话：任何需要“回到最近一个未完成状态”的操作，都在栈的射程范围内。
顺带说一句，全栈工程师那个“栈”是技术栈的意思，和今天这个后进先出的数据结构不是一回事。别在面试时把这两个概念搞混，真的有人这么干过。
2. 手写两种栈：数组栈的扩容细节与链表栈的指针开销
刷题时直接用 STL 的std::stack就够了，但自己手写一遍实现，会对“栈为什么快”“栈为什么容易爆”有更真实的体感。这里给出两种最常见的实现。
2.1 数组栈：扩容策略是核心
数组栈的核心是维护一个连续数组和栈顶下标。我用 C++ 模板写一个精简版：
#include <stdexcept> template<typename T> class ArrayStack { private: T* data; int capacity; int topIndex; // 栈顶元素下标，空栈时为 -1 public: explicit ArrayStack(int cap = 16) : capacity(cap), topIndex(-1) { data = new T[capacity]; } ~ArrayStack() { delete[] data; } void push(const T& val) { if (topIndex + 1 == capacity) { expand(); } data[++topIndex] = val; } void pop() { if (empty()) { throw std::runtime_error("stack underflow"); } --topIndex; } T& top() { if (empty()) { throw std::runtime_error("stack underflow"); } return data[topIndex]; } bool empty() const { return topIndex == -1; } int size() const { return topIndex + 1; } private: void expand() { int newCap = capacity * 2; T* newData = new T[newCap]; for (int i = 0; i <= topIndex; ++i) { newData[i] = data[i]; } delete[] data; data = newData; capacity = newCap; } };两个关键点。第一，topIndex初始为 -1，push 时先加一再写入，pop 时直接减一，逻辑最省事。第二，扩容为什么选二倍而不是“容量 + 固定值”？因为二倍扩容能保证均摊代价是 O(1)：每扩容一次，新容量至少能容纳之前已有的全部元素，之后的 n 次 push 都不用再扩容，把一次 O(n) 的拷贝摊到 n 次操作里，每次均摊下来还是常数时间。固定增量则会让扩容频率过高，整体均摊到 O(n)。
2.2 链表栈：不需要扩容，但每个节点都付了指针钱
链表栈的思路是用链表头当栈顶，每次 push 在头部插入新节点：
template<typename T> class LinkedStack { private: struct Node { T val; Node* next; Node(const T& v, Node* n) : val(v), next(n) {} }; Node* head; // 链表头即栈顶 int count; public: LinkedStack() : head(nullptr), count(0) {} ~LinkedStack() { while (head) { Node* cur = head; head = head->next; delete cur; } } void push(const T& val) { head = new Node(val, head); ++count; } void pop() { if (empty()) { throw std::runtime_error("stack underflow"); } Node* cur = head; head = head->next; delete cur; --count; } T& top() { if (empty()) { throw std::runtime_error("stack underflow"); } return head->val; } bool empty() const { return head == nullptr; } int size() const { return count; } };注意这里有个隐藏开销：每次 push 都是一次new，也就是一次堆内存分配。频繁的小分配在真实系统里可能成为性能瓶颈，而且每个节点都要额外存一个 next 指针，64 位系统下就是 8 字节。如果栈里存的是 int，那光是指针开销就抵得上一个元素了。
2.3 选型对比，以及一个 STL 冷知识
| 对比维度 | 数组栈 | 链表栈 |
|---|---|---|
| 内存布局 | 连续内存，缓存友好 | 节点分散，缓存命中率低 |
| 扩容行为 | 容量满时倍增，需要拷贝已有元素，单次最坏 O(n) | 无需扩容，每次 push 新建节点 |
| 单次操作均摊 | O(1) | O(1) |
| 空间开销 | 预分配容量可能浪费少量内存 | 每个节点多一个 next 指针 |
| 典型场景 | 高频读写、资源受限环境 | 容量完全不可预估的场景 |
我的建议很直接：算法题里直接用std::stack；真实项目里除非有明确理由，否则默认数组栈。这里有个很多人不知道的小细节——C++ 的std::stack默认底层容器其实是std::deque，不是std::vector。deque 是分段连续的结构，头部和尾部插入都是 O(1)，所以std::stack的 push/pop/top 都稳定是常数时间。想知道为什么，往下看到栈帧那一节就明白了：栈这种“只在尾部操作”的结构，用 deque 实现最省心。
3. 括号匹配这类“对称性”题目：配对与嵌套是栈的直觉信号
3.1 为什么计数法解决不了括号问题
很多人在初学字符串处理时，遇到括号先想到计数：统计左右括号数量相等就合法。这个思路在只有一种括号时能通过一部分用例，但一旦括号类型变多，立刻失效。看这个反例：([)]。左括号两个、右括号两个，数量完全对得上，但它并不是一个合法的括号序列，因为[还没闭合，)就出现了。
为什么会这样？因为括号合法性要求的不是“总数匹配”，而是“关闭顺序和打开顺序严格反向”。最近打开的括号必须最先关闭，这恰恰就是后进先出。所以括号匹配这类题，从见题的第一秒就应该往栈上想：遍历字符串，遇到左括号就压栈，遇到右括号就弹栈检查是否匹配。栈天然保存了“还没闭合的左括号，按什么顺序等着被关闭”。
3.2 完整解法与代码走读
这是 LeetCode 20 题 Valid Parentheses，算是栈题的入门标配：
bool isValid(string s) { stack<char> st; for (char c : s) { if (c == '(' || c == '[' || c == '{') { st.push(c); } else { if (st.empty()) { return false; // 没有左括号可配，直接失败 } char top = st.top(); if ((c == ')' && top == '(') || (c == ']' && top == '[') || (c == '}' && top == '{')) { st.pop(); } else { return false; } } } return st.empty(); }复杂度很漂亮：每个字符最多压栈一次、弹栈一次，时间 O(n)，空间 O(n)。走一遍[()]：遇到[压栈，遇到(压栈，遇到)弹出(匹配成功，遇到]弹出[匹配成功，最后栈空，合法。再看([)]：遇到(压栈，遇到[压栈，遇到)时栈顶是[，不匹配，直接返回 false。栈顶状态就是“最近一个还没闭合的左括号”，判断起来干净利落。
3.3 同类变体：路径简化与标签校验
括号题只是这类“配对嵌套”问题最朴素的形态，同一套思想能延伸到很多看起来不像括号的题。比如路径简化（LeetCode 71），把/a/./b/../../c/简化为/c：用栈记录路径片段，遇到.忽略，遇到..就弹出上一级，最后把栈里剩下的片段拼起来。这不就是“最近访问的路径优先被撤销”吗。
再比如 HTML 标签嵌套校验：<div><p>text</p></div>合法，<div><p></div></p>不合法。标签的开启和闭合天然是一对配对关系，而且后开的标签必须先闭，和括号一模一样。以后看到任何“外部元素包裹内部元素、内部先闭合”的题，都默认往栈上想。
4. 单调栈：把“下一个更大元素”从暴力优化成模板
4.1 先看暴力解法为什么慢
“找出数组中每个元素的下一个更大元素”，听起来很简单。暴力思路也直接：对每个位置 i，从 i+1 往后扫描，找到第一个比 nums[i] 大的数。但最坏情况，比如一个严格递减的数组，每个位置都要扫到最后，总复杂度 O(n²)。题目一卡到十万级数据量，直接超时。
关键在于，暴力解法浪费了大量重复扫描。你扫描后面的元素时，前面已经扫过的比较关系没有保存下来，导致同一对元素被反复比较。单调栈干的事情，就是把“谁比谁大”这种关系用一趟线性扫描全部记下来。
4.2 单调栈模板的构造逻辑
单调栈的模板我建议直接背下来，再理解原理：
vector<int> nextGreaterElement(vector<int>& nums) { int n = nums.size(); vector<int> res(n, -1); stack<int> st; // 存下标，栈底到栈顶单调递减 for (int i = 0; i < n; ++i) { while (!st.empty() && nums[i] > nums[st.top()]) { res[st.top()] = nums[i]; // 当前元素就是栈顶的下一个更大元素 st.pop(); } st.push(i); } return res; }核心逻辑是这样：栈里维护的是一串单调递减的下标序列。遍历到新元素时，只要它比栈顶元素大，就说明栈顶元素“下一个更大元素”找到了，于是弹出并记录答案。这个新元素继续和新的栈顶比，直到栈顶比它大或者栈空，然后把自己压进去。每个元素最多进栈一次、出栈一次，所以整体 O(n)。
走一遍[2, 1, 5, 6, 2, 3]：2 和 1 依次入栈（递减）。遇到 5，比栈顶的 1 大，弹出 1 记录答案 5；再比栈顶的 2 大，弹出 2 记录答案 5；压入 5。遇到 6，弹出 5 记录答案 6。后面 2 入栈，遇到 3 弹出 2 记录答案 3。最后栈里剩下 6 和 3，没有更大元素，答案保持初始化的 -1。结果[5, 5, 6, -1, 3, -1]，和暴力算出来的一模一样。
4.3 三个高频变体与最小栈彩蛋
单调栈的变体非常多，但底层都是同一个模板换皮：
| 变体 | 栈的单调性 | 弹出时记录什么 |
|---|---|---|
| 下一个更大元素 | 递减栈 | 当前元素值 |
| 每日温度 | 递减栈 | 当前下标与栈顶下标之差 |
| 柱状图最大矩形 | 递增栈 | 以弹出柱子为高的矩形面积 |
| 接雨水 | 递减栈 | 弹出位置可接的雨水量 |
每日温度（LeetCode 739）就是“下一个更大元素”的孪生题，只是答案从“更大的值”变成“等了多少天”，也就是下标差，模板几乎不用改。柱状图最大矩形（LeetCode 84）稍微绕一点：维护单调递增栈，当当前柱子比栈顶矮时，说明以栈顶柱子为高的矩形右边界已经确定，弹出并计算宽度和面积；为了处理末尾还留在栈里的柱子，通常会在 heights 末尾补一个高度为 0 的哨兵。核心转化一句话：找“左右第一个更矮的柱子”，这个动作就是单调栈的专长。
最后回头解决文章开头那位候选人卡住的最小栈。要求 push、pop、getMin 都 O(1)，常规思路是 getMin 时遍历整个栈，太慢。答案其实一句话：额外维护一个辅助栈，每次 push 时把“当前最小值”也压进辅助栈，pop 时同步弹出。原理很简单，但面试里能想到的人不多。这揭示了一个更通用的技巧：一个栈不够用，就再加一个栈。“栈 + 辅助栈”的组合在算法题里出现频率不低。
5. 栈帧与递归：函数调用栈到底怎么工作
5.1 一次函数调用在栈上发生了什么
讨论完算法里的栈，必须回到系统层面看看“栈”这个字的本体。假设 main 调用 funcA(3)，编译器眼中大致是这么一套流程：
- 调用方把实参按约定方式压栈（具体顺序由 ABI 决定，这里按最经典的栈式调用理解）；
- 压入返回地址——也就是 funcA 执行完后，main 要从哪条指令继续往下走；
- 进入 funcA 后，先保存 main 的栈帧指针（frame pointer），这样才能在返回时恢复 main 的栈现场；
- 栈指针继续往低地址方向移动，为 funcA 的局部变量腾出空间。
这几样东西合在一起，就是一次函数调用的“栈帧”。funcA 再调用 funcB，就再压一层新栈帧。函数返回时，按完全相反的顺序清理：销毁局部变量、恢复旧帧指针、弹出返回地址、跳回调用点继续执行。
你调试崩溃时看到的 backtrace（调用栈回溯），就是沿着栈帧里保存的地址链一级一级往回找现场。崩溃时打印调用栈，是排查问题最快的手段；ARM 等嵌入式平台上的回溯规则由 ABI 定义，但本质都是跟着返回地址走。理解栈帧，调试器的“调用堆栈”窗口就不再是黑魔法了。
5.2 递归为什么天生依赖栈
递归代码看着简单，底层靠的其实就是这套栈帧机制。每次递归调用自身，就压入一层新栈帧，参数、局部变量、返回地址都留在各自独立的帧里；递归返回，则逐帧弹出。所谓“回溯”，不过是系统把之前手动保存的状态自动恢复了一遍。
这一点对算法学习特别重要。你写一个二叉树的 DFS，递归版本由系统栈自动帮你记录“当前走到哪个节点、左边有没有访问”，完全不用手动管理；一旦改成迭代版本，你就得自己开一个栈来模拟这个过程。很多人觉得“用栈写 DFS”很别扭，就是因为没想明白：你其实是在复刻系统栈帧的行为。
5.3 栈溢出的真相与应对
Linux 下主线程栈默认一般是 8MB，嵌入式或 MCU 平台可能只有几 KB。无限递归，或者递归深度大到超过栈容量，就会栈溢出，程序直接崩溃。这里的“栈”就是函数调用栈，不是算法题里你自己定义的那个栈。
应对方式有几个：限制递归深度；把递归改写成显式栈加循环；某些语言支持尾递归优化，编译器会把尾调用优化成跳转，不再压新栈帧。面试时聊到“递归的缺点”，能答出“每一层调用都保存完整上下文、占用栈空间、深度过大会栈溢出”，就算过了这一题。
6. 堆和栈的内存之争：变量到底存在哪
6.1 先分清两个“堆”
这是我在面试里问过很多次的问题：“堆和栈有什么区别？”回答五花八门，其中有一个高频误区——把算法里的堆（二叉堆、优先队列）和内存里的堆（malloc/new 分配的区域）混为一谈。这两个概念只是恰好同名：
- 数据结构中的堆：一种完全二叉树，用来实现优先队列，典型操作是 push 和取最值；
- 内存区域中的堆：进程地址空间里一块自由管理的内存，动态分配的对象的家。
讨论算法题时说“用堆做”，多半指优先队列；讨论内存布局时说“对象在堆上”，指动态分配。两者不是一回事，面试时先说清楚你问的是哪个，能避免很多尴尬。
6.2 局部变量、全局静态变量、堆对象都放在哪
| 变量类型 | 存放位置 | 生命周期 |
|---|---|---|
| 局部变量（栈变量） | 栈帧 | 函数调用期间 |
| 全局变量 / 静态变量 | 静态存储区 | 程序整个运行期 |
| new / malloc 产生的对象 | 堆 | 从分配直到释放（或由 GC 回收） |
函数里定义一个“很大的局部数组”，其实就压在栈帧里，8MB 的栈很容易被几十 MB 的数组直接打穿。算法题里见过有人直接在函数里开int a[1000000]，本地跑得好好的，换到在线评测环境直接崩溃，就是因为栈空间不够。大块数据要么放全局/静态区，要么用 new 放堆上，这是实际做题时应该避开的坑。
6.3 “栈比堆快”的真相，以及它对算法题的影响
栈的分配就是移动一下栈指针，一条指令完成；堆分配要搜索空闲块、维护元信息、处理并发锁，确实慢不少。另一个原因是缓存局部性——栈上的局部变量往往挨得近，访问友好；堆对象散落各处，cache miss 概率高。但话说回来，这只是普遍现象，不是铁律。如果你一次性申请一大块连续堆内存，访问速度同样能拉满。所以别只背“栈快堆慢”的结论，面试追问的时候要能讲清楚背后这两个原因。
这一节对算法题的直接影响是：所有高频状态都尽量压在栈上，比如用局部变量而不是反复 new 对象；但容量太大的数据结构，比如图的邻接表、大数组，就老老实实放堆里。这个取舍在写工程代码的时候比刷题时更明显。
7. 栈题识别清单与五个高频翻车现场
7.1 三个“该用栈”的信号
我把压箱底的识别方法整理成三句话，刷题时可以直接对照：
- 配对与嵌套关系。关闭顺序和打开顺序相反，比如括号、HTML 标签、嵌套作用域。看到这类题，默认栈。
- 需要回退到最近状态。撤销操作、路径简化、浏览器后退、DFS 回溯。这类题本质是“回到最近一个未完成状态”，栈是天然的容器。
- 与“下一个更大/更小”有关。求某个元素右侧第一个比它大（或小）的元素，或者等价的距离、面积问题。这是单调栈的主场。
判断标准很简单：拿一张纸模拟数据流，如果某个元素处理完后，后面再需要它时会用到“它是最近被处理的”，那就是栈。
7.2 五个高频翻车现场
这些坑我见过太多次了，自己在初学阶段也都踩过，写在这里当警示牌。
- 弹空栈。C++ 的
std::stack::top()和pop()在空栈上是未定义行为，不是抛异常。所有弹栈操作前先判空，这是最基本的防御。 - 单调栈遗留元素。遍历结束后，栈里剩下的元素都没有“下一个更大/更小”的答案。很多人忘记处理，或者不知道初始化答案数组时就要预设好默认值。模板里
res(n, -1)就是在给这部分兜底。 - 存值还是存下标。单调栈到底存元素值还是存下标？需要记录位置信息时（每日温度、柱状图面积）必须存下标，访问值再用
nums[st.top()]取。只比较大小不关心位置的简化问题，才可以只存值。 - 表达式求值的顺序。中缀表达式转后缀、或者用两个栈直接求值时，数字栈和符号栈谁先弹、括号处理完再弹哪一层，顺序错了结果全错。我的经验：遇到右括号，先把括号内的符号栈全部清空，再弹数字栈；遇到运算符，先弹出栈里优先级不低于当前运算符的所有符号，再压当前符号。
- 递归转迭代的深度切换。有些题的递归解法看着优雅，但输入一大就把系统栈打爆。要么限制递归深度并逐层剪枝，要么改成显式栈加循环。判断标准很简单：递归深度是否可能超过几千层，会的话就趁早转迭代。
最后分享一个我自己的习惯：拿到一个新题，先不急着看标签，而是问一句“这里存不存在一种最近优先的关系”。如果存在，哪怕题面里没有“栈”这个字，也基本可以往栈的方向想。栈这东西看着小，但它其实是很多看似复杂问题的底层骨架。能把这一层想通，括号匹配、单调栈、递归转迭代这些题目，也就不再是背模板，而是变成一种顺手的直觉了。
