Max Stack 最大栈

Design a max stack that supports push, pop, top, peekMax and popMax.

push(x) -- Push element x onto stack.
pop() -- Remove the element on top of the stack and return it.
top() -- Get the element on the top.
peekMax() -- Retrieve the maximum element in the stack.
popMax() -- Retrieve the maximum element in the stack, and remove it. If you find more than one maximum elements, only remove the top-most one.

Example 1:
MaxStack stack = new MaxStack();
stack.push(5);
stack.push(1);
stack.push(5);
stack.top(); -> 5
stack.popMax(); -> 5
stack.top(); -> 1
stack.peekMax(); -> 5
stack.pop(); -> 1
stack.top(); -> 5

Note:
-1e7 <= x <= 1e7
Number of operations won't exceed 10000.
The last four operations won't be called when stack is empty.

题目要求实现一个最大栈，能够压入元素，返回弹出的元素，获得栈顶元素，得到栈中最大的火元素，返回弹出栈中的最大元素。和剑指offer上的一道min栈有点类似，同样通过2个栈来实现，只是popMax()的时候可能还需要一个额外的栈来实现。

public class MaxStack {
    Stack<Integer> stack = new Stack<>();
    Stack<Integer> maxStack = new Stack<>();

    public void push(int num) {
        stack.push(num);
        if (maxStack.isEmpty()) {
            maxStack.push(num);
        } else {
            if (maxStack.peek() >= num) {
                maxStack.push(maxStack.peek());
            }
        }
    }

    public int pop() {
        maxStack.pop();
        return stack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int peekMax() {
        return maxStack.peek();
    }

    public int popMax() {
        // 使用一个辅助栈保存stack中弹出的元素
        Stack<Integer> tmp = new Stack<>();
        // 因为maxStack中保存的一直是栈中最大的元素，因此需要在stack中找到第一个和该值相等的元素
        int top = maxStack.peek();
        while (stack.peek() != top) {
            tmp.push(stack.pop());
        }
        // 找到了，那么就弹出该元素，同时不要忘记应该把maxStack的元素也弹出
        stack.pop();
        maxStack.pop();
        // 最后再把临时栈中保存的内容压回到stack中
        while (!tmp.isEmpty()) {
            stack.push(tmp.pop());
        }
        return top;
    }
}