java - 没有额外空间的 O(n) 中的反转堆栈不会发生

Question

我正在尝试使用递归来反转堆栈:

我能够以相反的顺序打印堆栈的元素。但是，如果我尝试插入反向元素，它就不起作用了。

设堆栈为 [0,1,2,3,4]。 4 是顶级。

这是我试过的:

private static void reverseStack(Stack<Integer> stack) {
        if (!stack.isEmpty()){
            int n=stack.pop();
            reverseStack(stack);
            System.out.println(n);
        }
    }

有了这个，我得到了正确的输出。

Output is :

0
1
2
3
4

这是我所期望的。

如果我尝试将这些元素推回堆栈，我将得到相同的堆栈而不会反转:

这是用于反转的代码:

private static void reverseStack(Stack<Integer> stack) {
        if (!stack.isEmpty()){
            int n=stack.pop();
            reverseStack(stack);
            System.out.println(n);
            stack.push(n);
        }
    }

这是从这段代码中获得的逐步堆栈:

private static void reverseStack(Stack<Integer> stack) {
        if (!stack.isEmpty()){
            int n=stack.pop();
            System.out.println(stack);
            reverseStack(stack);
            System.out.println(n);
            stack.push(n);
        }
    }

我们可以清楚地看到输出堆栈与输入堆栈相同，但仍然以相反的顺序打印元素。我哪里做错了？

Answer 1

您必须构建一个新 堆栈，以便第一个从旧堆栈弹出的是第一个被插入新堆栈的堆栈。不会有“额外空间”，因为每个原始项目都将位于 2 个堆栈之一中。我会使用了解您正在构建的堆栈的辅助函数来完成此操作。