LintCode

Stack Sorting

Michael

Aug 21, 2016 • 1 min read

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

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 class Solution {
    /**
     * @param stack an integer stack
     * @return void
     */
    public void stackSorting(Stack<Integer> stack) {
        if (stack == null || stack.isEmpty()) {
            return;
        }
        
        Stack<Integer> tempStack = new Stack<Integer>();
        
        while (!stack.isEmpty()) {
            int element = stack.pop();
            
            while (!tempStack.isEmpty() && tempStack.peek() < element) {
                stack.push(tempStack.pop());
            }
            
            tempStack.push(element);
        }
        
        while (!tempStack.isEmpty()) {
            stack.push(tempStack.pop());
        }
    }
}

Hope this helps,
Michael