Max Stack

hard stack design

Problem

Standard stack plus peekMax() and popMax() (returns and removes the maximum).

Inputpush 5; push 1; push 5; peekMax; popMax; top

Output5 5 1

popMax removes a 5; top shows the remaining one.

input

class MaxStack:
    def __init__(self): self.s = []; self.m = []
    def push(self, x): self.s.append(x); self.m.append(max(x, self.m[-1]) if self.m else x)
    def pop(self): self.m.pop(); return self.s.pop()
    def top(self): return self.s[-1]
    def peekMax(self): return self.m[-1]
    def popMax(self):
        mx = self.peekMax(); buf = []
        while self.top() != mx: buf.append(self.pop())
        self.pop()
        while buf: self.push(buf.pop())
        return mx

class MaxStack {
  constructor() { this.s = []; this.m = []; }
  push(x) { this.s.push(x); this.m.push(this.m.length ? Math.max(x, this.m[this.m.length-1]) : x); }
  pop() { this.m.pop(); return this.s.pop(); }
  top() { return this.s[this.s.length-1]; }
  peekMax() { return this.m[this.m.length-1]; }
  popMax() {
    const mx = this.peekMax(); const buf = [];
    while (this.top() !== mx) buf.push(this.pop());
    this.pop();
    while (buf.length) this.push(buf.pop());
    return mx;
  }
}

class MaxStack {
    Deque s = new ArrayDeque<>(), m = new ArrayDeque<>();
    public void push(int x) { s.push(x); m.push(m.isEmpty() ? x : Math.max(x, m.peek())); }
    public int pop() { m.pop(); return s.pop(); }
    public int top() { return s.peek(); }
    public int peekMax() { return m.peek(); }
    public int popMax() {
        int mx = peekMax(); Deque buf = new ArrayDeque<>();
        while (top() != mx) buf.push(pop());
        pop();
        while (!buf.isEmpty()) push(buf.pop());
        return mx;
    }
}

class MaxStack {
    stack s, m;
public:
    void push(int x) { s.push(x); m.push(m.empty() ? x : max(x, m.top())); }
    int pop() { int t = s.top(); s.pop(); m.pop(); return t; }
    int top() { return s.top(); }
    int peekMax() { return m.top(); }
    int popMax() {
        int mx = peekMax(); stack buf;
        while (top() != mx) buf.push(pop());
        pop();
        while (!buf.empty()) { push(buf.top()); buf.pop(); }
        return mx;
    }
};

Explanation

This design keeps two stacks that grow and shrink together: s holds the actual values, and m holds the running maximum at each level. Every time you push a value, you also push the bigger of that value and the current max onto m.

Because m mirrors s, the top of m is always the maximum of everything currently in the stack. That makes peekMax and ordinary pop/top instant — you just read or pop the tops of both stacks.

The tricky operation is popMax, which must remove the maximum even if it is buried. We first read the max mx, then pop values into a temporary buffer buf until the top equals mx. We pop that max, then push everything from buf back so the rest of the stack keeps its order.

Example: push 5, 1, 5. Now s=[5,1,5] and m=[5,5,5]. peekMax reads 5. popMax sees the top is already 5, removes it, and returns 5, leaving top()=1.

It works because the parallel max-stack always knows the current maximum, and the buffer trick lets us reach a deeper max while preserving the relative order of the other elements.

Time: O(n) popMax, O(1) others Space: O(n)