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

1. push(x) -- Push element x onto stack.
2. pop() -- Remove the element on top of the stack and return it.
3. top() -- Get the element on the top.
4. peekMax() -- Retrieve the maximum element in the stack.
5. 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.

Stack

class MaxStack {
    private Stack<Integer> num;
    private Stack<Integer> max;

    /** initialize your data structure here. */
    public MaxStack() {
        this.num = new Stack<Integer>();
        this.max = new Stack<Integer>();
    }

    public void push(int x) {
        int max = this.max.size() > 0 ? this.max.peek() : x;
        this.num.push(x);
        this.max.push(Math.max(x, max));
    }

    public int pop() {
        int res = this.num.pop();
        this.max.pop();
        return res;
    }

    public int top() {
        return this.num.peek();
    }

    public int peekMax() {
        return this.max.peek();
    }

    public int popMax() {
        int max = this.max.peek();
        Stack<Integer> s1 = new Stack<>();

        while(this.num.peek() != max) {
            s1.push(this.num.pop());
            this.max.pop();
        }
        this.num.pop();
        this.max.pop();

        while(s1.size() > 0) {
            this.push(s1.pop());
        }

        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();
 */

Double linked list + treemap

class MaxStack {
    class Node {
        public int val;
        public Node prev;
        public Node next;

        public Node(int v) {
            this.val = v;
            this.prev = null;
            this.next = null;
        }
    }

    private Node head;
    private Node tail;

    private TreeMap<Integer, List<Node>> map;

    /** initialize your data structure here. */
    public MaxStack() {
        this.head = new Node(0);
        this.tail = new Node(0);
        this.head.next = this.tail;
        this.tail.prev = this.head;

        this.map = new TreeMap<Integer, List<Node>>();
    }

    public void push(int x) {
        Node node = new Node(x);
        node.next = this.tail;
        node.prev = this.tail.prev;
        this.tail.prev.next = node;
        this.tail.prev = node;

        if(!this.map.containsKey(x)) 
            this.map.put(x, new ArrayList<Node>());
        this.map.get(x).add(node);
    }

    public int pop() {
        Node temp = this.tail.prev;
        temp.prev.next = this.tail;
        this.tail.prev = temp.prev;

        temp.next = null;
        temp.prev = null;

        List<Node> list = map.get(temp.val);
        list.remove(list.size() - 1);
        if(list.size() == 0)
            map.remove(temp.val);

        return temp.val;
    }

    public int top() {
        return this.tail.prev.val;
    }

    public int peekMax() {
        return this.map.lastKey();
    }

    public int popMax() {
        List<Node> list = map.get(map.lastKey());
        Node n = list.remove(list.size() - 1);
        if(list.size() == 0)
            map.remove(n.val);

        n.prev.next = n.next;
        n.next.prev = n.prev;
        n.next = null;
        n.prev = null;

        return n.val;
    }
}

/**
 * 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();
 */