Queue & Monotonic Stack

A queue serves in arrival order. A monotonic stack keeps its items sorted so answers pop out as soon as they are known.

The idea

Queue: like a line at a shop. The first person to join is the first to be served (FIFO). You add at the back (enqueue) and remove from the front (dequeue).

Monotonic stack: for each number, find the next number to its right that is bigger. Instead of scanning right for each one, keep a stack of numbers still waiting for their bigger neighbour. When a new number arrives, every waiting number that is smaller than it has just found its answer: pop them and record it. Then the new number joins the waiting list. The waiting numbers stay in decreasing order, which is why it is called “monotonic”.

Watch it work

Try it

Common mistakes

How fast is it?

Monotonic stack: O(n) time – every index is pushed once and popped at most once, even though there is a loop inside a loop. Space: O(n). The naive version (scan right for each item) is O(n²). Queue operations are O(1) each (with a slice, queue[1:] is O(1) but keeps the memory until it is garbage collected).