Stack Sorting

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).

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.

Challenge

O(n²) time is acceptable.

思路：
先把所有元素从原堆栈倒进辅助堆栈里。然后从辅助栈里每拿出一个元素和原堆栈的每一个元素比。只要原堆栈里最上面的元素的值大于它，就把原堆栈里这个大的元素放回辅助栈。然后接着再看原堆栈最上面的元素，直到所有大于它的元素都被放回辅助栈。这样每轮比完以后，原堆栈里剩下排好序的元素，并且都比辅助栈里拿出来的这个小。辅助栈里所有的元素都比这个元素大。我们把这个元素放进原堆栈，原堆栈仍然有序。

public class Solution {
    /**
     * @param stack an integer stack
     * @return void
     */
    public void stackSorting(Stack<Integer> stack) {
        // Write your code here
        Stack<Integer> temp = new Stack<Integer>();
        
        while (!stack.isEmpty()) {
            temp.push(stack.pop());
        }
        
        while (!temp.isEmpty() ) {
            int item = temp.pop();
            while (!stack.isEmpty() && item < stack.peek()) {
                temp.push(stack.pop());
            }
            stack.push(item);
        }
    }
}