Reversing stack in O(n) without extraspace is not happening

Question

I'm trying to reverse a stack using recursion :

I'm able to print the elements of the stack in reverse order. But if I try to push the reverse elements it is not working.

Let the stack be [0,1,2,3,4]. 4 is top.

This is what I've tried:

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

With this I'm getting the correct output.

Output is :

0
1
2
3
4

This is what I've expected.

If I try to push these elements back to stack I'm getting the same stack back without getting reversed :

This is the code used for reversing :

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

This is the step wise stack obtained from this code :

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);
        }
    }

We can clearly see that the output stack is same as input stack but still elements are printed in reverse order. Where am I doing wrong ?

Answer 1

You have to build a new stack, so that the first one popped from the old stack is the first one pushed onto the new one. There won't be "extra space", as every original item will be in one of the 2 stacks. I'd do it using a helper function that knows about the stack you are building.