Moving elements from one stack to another

Tweet

Suppose we have stack and want to move elements to another stack preserving element order, If we don't have any restrictions than it's very simple task, using temporary space we can achieve it with no extra effort.
Now let's solve this problem with restrictions, we are allowed to use only additional O(1) memory.  When I first stated this problem I thought that it was not solvable, but after few minutes of thinking I figured out simple algorithm.

Imagine that we already moved N-1 elements to new stack, they are ordered correctly and now we are going to move Nth element. We can do it in this way:

1. Pop Nth element from initial stack and save it in temporary variable
2. Move N-1 elements from destination stack to initial stack one by one.
3. Push the element saved in 1st step in destination stack.
4. Move N-1 elements from initial stack to destination stack -  those are elements which were moved in 2nd step.

And we got it, we have moved N elements in destination stack. Now we can use this approach to move all the elements and we'll be happy.

Here is the implementation of this algorithm:

    static public void main(String[] args) {
        Stack stack = new Stack();
        for (int i = 0; i < 31; i++) {
            stack.add(i);
        }
        Stack stack2 = new Stack();

        while (!stack.isEmpty()) {
            int temp = stack.pop();
            int counter = 0;
            while (!stack2.isEmpty()) {
                stack.push(stack2.pop());
                counter++;
            }
            stack2.push(temp);

            while (counter < 0) {
                stack2.push(stack.pop());
                counter--;
            }
        }


        while (!stack2.isEmpty()) {
            System.out.print(stack2.pop() + " ");
        }


    }

The algorithm which I proposed is useful only in situations when there is strict memory restrictions,  because time complexity has grown and it is O(N^2).