Minimum Stack and Queue

Stacks and queues that also report their minimum in $O(1)$.

Minimum stack — $O(1)$ everything

Store, alongside each element, the minimum of the stack up to and including it.

struct MinStack {
    stack<pair<long long,long long>> st;               // {value, min so far}
 
    void push(long long x) {
        long long m = st.empty() ? x : min(x, st.top().second);
        st.push({x, m});
    }
    void pop()      { st.pop(); }
    long long top() { return st.top().first; }
    long long getMin() { return st.top().second; }
    bool empty()    { return st.empty(); }
};

$O(1)$ per operation, $O(n)$ memory. The one-line insight is that a stack’s minimum only ever depends on a prefix of the stack, so it can be stored per element.

Minimum queue — two stacks

A queue is simulated by two stacks: in receives pushes, out serves pops. When out is empty, everything from in is moved across (reversing the order). Since each stack knows its own minimum, the queue’s minimum is the smaller of the two.

struct MinQueue {
    MinStack in, out;
 
    void push(long long x) { in.push(x); }
 
    void move() {
        if (out.empty())
            while (!in.empty()) { out.push(in.top()); in.pop(); }
    }
    void pop()  { move(); out.pop(); }
    long long front() { move(); return out.top(); }
 
    long long getMin() {
        if (in.empty())  return out.getMin();
        if (out.empty()) return in.getMin();
        return min(in.getMin(), out.getMin());
    }
};

Each element is moved from in to out exactly once, so all operations are $O(1)$ amortized.

Minimum queue — the deque alternative

For a sliding window specifically, a monotonic deque is simpler and has a better constant:

deque<long long> dq;
void push(long long x) { while (!dq.empty() && dq.back() >= x) dq.pop_back(); dq.push_back(x); }
void pop(long long x)  { if (!dq.empty() && dq.front() == x) dq.pop_front(); }
long long getMin()     { return dq.front(); }

But note the difference: the deque version needs to know which value is being removed, so it only works when you pop in FIFO order and can identify the element. The two-stack version works for any push/pop sequence.

Which to use

Situation	Structure
Sliding window over an array	monotonic deque
Arbitrary push/pop, need the minimum	two-stack minimum queue
LIFO only	minimum stack
Need arbitrary deletion	multiset, $O(\log n)$
Need the $k$-th smallest	ordered set

Where the general version is needed

The two-stack minimum queue is exactly what makes some otherwise-impossible techniques work:

• Mo’s algorithm with a non-invertible aggregate. Mo’s needs both add and remove; when removal is impossible (as it is for min), the “Mo’s with rollback” variant uses a stack-based structure with undo instead.
• Queue-like DP transitions where the window’s left end advances irregularly.
• Simulating a deque with two stacks — the same trick, extended, gives a min-deque with $O(1)$ amortized operations.

The general principle

Any aggregate that a stack can maintain in $O(1)$ (by storing a running value per element) can be maintained by a queue at $O(1)$ amortized, via the two-stack simulation. That covers min, max, gcd, sum, and, or, and any associative operation — the queue never needs to undo anything, which is precisely why it works where a naive approach fails.

See also: Monotonic Queue · Stacks and Queues · Mo’s Algorithm