面试题 03.05. 栈排序 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class SortedStack {

    private final Stack<Integer> stack;
    private final Stack<Integer> tmpStack;

    public SortedStack() {
        this.stack = new Stack<>();
        this.tmpStack = new Stack<>();
    }

    public void push(int val) {
        // push 5
        // stack:
        // 1
        // 2
        // 7
        while (!stack.isEmpty() && stack.peek() < val) {
            tmpStack.push(stack.pop());
        }
        stack.push(val);
        while (!tmpStack.isEmpty()) {
            stack.push(tmpStack.pop());
        }
    }

    public void pop() {
        if (stack.isEmpty()) {
            return;
        }
        
        stack.pop();
    }

    public int peek() {
        if (stack.isEmpty()) {
            return -1;
        }
        
        return stack.peek();
    }

    public boolean isEmpty() {
        return stack.isEmpty() && tmpStack.isEmpty();
    }

}

思路：使 stack 保持有序即可，使用 tmpStack 来做临时中转。

References

面试题 03.05. 栈排序