Max Stack

1. peekMax();
2. popMax();

Solution 1: Using two stacks to maintain the max value

• https://github.com/garudareiga/algo-java/blob/master/src/main/java/stackQueue/MaxStack.java

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

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

    public void pop() {
        int x = stack.pop();
        if (maxStack.peek() == x)
            maxStack.pop();
    }

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

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

    public int popMax() {
        if (stack.isEmpty())
            throw new EmptyStackException();
        int r = maxStack.pop();
        Iterator<Integer> iter = stack.iterator();
        while (iter.hasNext()) {
            int v = iter.next();
            if (v == r) { iter.remove(); break; }
        }
        return r;
    }
}