栈与队列高频面试题：逆波兰表达式与压入弹出序列全解析

1. 先从一道“看起来很简单”的题说起栈和队列是算法面试里最容易让人掉以轻心的板块。二叉树、动态规划、图论听起来吓人大家会提前认真准备反而是Stack和Queue很多人在简历上写“熟练掌握数据结构”真到面试时却连一道逆波兰表达式求值都写不利索。这个系列的第二篇我挑了栈与队列里最典型的两道题逆波兰表达式求值和栈的压入弹出序列。一个考“怎么用栈”——给你一串后缀表达式让你算出结果一个考“怎么建栈”——给你入栈序列和出栈序列让你判断这个出栈顺序能不能真实发生。两道题都来自高频面试原题LeetCode 上分别对应150. Evaluate Reverse Polish Notation和946. Validate Stack Sequences字节、阿里、美团、腾讯的算法题库里基本都有它们的身影。为什么把这两道放一起讲因为它们的考察点完全互补逆波兰表达式考察“栈作为计算工具”的机械执行过程压入弹出序列考察“栈作为状态机”的演变逻辑。前者侧重代码实现能力后者侧重逻辑推导能力。把这两道吃透栈与队列的面试题就打通了大半。适合看这篇文章的人正在刷题准备春招秋招的应届生、工作几年想跳槽但算法基础生疏的开发者、以及想系统梳理栈与队列考点的学习者。我会从题目本身出发把暴力解法、最优解法、正确性分析、面试表达技巧全讲透最后附上我在实际面试和刷题过程中踩过的坑。2. 逆波兰表达式人类写中缀机器读后缀2.1 为什么要发明后缀表达式先问一个很基础但很多人答不上来的问题为什么我们平时写数学表达式要用3 4 * 2这种形式而计算机更喜欢3 4 2 * 因为中缀表达式对人类友好但对机器不友好。3 4 * 2需要知道“乘法优先级高于加法”还需要处理括号——这本质上是一套语法规则。而3 4 2 * 不需要任何优先级和括号运算符直接跟在它要操作的数字后面计算过程可以严格地从左到右扫描遇到数字就压栈遇到运算符就弹出两个数字做运算再压回去。这里有个经典的类比中缀表达式像人类阅读的书面语言有语法、有歧义后缀表达式像机器执行的指令序列每一步做什么都是确定的。逆波兰表达式Reverse Polish NotationRPN是波兰逻辑学家 Jan Łukasiewicz 在 1920 年代提出的当初是为了研究命题逻辑的括号消除问题。后来发现它特别适合计算机实现因为求值过程只需要一个栈不需要递归下降、不需要语法树、不需要回溯。2.2 手工模拟一次完整求值过程题目描述是这样的给你一个字符串数组tokens表示一个逆波兰表达式比如[2, 1, , 3, *]求值结果应该是(2 1) * 3 9。我们手工模拟一遍tokens: [2, 1, , 3, *] 扫描 2 - 数字压栈 stack: [2] 扫描 1 - 数字压栈 stack: [2, 1] 扫描 - 运算符弹出 1 和 2计算 213压栈 stack: [3] 扫描 3 - 数字压栈 stack: [3, 3] 扫描 * - 运算符弹出 3 和 3计算 3*39压栈 stack: [9] 遍历结束栈顶也就是唯一元素 9就是答案。整个过程如果用一句话概括数字进来就等着运算符来了就把最近等的两个数字叫出来算掉结果再回去等着。这就是栈的 LIFO后进先出特性在表达式求值中的最直接体现。2.3 最容易踩的坑减法/除法的操作数顺序很多人第一次写这道题代码结构和思路都没问题但一提交就错一半。问题出在减法和除法上。假设表达式是[5, 3, -]正确结果是5 - 3 2。你的代码如果写成int b stack.pop(); int a stack.pop(); stack.push(a - b);结果为 2正确。但如果写成int b stack.pop(); int a stack.pop(); stack.push(b - a);结果为 -2错误。为什么因为栈顶是后入栈的元素。扫描到运算符时栈内顺序是[num1, num2]其中 num2 是后入栈的、也就是表达式里靠后的数字。第一次 pop 拿到的是 num2第二次 pop 拿到的才是 num1。所以必须是a - b先弹出来的是被减数的反面别搞反。这个坑我在面试现场亲眼见过候选人踩。代码写得很流畅最后跑测试用例[4, 3, -]输出1他自己都没发现是反的。因为4 - 3 1和3 - 4 -1恰好绝对值一样这种用例具备迷惑性其实用例设计得不好换个用例立刻暴露。2.4 标准实现与边界处理完整实现如下Java 版本public int evalRPN(String[] tokens) { DequeInteger stack new ArrayDeque(); for (String token : tokens) { if (isOperator(token)) { int b stack.pop(); int a stack.pop(); switch (token) { case : stack.push(a b); break; case -: stack.push(a - b); break; case *: stack.push(a * b); break; case /: stack.push(a / b); break; } } else { stack.push(Integer.parseInt(token)); } } return stack.pop(); } private boolean isOperator(String token) { return token.length() 1 -*/.indexOf(token) 0; }几个容易被忽视的细节操作符判断tokens数组里的元素全是字符串要区分数字和运算符。用char c token.charAt(0)判断时注意负数-13的第一个字符也是-会被误判为运算符。安全做法是先判断字符串长度长度为 1 且是运算符才算运算符。除法向零取整LeetCode 原题明确要求“向零截断”也就是-7 / 3 -2而不是-3向下取整。Java 的整数除法默认就是向零取整所以直接用/没问题。但如果面试官让你手写 Python 实现要注意int(negative / positive)的行为和//不一样这是个很容易在实现细节上栽跟头的地方。栈的数据结构选型Java 里推荐用ArrayDeque而不是Stack。Stack继承自Vector所有方法都加了同步锁性能差面试官看到你用Stack虽然不会扣分太多但用ArrayDeque更干净也顺便展示了你对 Java 集合框架的理解。2.5 为什么这个解法的时间复杂度是 O(n)每个 token 最多入栈一次、出栈一次入栈出栈都是 O(1)。所以总时间复杂度是 O(n)n 是 tokens 的长度。空间复杂度 O(n)最坏情况下表达式全是数字比如[1, 2, 3, 4, 5]所有数字都压在栈里此时栈的深度就是 n。顺便说一个面试加分点这道题有一种“不需要完整栈”的递归写法从右往左遍历遇到运算符递归处理可以把空间复杂度优化到 O(1) 的递归深度仍然是 O(n)但栈空间由系统管理。不过这种写法可读性差、面试中容易翻车我只在博客里提一句不建议面试时主动秀这个操作除非你已经背得滚瓜烂熟。3. 栈的压入弹出序列验证一个“虚构”的出栈过程3.1 读懂题目不是让你求出栈序列而是判断可行性题目描述输入两个整数序列pushed和popped第一个序列表示栈的压入顺序请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。举个例子pushed [1, 2, 3, 4, 5] popped [4, 5, 3, 2, 1]答案是 true。模拟过程是push 1 push 2 push 3 push 4 pop - 4 push 5 pop - 5 pop - 3 pop - 2 pop - 1再看一个反例pushed [1, 2, 3, 4, 5] popped [4, 3, 5, 1, 2]答案是 false。因为你没法在不弹出 5 的情况下把 1 弹出来——5 是最后压入的只要它还在栈里1 就不可能先出来。这道题剑指 Offer 里有原题面试题31牛客网上也有一模一样的题目JZ31所以面试里出现的概率极高。它考察的核心是你能否用栈的 LIFO 特性去一步一步“倒推”一个过程。3.2 暴力思路枚举所有可能的出栈序列如果不知道怎么做最容易想到的思路是先用pushed生成所有可能的出栈序列再判断popped是否在其中。但这是一个排列问题n 个元素的出栈序列数量是第 n 个卡特兰数增长极快n可能的出栈序列数5421016796159694845206564120420n20 时已经有超过 65 亿种可能枚举法直接爆炸。所以面试时如果说出这种思路至少能证明你意识到了“出栈序列不是随意的”但紧接着需要立刻说出更优方案。3.3 最优解法用辅助栈模拟真实过程正确的思路是不要凭空去验证而是用辅助栈把这个出栈过程完整地“演”一遍。如果演得出来就是 true如果演到一半卡住了就是 false。算法流程维护一个辅助栈stack同时用两个指针i和j分别指向pushed和popped的当前进度。依次将pushed[i]压入栈i。每次压入后循环检查如果栈不为空且栈顶元素等于popped[j]就把栈顶弹出j。循环第 2、3 步直到pushed中的所有元素都压入过栈。最后检查j是否等于popped.length。如果等于说明整个popped序列都被成功模拟弹出返回 true否则返回 false。Java 实现public boolean validateStackSequences(int[] pushed, int[] popped) { DequeInteger stack new ArrayDeque(); int j 0; for (int num : pushed) { stack.push(num); while (!stack.isEmpty() stack.peek() popped[j]) { stack.pop(); j; } } return j popped.length; }关键点在于peek()和popped[j]相等时栈顶就是当前“最应该弹出”的元素。因为一旦一个元素被压入栈它上方只会有比它更晚被压入的元素。如果栈顶恰好是popped[j]那这个元素现在不弹以后也弹不了它上面的元素会越来越多所以此时必须弹。3.4 正确性论证为什么“栈顶匹配就弹出”是安全的很多初学者会担心栈顶匹配popped[j]时是否应该等一下也许先弹出别的元素也能构造出相同的出栈序列答案是不需要。因为栈顶元素是栈内所有元素中最晚压入的如果要弹出popped[j]它必须是当前栈顶之外的其他元素那意味着必须先把栈顶元素弹出但栈顶元素在popped[j]之后的位置才出现一旦提前弹出就不可能按顺序弹出了。所以“栈顶匹配就弹出”不仅是安全的而且是唯一可能的选择。这就是这道题的贪心性质每一步的操作都被前序条件约束得死死的。这里有一个更直观的解释出栈序列相当于给每个元素盖了一个“弹出时间戳”。如果元素 x 比元素 y 后入栈但想比 y 先出栈那 x 必须压在 y 上方弹出时先弹出 x 再弹出 y。反过来如果 y 先入栈且 x 后入栈但出栈序列要求 y 在 x 之前弹出那要求就矛盾了必然不可能。这个逻辑用反证法可以严格证明面试时口头说明一遍就够了。3.5 边界情况与易错点pushed 和 popped 长度相等但完全不相干比如pushed[1,2,3], popped[3,1,2]模拟时会发现压完 3 后栈顶是 3 确实等于 popped[0]弹出接着 popped[1]1但栈顶是 2且后续不会再压入任何元素返回 false。这个用例很好能检验代码是否在pushed遍历结束后正确退出。空数组pushed[]且popped[]时直接返回 true。LeetCode 的测试用例里可能有这个边界代码里for循环不会执行j popped.length自然成立。popped 里存在 pushed 中不存在的元素题目约定两个数组长度相等且元素互不重复所以正常不会出现这种非法输入。但如果你在真实面试中写代码可以考虑加一个防御性检查给面试官留下严谨的印象。while 循环里的数组越界风险while (!stack.isEmpty() stack.peek() popped[j])这个条件里如果j已经越界也就是 popped 数组已经遍历完了再访问popped[j]会抛异常。但是因为题目保证 popped 长度和 pushed 相等且总共只会弹出 pushed.length 次所以 j 最坏情况刚好等于 popped.length 时 while 条件里stack.isEmpty()通常已经为真所有元素都弹出了不会进入访问。不过写代码时养成先判断j popped.length的习惯更稳妥。4. 两道题背后的“栈思维”从算法题到工程实践4.1 逆波兰表达式在真实世界的应用场景很多人觉得逆波兰表达式是纯理论玩具实际上它在真实工程中非常常见。我一直强调一个观点如果某个算法只出现在面试题里那它可能不值得深究但如果它同时出现在编译器、计算器和工业软件里那它值得你花时间彻底搞懂。逆波兰表达式最大的应用场景是表达式求值。很多手写计算器、电子表格产品在解析用户输入时先把中缀表达式转成后缀表达式再用一个栈直接求值。这样做的好处是中缀转后缀只需要一次从左到右的扫描后缀求值也只需要一次从左到右的扫描两个 O(n) 的扫描就完成了整个人类数学表达式的计算。相比递归下降解析器动辄上百行的语法分析代码这个方案在简单场景下要轻量得多。另外JVM 的字节码指令设计也借鉴了这个思想。JVM 是一个基于栈的虚拟机指令iload、iadd、imul的语义就是“把值压入操作数栈”“弹出栈顶两个值做加法”等等和逆波兰表达式的执行过程一模一样。理解了逆波兰表达式你就理解了 JVM 操作数栈的工作原理。4.2 压入弹出序列与函数调用栈的关联压入弹出序列这道题表面上看只是在验证一个抽象栈的行为但实际上它和真实系统中的函数调用栈完全是同一个模型。考虑一个简单的递归函数void f(int n) { if (n 0) return; f(n - 1); System.out.println(n); }调用f(3)时函数栈帧的入栈顺序是f(3) - f(2) - f(1)出栈顺序是f(1) - f(2) - f(3)。这个“后调用的先结束”就是 LIFO。如果你有一串函数调用记录想要判断是否合法本质上就是在做一道压入弹出序列的验证题。调试界有个经典问题叫“栈回溯stack unwinding / backtrace”程序崩溃后调试器要根据栈帧中的返回地址把整个调用链恢复出来。这个恢复过程就依赖栈帧严格符合后进先出的顺序一旦栈帧被破坏缓冲区溢出攻击的常见目标回溯就会失败程序连“我是谁、我从哪里来”都不知道了。这也是为什么栈溢出攻击一直是安全领域的经典问题——破坏了栈的顺序就是破坏了程序的控制流。4.3 队列相关的高频考点从“栈和队列”到“消息队列”既然这个系列是“栈与队列”队列部分也不能完全略过。面试中队列的考察重点通常有两个方向一是基础队列的手写实现用数组实现循环队列、用两个栈实现队列、用两个队列实现栈。这三个“互相实现”的题目几乎是栈与队列板块的“全家桶”基本必考。二是阻塞队列与生产者消费者模型特别是在 Java 面试里ArrayBlockingQueue、LinkedBlockingQueue的实现原理、线程池为什么用阻塞队列、消息队列的重复消费和顺序问题都是高频问题。它们看起来像分布式中间件八股文但底子上就是“先进先出 有界/无界 多线程安全”的组合。这里我多说一句栈与队列这两类数据结构在工程应用里的侧重点是镜像的。栈强调“撤销、回溯、优先级反转”队列强调“排队、缓冲、削峰填谷”。面试官问栈的时候一般在考察你对 LIFO 的理解深度问队列的时候在考察你对系统吞吐和异步解耦的理解深度。所以备考时不要只刷题试着把每道题映射到真实系统的一个场景里记忆会牢固得多。5. 实操记录与面试表达技巧两道题如何写出“满分答案”5.1 面试时先说思路再写代码我带过不少候选人模拟面试发现一个普遍问题拿到题目就直接开写写到一半发现思路不对再停下来改整个过程观感极差。正确的面试姿势是先花 30 秒把题目重述一遍再花 30 秒说明思路然后开始写代码写完最后手动跑一个用例。以逆波兰表达式为例你可以这样说“这道题我准备维护一个操作数栈。遍历 tokens遇到数字就压栈遇到运算符就弹出两个数字注意减法和除法要区分先弹出的作为右操作数、后弹出的作为左操作数计算完再压回栈。最后栈里只剩一个数字就是答案。时间复杂度 O(n)空间复杂度 O(n)。”这段话说完面试官基本就放心了。你还没写代码他已经知道你有清晰的前进路线。以压入弹出序列为例“我准备用一个辅助栈模拟整个压栈和弹栈过程。指针 i 遍历 pushed把元素压入辅助栈然后循环检查栈顶是否等于 popped[j]相等就弹出并让 j 前进。最后看 j 能否前进到数组末尾能就说明 popped 是合法的弹出序列。时间复杂度 O(n)因为每个元素最多入栈一次、出栈一次。”把思路用一两句话讲清楚比闷头写十分钟代码高级得多。5.2 手动跑用例的正确姿势写完代码面试官经常说“跑个测试用例看看”。这时候你选择哪个用例也是有讲究的。逆波兰表达式建议选[4, 13, 5, /, ]也就是4 (13 / 5) 4 2 6。因为里面有一处整数除法且能整除好算同时数字不是按顺序排列的能验证你操作数弹出的顺序是否写对。代码执行过程stack: [] 扫描 4 - 压栈 stack: [4] 扫描 13 - 压栈 stack: [4, 13] 扫描 5 - 压栈 stack: [4, 13, 5] 扫描 / - 弹出 5 和 13计算 13/52压栈 stack: [4, 2] 扫描 - 弹出 2 和 4计算 426压栈 stack: [6] 返回 6压入弹出序列建议选pushed[1,2,3,4,5], popped[4,5,3,2,1]。这个用例长、流程完整而且答案是 true不会触发边界分支。跑完后可以再补一个 false 用例比如popped[4,5,3,1,2]说明你考虑过失败情况。5.3 复盘这两道题能衍生出哪些变体面试官经常会在你做出一道题后紧跟着问变体尤其是你做得又快又好的时候。提前想好变体能让你在被追问时从容应对。逆波兰表达式的常见变体如果表达式里包含单目运算符比如负号-作为一元运算怎么处理答案是判断操作符需要的操作数个数单目就只弹一个。如果要支持中缀表达式怎么扩展答案是先用调度场算法Shunting-yard algorithm转后缀再求值。调度场算法是 Dijkstra 发明的原理就是用两个栈处理运算符优先级是这道题最自然的扩展。压入弹出序列的常见变体如果 pushed 里有重复元素算法还成立吗不成立。因为栈顶元素和 popped[j] 相等时你无法确定这个元素到底是哪一次压入的实例。这解释了为什么题目会明确“所有数字均不相等”。如果不给你 pushed只给 popped让你判断它是否可能是某个长度为 n 的序列的出栈顺序本质上和原题等价你可以用 1..n 作为 pushed 再验证。6. 我刷完这几道题后的三个习惯准备算法面试这么多年我自己也总结了一套刷“栈与队列”类题目的方法论这里分享给正在备考的朋友。第一一定不要满足于“AC”。LeetCode 上通过就算成功但面试不是这样的——面试官会要求你讲清楚复杂度、边界条件、正确性以及代码风格。所以我刷每道题都会强迫自己用至少两种方式写一遍一种是最优解法一种是暴力解法或者递归解法。写暴力解不是为了提交而是为了理解为什么最优解是对的。第二把每道题的“错误写法”都留个记录。比如逆波兰表达式把a - b写成b - a压入弹出序列忘了在 while 循环里判断j是否越界。这些错误恰恰是面试时最容易现场翻车的点。我建议你把常见的错误写法记在笔记本上面试前翻一遍比多刷十道题都管用。第三多想想“为什么面试官要考这个”。栈与队列的题目本质上考的是数据结构特性和工程思维的结合。逆波兰表达式考的是“如何把人类表达转换成机器可执行指令”压入弹出序列考的是“如何在顺序约束下验证一个过程是否可行”。这两个能力函数调用栈、编译原理、消息队列、任务调度里全都用得上。想清楚这一点你就不是在背题而是在建立真正的底层认知。这套题的精髓说白了就是八个字先进后出步步为营。栈的特性大家都懂但能不能在题目的约束下严谨地模拟这个过程这就是面试官真正想看的。把这篇讲的细节都消化好下次再遇到栈相关的题目你会从容很多。