Java传递Stack到getMax函数触发EmptyStack异常问题排查

核心错误：对象引用赋值未实现栈拷贝 #

你写的Stack<Integer> s=st; 是典型的Java对象引用赋值，没有创建新的栈实例：

• st是指向原栈对象的引用，赋值给s之后，s和st指向内存中同一个栈对象
• 你在getMax中对s执行pop()操作，本质就是直接删除原栈中的元素，调用一次getMax后原栈会被完全清空
• 后续再执行类型2的弹栈操作，或者再次调用getMax取栈顶时，栈已经为空，自然抛出emptyStack exception

部分测试用例可正常运行的原因 #

编号0、2、27的测试用例大概率满足以下特征：

• 整个测试流程中getMax操作只出现一次
• getMax是测试用例的最后一步操作，调用之后没有后续的弹栈、取最大值操作，所以不会触发空栈异常

临时修复（兼容现有逻辑） #

如果要保留现有遍历栈找最大值的逻辑，需要先对原栈做深拷贝，再操作拷贝后的栈：

static void getMax(Stack<Integer> st)
{
    // 创建新的栈实例，拷贝原栈所有元素，和原栈完全独立
    Stack<Integer> s = new Stack<>();
    s.addAll(st);
    int max=s.peek();
    s.pop();
    while(!s.empty())
    {
        if(s.peek()>max)
            max=s.peek();
        s.pop();       
    }
    System.out.println(max);
}

优化方案（提升运行效率） #

现有方案每次getMax的时间复杂度是O(n)，如果测试用例规模大很容易超时，推荐使用双栈方案实现O(1)时间复杂度的取最大值操作：

• 维护两个栈：普通栈存所有元素，最大值栈只存当前的最大值序列
• 元素入栈时，如果入栈元素大于等于最大值栈的栈顶，同步将元素推入最大值栈
• 元素出栈时，如果弹出的元素等于最大值栈的栈顶，同步弹出最大值栈的栈顶
• 取最大值时直接返回最大值栈的栈顶即可

内容的提问来源于stack exchange，提问作者Titan Demon