Stack vs Queue — When to Use Which, and What Each Enables

Stack and queue are two answers to the same question: which pending item do I process next? Stack picks the most recent one; queue picks the oldest. The answer changes the algorithm, not the code shape — same push, same pop, same peek, different visit order. This post is the tie-breaker: what each enables, when the choice is forced, and why "just use a list" isn't always right.

The verdict

Stack (LIFO — Last In, First Out). Pop returns the most recent push. Enables DFS, matching problems (parentheses, HTML tags), monotonic-stack scanning, undo/redo, expression evaluation.

Queue (FIFO — First In, First Out). Pop returns the oldest push still pending. Enables BFS, level-order tree traversal, streaming/pipeline processing, task scheduling.

Same asymptotic ops — O(1) push and pop for both. The choice is which visit order the algorithm needs, and that's decided by the problem's invariant, not by preference.

When to reach for a stack

DFS traversal. Iterative DFS is a stack of "nodes to visit". See the iterative vs recursive DFS post.
Matching and nesting. LC 20 Valid Parentheses, LC 32 Longest Valid Parentheses, HTML/XML tag matching. Each opener pushes; each closer pops and checks the top.
Monotonic stack. Next/previous greater/smaller problems. See the monotonic-stack pattern post.
Undo/redo. Any state with reversible operations — a text editor's edit history, LC 155 Min Stack.
Expression evaluation. Shunting-yard, postfix evaluation, LC 150 Evaluate Reverse Polish Notation, LC 224 Basic Calculator.
Recursive-to-iterative conversion. Any problem the recursion solves naturally, the stack solves iteratively — including backtracking if you need it explicit.

When to reach for a queue

BFS traversal. The queue is what makes BFS "explore in order of distance from start". See the BFS vs DFS post.
Level-order tree traversal. LC 102, LC 199, LC 993. The queue naturally groups nodes by depth when you snapshot len(queue) at each iteration.
Streaming with FIFO order. LC 933 Number of Recent Calls: enqueue timestamp, dequeue when it falls outside the window.
Task scheduling. Round-robin, cooldown-based (LC 621 Task Scheduler pairs a queue with a heap).
Multi-source BFS. LC 994 Rotting Oranges, LC 542 01 Matrix. Enqueue every source at the start; BFS from all of them in parallel.

Side by side

Aspect	Stack	Queue
Order	LIFO — last in, first out	FIFO — first in, first out
Push (add)	O(1)	O(1)
Pop (remove)	O(1)	O(1)
Peek (see next-out)	O(1)	O(1)
Access middle	O(n)	O(n)
Traversal it powers	Depth-first	Breadth-first
Solves matching / nesting	✓	✗
Solves shortest-path (unweighted)	✗	✓
Python type	`list` (append / pop)	`collections.deque` (append / popleft)
Java type	`ArrayDeque` (`push`/`pop`)	`ArrayDeque` (`offer`/`poll`)
JavaScript type	`Array` (push / pop)	`Array` with head index, or custom class
C++ type	`std::stack` or `std::vector`	`std::queue` or `std::deque`

The row worth calling out: never use list as a queue in Python. list.pop(0) is O(n); a proper queue needs collections.deque for O(1) popleft. See the BFS vs DFS post for the accidental-O(V²) case this creates.

Worked example — stack (LC 20 Valid Parentheses)

Given a string of (), [], {}, determine if brackets are validly matched and nested.

Each opener pushes onto the stack. Each closer pops and checks the top matches. LIFO order is exactly what "innermost bracket must close first" means.

def isValid(s):
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    for ch in s:
        if ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
        else:
            stack.append(ch)
    return not stack

A queue can't solve this — FIFO order can't check "innermost first". The problem's nesting invariant is LIFO.

Worked example — queue (LC 933 Number of Recent Calls)

You have a stream of ping timestamps. ping(t) returns the number of pings in the last 3000 ms including t.

Enqueue each ping's timestamp; dequeue any timestamp that falls outside the window. Queue's FIFO order matches the "oldest expires first" invariant.

from collections import deque

class RecentCounter:
    def __init__(self):
        self.q = deque()

    def ping(self, t):
        self.q.append(t)
        while self.q[0] < t - 3000:
            self.q.popleft()
        return len(self.q)

Each ping is amortised O(1) — each timestamp enters and leaves the queue exactly once. A stack couldn't solve this: you'd have to scan for the oldest timestamp on every call.

Bottom line

Ask: which pending item does the algorithm want next?

The most recent (matching, DFS, undo, monotonic scanning) — stack.
The oldest (BFS, level-order, streaming, task scheduling) — queue.

The choice isn't stylistic; the problem's invariant decides. Get the invariant right and the container follows in one line.

For the O(1) push/pop claim both containers rest on — plus the language-specific gotcha that list.pop(0) in Python and Array.shift in JavaScript are secretly O(n) — see the time-complexity-of-common-operations post.