[Java] Reverse stack without using additional data structures

Given a stack, reverse it without using additional data structures. Example:

S     becomes    S      

1                4

2                3

3                2

4                1

Without additional structures, the only available space for us is the call stack, therefore we must use recursion.
 

To reverse a stack we need to pop all elements out and then add them back in order. However in a single pass this cannot happen, as we have access to only one element on the top and can store only one additional element in a variable.
 

We can however process the stack multiple times for each element in two phases:

(1) store top element from the given stack

(1.1) continue same logic until stack is empty

(2) push the top element at the bottom of the stack
 

phase (2) uses a similar logic, given an element X:

(2.1) store the current top element in the stack

(2.2) push X at the bottom of the stack

(2.3) add back the stored top at point (2.1)

The overall process is therefore:

1. store top element from the given stack - X
2. goto 1 until stack is empty
3. store the current top element in the stack - Y
4. push X at the bottom of the reduced stack
5. add Y back to the stack

The runtime of this code is O(N^2) since for each element in the stack we traverse the whole stack again in phase (2), while space is O(N) since at any point in time we won't have more than N calls on the stack .

You can check my implementation of reverseStack on my Gist along with some tests in ReverseStackJTests.