readyforhires
Sign up free

Stack & Queue 101

Fundamental · 4 chapters · 7 min read · Use last-in-first-out to match brackets, undo steps and find the next greater value.

Practise this in the app All guides

Stacks, queues and when to use them

Two ways to line things up

A stack is last-in, first-out (LIFO): like a pile of plates, you add and remove from the top. A queue is first-in, first-out (FIFO): like the line at a railway ticket counter, people leave in the order they arrived. In Python a plain list is a good stack (append and pop are O(1)), and collections.deque is the right queue (append and popleft are O(1)). Never use list.pop(0) as a queue in an interview; it is O(n).

Signals for a stack

Signals for a queue

Mental model

A stack holds the things that are still "open" or "waiting for an answer". When a new element arrives, it may close or answer some of them, always the most recent first. If you can describe what is waiting on your stack in one phrase ("indices of days that have not yet seen a warmer day"), you are using it correctly.

Core patterns with templates

1. Cancel the previous item

def remove_adjacent_duplicates(s):
    st = []
    for ch in s:
        if st and st[-1] == ch:
            st.pop()
        else:
            st.append(ch)
    return "".join(st)

The same shape handles backspace (# pops, anything else pushes).

2. Evaluate Reverse Polish Notation

def eval_rpn(tokens):
    st = []
    for t in tokens:
        if t in "+-*/":
            b, a = st.pop(), st.pop()
            if t == "+":
                st.append(a + b)
            elif t == "-":
                st.append(a - b)
            elif t == "*":
                st.append(a * b)
            else:
                st.append(int(a / b))
        else:
            st.append(int(t))
    return st[0]

Pop b first: the right operand is on top. int(a / b) truncates towards zero, unlike //.

3. Monotonic stack for "next warmer day"

def daily_temperatures(t):
    ans = [0] * len(t)
    st = []
    for i, x in enumerate(t):
        while st and t[st[-1]] < x:
            j = st.pop()
            ans[j] = i - j
        st.append(i)
    return ans

The stack holds indices whose temperatures are decreasing from bottom to top. Example: [73, 74, 75, 71, 69, 72, 76] gives [1, 1, 4, 2, 1, 1, 0].

4. Nested decoding with two stacks

def decode(s):
    st, cur, num = [], "", 0
    for ch in s:
        if ch.isdigit():
            num = num * 10 + int(ch)
        elif ch == "[":
            st.append((cur, num))
            cur, num = "", 0
        elif ch == "]":
            prev, k = st.pop()
            cur = prev + cur * k
        else:
            cur += ch
    return cur

5. Queue for BFS

from collections import deque
q = deque([start])
while q:
    node = q.popleft()
    # visit node, append unvisited neighbours

Complexity, mistakes and edge cases

Complexity

OperationStack (list)Queue (deque)
push / appendO(1)O(1)
pop top / popleftO(1)O(1)
peekst[-1] O(1)q[0] O(1)

A monotonic stack is O(n) overall even with a nested while: each index is pushed once and popped at most once.

Common mistakes

Edge cases

Empty input, a single element, strictly increasing or strictly decreasing sequences (which stress the monotonic stack in opposite ways), all equal values, unbalanced brackets, and nested structures several levels deep.

The histogram trick

For "largest rectangle in a histogram", keep a stack of bar indices with increasing heights. When a shorter bar arrives, pop taller bars; each popped bar's rectangle extends from just after the new stack top to just before the current index. Appending a sentinel bar of height 0 at the end flushes the stack so you do not need special code afterwards.

Variations and practise

How interviewers twist it

How to explain it

Name what the stack holds and its order: "indices of bars with increasing heights" or "characters not yet cancelled". Then say when you pop: "when the current value breaks the order". That gives the interviewer confidence before you write a single line.

Practise

The problems below move from simple cancelling (backspace and adjacent duplicates) to expression evaluation, nested decoding, the monotonic stack, and finally the histogram rectangle. Solve the monotonic-stack problems twice: once by brute force to see the pattern, then with the stack.

Practise

Easy

Medium

Hard

Practise this in the app All guides