Stack & Queue

LIFO and FIFO — and the monotonic-stack trick that beats every "next greater element" question.

intermediatePractice Full theoryPrereq:Arrays & Hashing

Start practice Read the theory See all problems

What you'll learn

Choose stack (LIFO) vs queue (FIFO) from the problem's access pattern
Use a stack for bracket matching and expression evaluation
Build a monotonic stack to answer next-greater / next-smaller in O(n)
Use a queue for BFS level-order traversal
Implement a deque for sliding-window-maximum
State why monotonic-stack problems are O(n) despite the inner pop loop

When to reach for this

Signals (use it)

Matching/nesting: brackets, tags, nested structures → stack
"Next greater / next smaller / previous greater element" → monotonic stack
"Most recent", undo, backtrack to last state → stack
Level-by-level processing, shortest path in unweighted graph → queue (BFS)
Sliding window maximum/minimum → monotonic deque

Anti-signals (don't)

Random access by index needed → use an array
Need min/max at any time with arbitrary inserts → heap
Order doesn't matter → set/map

Theory & deep dive

Stacks and queues are the two simplest 'ordered access' structures, and the order they enforce is the whole point. A stack is LIFO — last in, first out — perfect for anything with nesting or 'most recent' semantics (matching brackets, undo, call stacks, DFS). A queue is FIFO — first in, first out — perfect for processing things in arrival order (BFS, scheduling, streaming).

The interview multiplier is the monotonic stack: a stack you keep sorted (increasing or decreasing) by popping elements that violate the order before pushing. It answers a whole class of 'next greater / next smaller / previous greater' questions in O(n) that look O(n²) at first glance — daily temperatures, largest rectangle in histogram, stock span.

This module covers both structures, the bracket-matching template, the monotonic-stack template, and BFS level-order with a queue.

The big idea in plain words

A stack is a pile of plates: you add to the top and take from the top, so the last plate you put down is the first one you pick up. A queue is a line at a ticket counter: the first person in line is served first. The order each one forces is exactly what makes it handy.

Example (stack): checking brackets in ([]). Push (, then push [. Now a ] arrives - it should close the most recently opened bracket, which is [, and it does, so pop it. Then ) should close (, and it does. The stack ends empty, so the string is valid. The 'most recent must close first' rule is pure last-in-first-out.

Stack vs queue — the core contract

Structure	Order	Add	Remove	Look	Java	Python
Stack	LIFO	push	pop (top)	peek	`Deque` (`ArrayDeque`)	`list` (append/pop)
Queue	FIFO	enqueue	dequeue (front)	peek	`ArrayDeque` / `LinkedList`	`collections.deque`
Deque	both ends	addFirst/Last	pollFirst/Last	peek	`ArrayDeque`	`collections.deque`

All operations are O(1). In Java, prefer ArrayDeque over the legacy Stack class (which is synchronised and slower). In Python, never use list.pop(0) for a queue — it's O(n); use collections.deque for O(1) pops from the front.

Watch out

Python list.pop(0) (front removal) is O(n) because it shifts every element. Always use collections.deque with popleft() for an O(1) queue.

Which structure? (decision flow)

Bracket matching with a stack

The canonical stack problem. Push every opening bracket; on a closing bracket, the top of the stack must be its matching opener — if not (or the stack is empty), it's invalid. A valid string ends with an empty stack. This LIFO behaviour mirrors how nesting works: the most recently opened bracket must close first.

Python· Valid parentheses

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

The monotonic stack

A monotonic stack keeps its elements in sorted order (say, decreasing). Before pushing a new element, pop everything smaller — and for each popped element, the new element is its 'next greater element'. Each element is pushed once and popped once, so despite the inner while, the total work is O(n).

Use it for: Daily Temperatures, Next Greater Element, Largest Rectangle in Histogram, Trapping Rain Water (stack variant), Stock Span.

Java· Daily temperatures (next warmer day)

int[] dailyTemperatures(int[] t) {
    int n = t.length;
    int[] ans = new int[n];
    Deque<Integer> stack = new ArrayDeque<>(); // indices, decreasing temps
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && t[i] > t[stack.peek()]) {
            int j = stack.pop();
            ans[j] = i - j;        // i is j's next warmer day
        }
        stack.push(i);
    }
    return ans;
}

Tip

Decide push/pop direction by what you're looking for: a decreasing stack finds the NEXT GREATER element; an increasing stack finds the NEXT SMALLER. Store indices, not values, when you need distances.

Queues and BFS level-order

A queue processes nodes in the order they were discovered, which produces breadth-first, level-by-level traversal. The standard pattern records the queue size at the start of each level, then dequeues exactly that many nodes — cleanly separating levels. This is the backbone of shortest-path-in-unweighted-graph and tree level-order problems.

Python· BFS level-order traversal of a tree

from collections import deque

def level_order(root):
    if not root: return []
    out, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):     # exactly this level's nodes
            node = q.popleft()
            level.append(node.val)
            if node.left:  q.append(node.left)
            if node.right: q.append(node.right)
        out.append(level)
    return out

How to talk about this in the interview

“Name the access pattern: "This is nesting/most-recent, so a stack (LIFO)." or "This needs level-by-level order, so a queue (BFS)." For next-greater problems, say: "A brute force is O(n²), but a monotonic stack does it in O(n) — I keep a decreasing stack and pop smaller elements as the answer arrives, so each index is pushed and popped once." That amortised O(n) argument is the signal interviewers want.”

Common mistakes

–Using Python `list.pop(0)` as a queue (O(n)) instead of `deque.popleft()` (O(1))
–Using Java's legacy `Stack` class instead of the faster `ArrayDeque`
–Popping from an empty stack — always check before pop/peek
–Storing values instead of indices in a monotonic stack when distances are needed
–Wrong monotonic direction (increasing vs decreasing) for next-greater vs next-smaller
–Not capturing `len(queue)` before the level loop in BFS, mixing levels together

Complexity summary

Stack/queue/deque operations are O(1). Bracket matching and monotonic-stack problems are O(n) time, O(n) space — each element is pushed and popped at most once. BFS is O(V + E) time and O(V) space for the queue.

Practice problems

17 total

Valid Parentheses