Max Stack

Design a stack that supports push, pop, top, peekMax (retrieve max element), and popMax (pop the max element). Implement each operation.

Example 1

push(5), push(1), push(5) → top()=5, popMax()=5, top()=1, peekMax()=5, pop()=1, top()=5

Solution Approach

Use two stacks: one main stack and one maxStack tracking the current max at each level. For popMax, use a temp stack to pop elements until the max is found, then restore.

Main stack: stores all elements.
maxStack: at each push, push max(element, maxStack.top()).
For pop: pop from both stacks.
For popMax: use a temp stack to pop elements until main.top()==max, pop both, then push temp elements back.

Java

import java.util.*;

class MaxStack {
    Deque<Integer> stack = new ArrayDeque<>();
    Deque<Integer> maxStack = new ArrayDeque<>();

    public void push(int x) {
        stack.push(x);
        maxStack.push(maxStack.isEmpty() ? x : Math.max(x, 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() {
        int max = peekMax();
        Deque<Integer> temp = new ArrayDeque<>();
        while (top() != max) temp.push(pop());
        pop();
        while (!temp.isEmpty()) push(temp.pop());
        return max;
    }
}

Time Complexity: O(N) for popMax, O(1) for others
Space Complexity: O(N)