716. Max Stack

class MaxStack {
    
    private Deque<Integer> stack;
    private Deque<Integer> maxStack;

    /** initialize your data structure here. */
    public MaxStack() {
        stack = new ArrayDeque<>();
        maxStack = new ArrayDeque<>();
    }

    public void push(int x) {
        stack.offerFirst(x);
        if (!maxStack.isEmpty() && x > maxStack.peekFirst()) {
            maxStack.offerFirst(x);
        } else {
            if (!maxStack.isEmpty()) {
                maxStack.offerFirst(maxStack.peekFirst());
            } else {
                maxStack.offerFirst(x); 
            }
        }
    }

    public int pop() {
        int x = stack.pollFirst();
        maxStack.pollFirst();
        return x;
    }
    
    public int top() {
        return stack.peekFirst();
    }
    
    public int peekMax() {
        return maxStack.peekFirst();
    }

    public int popMax() {
        int max = maxStack.peekFirst();
        Deque<Integer> temp = new ArrayDeque<>();
        while (!stack.isEmpty() && stack.peekFirst() < max) {
            temp.offerFirst(stack.pollFirst());
            maxStack.pollFirst();
        }
        stack.pollFirst();
        maxStack.pollFirst();
        while (!temp.isEmpty()) {
            push(temp.pollFirst());
        }
        return max;
    }
}

/**
 * Your MaxStack object will be instantiated and called as such:
 * MaxStack obj = new MaxStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.peekMax();
 * int param_5 = obj.popMax();
 */