Stack Sorting

Sort a stack in ascending order (with biggest terms on top).

You may use at most one additional stack to hold items, but you may not copy the elements into any other data structure (e.g. array).

Have you met this question in a real interview?

Yes

Example

Given stack =

| |
|3|
|1|
|2|
|4|
 -

return:

| |
|4|
|3|
|2|
|1|
 -

The data will be serialized to[4,2,1,3]. The last element is the element on the top of the stack.

public void stackSorting(Stack<Integer> stack) {
    Stack<Integer> backup = new Stack<Integer>();
    while(!stack.isEmpty()) {
        int tmp = stack.pop();
        while(!backup.isEmpty() && tmp > backup.peek()) {
            stack.push(backup.pop());
        }
        backup.push(tmp);
    }
    while(!backup.isEmpty()) {
        stack.push(backup.pop());
    }
}