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

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 Notation，RPN）是波兰逻辑学家 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，计算 2+1=3，压栈 stack: [3] 扫描 "3" -> 数字，压栈 stack: [3, 3] 扫描 "*" -> 运算符，弹出 3 和 3，计算 3*3=9，压栈 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) { Deque<Integer> 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=20 时已经有超过 65 亿种可能，枚举法直接爆炸。所以面试时如果说出这种思路，至少能证明你意识到了“出栈序列不是随意的”，但紧接着需要立刻说出更优方案。

3.3 最优解法：用辅助栈模拟真实过程

正确的思路是：不要凭空去验证，而是用辅助栈把这个出栈过程完整地“演”一遍。如果演得出来，就是 true；如果演到一半卡住了，就是 false。

算法流程：

1. 维护一个辅助栈stack，同时用两个指针i和j分别指向pushed和popped的当前进度。
2. 依次将pushed[i]压入栈，i++。
3. 每次压入后，循环检查：如果栈不为空且栈顶元素等于popped[j]，就把栈顶弹出，j++。
4. 循环第 2、3 步，直到pushed中的所有元素都压入过栈。
5. 最后检查j是否等于popped.length。如果等于，说明整个popped序列都被成功模拟弹出，返回 true；否则返回 false。

Java 实现：

public boolean validateStackSequences(int[] pushed, int[] popped) { Deque<Integer> 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/5=2，压栈 stack: [4, 2] 扫描 "+" -> 弹出 2 和 4，计算 4+2=6，压栈 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是否越界。这些错误恰恰是面试时最容易现场翻车的点。我建议你把常见的错误写法记在笔记本上，面试前翻一遍，比多刷十道题都管用。

第三，多想想“为什么面试官要考这个”。栈与队列的题目，本质上考的是数据结构特性和工程思维的结合。逆波兰表达式考的是“如何把人类表达转换成机器可执行指令”，压入弹出序列考的是“如何在顺序约束下验证一个过程是否可行”。这两个能力，函数调用栈、编译原理、消息队列、任务调度里全都用得上。想清楚这一点，你就不是在背题，而是在建立真正的底层认知。

这套题的精髓，说白了就是八个字：先进后出，步步为营。栈的特性大家都懂，但能不能在题目的约束下严谨地模拟这个过程，这就是面试官真正想看的。把这篇讲的细节都消化好，下次再遇到栈相关的题目，你会从容很多。