如果说数组和链表是数据结构里的基础积木那栈就是那个“说明书上一句话就能说完实战里却最容易认不出来”的零件。后进先出四个字人人都会背但真正在看题的时候我们想到它了吗去年我面试一位候选人让他实现一个最小栈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 templatetypename 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初始为 -1push 时先加一再写入pop 时直接减一逻辑最省事。第二扩容为什么选二倍而不是“容量 固定值”因为二倍扩容能保证均摊代价是 O(1)每扩容一次新容量至少能容纳之前已有的全部元素之后的 n 次 push 都不用再扩容把一次 O(n) 的拷贝摊到 n 次操作里每次均摊下来还是常数时间。固定增量则会让扩容频率过高整体均摊到 O(n)。2.2 链表栈不需要扩容但每个节点都付了指针钱链表栈的思路是用链表头当栈顶每次 push 在头部插入新节点templatetypename 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) { stackchar 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 标签嵌套校验divptext/p/div合法divp/div/p不合法。标签的开启和闭合天然是一对配对关系而且后开的标签必须先闭和括号一模一样。以后看到任何“外部元素包裹内部元素、内部先闭合”的题都默认往栈上想。4. 单调栈把“下一个更大元素”从暴力优化成模板4.1 先看暴力解法为什么慢“找出数组中每个元素的下一个更大元素”听起来很简单。暴力思路也直接对每个位置 i从 i1 往后扫描找到第一个比 nums[i] 大的数。但最坏情况比如一个严格递减的数组每个位置都要扫到最后总复杂度 O(n²)。题目一卡到十万级数据量直接超时。关键在于暴力解法浪费了大量重复扫描。你扫描后面的元素时前面已经扫过的比较关系没有保存下来导致同一对元素被反复比较。单调栈干的事情就是把“谁比谁大”这种关系用一趟线性扫描全部记下来。4.2 单调栈模板的构造逻辑单调栈的模板我建议直接背下来再理解原理vectorint nextGreaterElement(vectorint nums) { int n nums.size(); vectorint res(n, -1); stackint 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()]取。只比较大小不关心位置的简化问题才可以只存值。表达式求值的顺序。中缀表达式转后缀、或者用两个栈直接求值时数字栈和符号栈谁先弹、括号处理完再弹哪一层顺序错了结果全错。我的经验遇到右括号先把括号内的符号栈全部清空再弹数字栈遇到运算符先弹出栈里优先级不低于当前运算符的所有符号再压当前符号。递归转迭代的深度切换。有些题的递归解法看着优雅但输入一大就把系统栈打爆。要么限制递归深度并逐层剪枝要么改成显式栈加循环。判断标准很简单递归深度是否可能超过几千层会的话就趁早转迭代。最后分享一个我自己的习惯拿到一个新题先不急着看标签而是问一句“这里存不存在一种最近优先的关系”。如果存在哪怕题面里没有“栈”这个字也基本可以往栈的方向想。栈这东西看着小但它其实是很多看似复杂问题的底层骨架。能把这一层想通括号匹配、单调栈、递归转迭代这些题目也就不再是背模板而是变成一种顺手的直觉了。