Stack & Queue — Valid Parentheses, Monotonic Stack and More

A stack is like a pile of plates: you add to the top and remove from the top — Last In, First Out (LIFO). A queue is like a ticket line: join at the back, leave from the front — First In, First Out (FIFO). Both do their main operations in O(1).

	Stack	Queue
Python	list (append, pop)	collections.deque (append, popleft)
Java	ArrayDeque (push, pop, peek)	ArrayDeque (offer, poll, peek)

In Java, prefer ArrayDeque over the old Stack class. In Python, never use list.pop(0) as a queue — it's O(n). Use deque.

Pattern 1 — Matching pairs (Valid Parentheses)

Every closing bracket must match the most recent unmatched opening bracket. "Most recent" = top of a stack.

def is_valid(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in pairs:                              # closing bracket
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()
        else:
            stack.append(ch)                         # opening bracket
    return not stack                                 # nothing left unmatched

boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char ch : s.toCharArray()) {
        if (ch == '(') stack.push(')');
        else if (ch == '[') stack.push(']');
        else if (ch == '{') stack.push('}');
        else if (stack.isEmpty() || stack.pop() != ch) return false;
    }
    return stack.isEmpty();
}

The Java version pushes the expected closing bracket — a neat trick that removes the lookup map.

Pattern 2 — Evaluate expressions (Reverse Polish Notation)

In ["2", "1", "+", "3", "*"], numbers go on the stack; an operator pops two numbers, applies itself and pushes the result: (2 + 1) * 3 = 9.

def eval_rpn(tokens):
    stack = []
    for t in tokens:
        if t in "+-*/":
            b, a = stack.pop(), stack.pop()        # note the order!
            if t == '+': stack.append(a + b)
            elif t == '-': stack.append(a - b)
            elif t == '*': stack.append(a * b)
            else: stack.append(int(a / b))         # truncate toward zero
        else:
            stack.append(int(t))
    return stack[0]

Pattern 3 — Min Stack (extra info per level)

Design a stack that returns the minimum in O(1). Store, alongside each value, the minimum so far:

class MinStack:
    def __init__(self):
        self.stack = []                 # (value, min at this level)
    def push(self, x):
        cur_min = min(x, self.stack[-1][1]) if self.stack else x
        self.stack.append((x, cur_min))
    def pop(self):
        self.stack.pop()
    def top(self):
        return self.stack[-1][0]
    def getMin(self):
        return self.stack[-1][1]

Pattern 4 — The monotonic stack (next greater element)

Daily Temperatures: for each day, how many days until a warmer one?

Brute force checks every later day — O(n²). A monotonic stack keeps indices whose answer we don't know yet, with temperatures decreasing from bottom to top. When a warmer day arrives, it is the answer for every colder day on top of the stack.

def daily_temperatures(temps):
    answer = [0] * len(temps)
    stack = []                                   # indices with no warmer day yet
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:    # today is warmer → resolve them
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)
    return answer

Dry run — [73, 74, 75, 71, 69, 72]:

i	temp	stack (indices) before	resolved
0	73	[]	—
1	74	[0]	0 → 1 day
2	75	[1]	1 → 1 day
3	71	[2]	—
4	69	[2, 3]	—
5	72	[2, 3, 4]	4 → 1, 3 → 2

Each index is pushed and popped at most once → O(n) overall. The same pattern solves Next Greater Element, Stock Span, and (with more work) Largest Rectangle in Histogram.

Which direction? Need the next greater → keep the stack decreasing. Need the next smaller → keep it increasing.

Queues and BFS

Queues shine when you must process things in the order they arrived — most importantly breadth-first search in trees and graphs (coming in later lessons). Implement Queue using Stacks is a classic design question: use one stack for input and one for output; move items to the output stack only when it's empty (amortised O(1)).

How to recognise a stack problem

• Brackets, nested structures, "undo", "backtrack to the most recent".
• Expressions and calculators.
• "Next greater / smaller element", "how many days until", spans and histograms → monotonic stack.

Common mistakes

1. Popping from an empty stack — always check if stack / !stack.isEmpty().
2. Wrong operand order for - and / in RPN (the first pop is the right operand).
3. Storing values in the monotonic stack when you need indices (for distances).
4. Using list.pop(0) as a queue in Python (O(n)).

Key takeaways

• Stack = LIFO, queue = FIFO, both O(1) for push/pop.
• "Most recent unmatched" → stack. "Next greater/smaller" → monotonic stack, O(n).
• Queues power BFS — you'll use them in trees and graphs.