A queue serves in arrival order. A monotonic stack keeps its items sorted so answers pop out as soon as they are known.
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”.
9, 7, 5, 3. Nothing pops. What is the answer for every item?1, 2, 3, 4. How big does the stack get?d d). The page tells you what a real program must guard against.<= instead of < changes the meaning when numbers are equal (next greater vs next greater or equal).-1.queue[0] panics in Go. Always check len(queue) > 0.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).