【算法避坑】栈的压入弹出序列：逻辑对了，为什么还会报 EmptyStackException？

1. 题目背景

题目：栈的压入、弹出序列（剑指 Offer 31）
描述：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。
示例：
输入：pushV=[1,2,3,4,5], popV=[4,5,3,2,1] -> 返回 true
输入：pushV=[1,2,3,4,5], popV=[4,3,5,1,2] -> 返回 false

2. 解题思路：模拟法

这就好比我们在玩一个“进出栈”的游戏。我们可以创建一个辅助栈，模拟题目描述的过程：

1. 遍历压入序列：按照 pushV 的顺序，把数字一个个放进辅助栈。
2. 即时检查：每放入一个数字，就立马看看栈顶的数字是不是 popV 当前想要弹出的那个数字（由指针 j 指向）。
3. 循环弹出：如果栈顶数字正是 popV[j] 想要的，我们就把它弹出来，并且把 j 指针往后移，继续检查新的栈顶。
4. 最终判断：如果所有操作结束后，辅助栈是空的，说明刚才的弹出顺序是合法的；否则就是非法的。

3. 易错点分析（我的“翻车”经历）

我最初写出的核心代码如下：

// ❌ 错误代码片段
for(int i=0; i<pushV.length; i++) {
    stack.push(pushV[i]);
    // 这里的条件顺序导致了 Bug
    while(j < popV.length && stack.peek() == popV[j] && !stack.isEmpty()) {
        stack.pop();
        j++;
    }
}

这段代码在逻辑上似乎没问题：只要还有元素要弹，且匹配上了，且栈不为空，就弹。
但是，Java 的逻辑运算符 && 是有顺序的！

当代码执行到 stack.peek() == popV[j] 这一步时，如果刚才的操作恰好把栈弹空了（比如 push=[1], pop=[1]，弹完之后栈空了，循环再次判断），此时调用 stack.peek() 会直接抛出 java.util.EmptyStackException。

虽然我在后面写了 && !stack.isEmpty()，但程序是从左往右执行的，还没来得及执行到判空语句，前面就已经报错挂掉了。这就好比你去开门（peek），必须先确认房子还存在（!isEmpty），如果你先去拧门把手，结果房子塌了，你就掉坑里了。

4. 正确代码与总结

修正后的代码：

// ✅ 正确代码片段
while(j < popV.length && !stack.isEmpty() && stack.peek() == popV[j]) {
    stack.pop();
    j++;
}

核心总结：

1. 防御性编程：在访问任何可能为空的容器（Stack, Queue, List）的头部或尾部元素（peek, get, top）之前，必须先检查容器是否为空。
2. 短路求值（Short-circuit evaluation）：A && B，如果 A 为假，B 就不会执行。利用这个特性，我们要把前置校验条件（如判空、判数组越界）永远放在逻辑操作的前面。
   • index < length && array[index] (先防越界，再取值)
   • obj != null && obj.value (先防空指针，再取属性)
   • !stack.isEmpty() && stack.peek() (先防空栈，再取栈顶)

5. 复杂度分析

• 时间复杂度：O(N)。虽然有两层循环（for 嵌套 while），但实际上每个元素最多被 push 一次，也最多被 pop 一次，总操作次数是线性的。
• 空间复杂度：O(N)。需要一个辅助栈，最坏情况下栈的深度等于数组长度。