Lesson

Stack, Queue, and Monotonic Stack

Intuition: plates and a coffee shop line

Picture a stack of plates. You put a clean plate on top, and you take one from the top too. The last plate you put down is the first one to go. That's a stack, and it works on the LIFO principle (Last In, First Out).

Now picture the line at a coffee shop. Whoever arrives first gets served first. That's a queue, and it works on the FIFO principle (First In, First Out).

Structure	Principle	Add	Remove	Where you see it
Stack	LIFO	to the top	from the top	"Undo" in an editor, function calls, brackets
Queue	FIFO	to the back	from the front	breadth-first search (BFS), task queues

Both operations cost O(1). That's all you need: the power of these structures lies precisely in their limits.

What it looks like in code

A stack is almost always built on a dynamic array. A queue needs a structure you can cheaply remove from at the front.

from collections import deque

stack = []
stack.append(1); stack.append(2)   # push onto the top
top = stack[-1]                     # peek at the top: 2
stack.pop()                         # pop the top

q = deque()
q.append(1); q.append(2)            # to the back
first = q.popleft()                 # from the front: 1 (O(1), unlike list.pop(0))

Trap: in Python, list.pop(0), and in JS, array.shift(), run in O(n) because they shift the whole array. For a queue, use deque or keep a head index.

A classic: brackets

The string "([{}])" is valid, but "([)]" isn't. Why do we need a stack here? A closing bracket must always match the most recent opening bracket that hasn't been closed yet. "Most recent" is exactly what LIFO means.

Here's the idea:

push every opening bracket onto the stack;
on a closing bracket, check that the stack isn't empty and that its partner is on top, then pop it;
at the end, the stack must be empty.

This is the first practice problem. Try writing it yourself from these three bullet points; you've got this.

Monotonic stack: "next greater element"

The problem: for each number, find the first number to its right that's greater than it, or -1 if there isn't one.

Answer: [5, 5, 6, 6, -1, -1]

The naive solution scans to the right from every element, which is O(n²). We can do better.

Intuition. Picture people in a line, each one waiting for "someone taller than me." Until that person shows up, they stand in the stack. A newcomer arrives and looks at the top of the stack: if the newcomer is taller, they're the answer for whoever is waiting there. We pop that person, check the next one, and so on. Then the newcomer takes their own place in line to wait.

The stack holds indices, and their values go in decreasing order from bottom to top. That's where the name "monotonic" comes from.

Here's the state before we process 5 (index 2): 2 and 1 are waiting in the stack.

i ↓ 52

Stack: [0, 1] (values 2, 1). 5 arrives: pop 1 → answer 5, pop 2 → answer 5

Next, 3 isn't greater than 5, so it simply joins the stack. Then 6 arrives:

i ↓ 64

Stack: [2, 3] (values 5, 3). 6 arrives: pop 3 and 5, both get answer 6

At the end, 6 and 4 are left in the stack. There's nobody to their right, so they get -1.

Template

def next_greater(nums):
    res = [-1] * len(nums)
    st = []                              # indices, values decreasing
    for i, x in enumerate(nums):
        while st and nums[st[-1]] < x:   # x is greater than the waiting one → it's the answer
            res[st.pop()] = x
        st.append(i)                     # now x waits itself
    return res

Why it's O(n) even with a while inside

The nested loop looks scary, but let's count differently: each index is pushed onto the stack exactly once and popped at most once. So over the whole pass there are at most n pushes and n pops. That's O(n) time, and in the worst case the stack takes O(n) space. This way of counting is called amortized analysis.

What it sounds like in an interview

"Naively this is O(n²). Notice that the elements still waiting for an answer form a decreasing sequence. I keep their indices in a monotonic stack. Each new element pops everything smaller than itself off the top and becomes their answer. Every index enters and leaves the stack at most once, so it's O(n) time and O(n) space."

Common mistakes

Storing values instead of indices. Then you have nowhere to write the answer, and in "how many days until" problems you have nothing to subtract.
< vs <=. Think about whether an equal element counts as "greater." The sign in the condition decides exactly that.
Reading the top of an empty stack. Always check st for emptiness first.
Forgetting the leftovers. Elements still in the stack after the loop get the default value (-1).
A queue built on pop(0) / shift(). Your solution quietly turns into O(n²).

You've now got three tools: the stack, the queue, and the monotonic stack. In the practice, we'll start with brackets.