Stacks and Queues

Stacks and queues are the same idea — “a sequence you only touch at the ends” — with one rule flipped. That single rule flip is the difference between undo history and a print queue.

What you’ll learn

• Stack (LIFO) built from a plain list: append/pop.
• Queue (FIFO) built from collections.deque: append/popleft.
• Why list.pop(0) is $O(n)$ and deque.popleft() is $O(1)$.
• The monotonic stack pattern — Next Greater Element, runnable.
• Using deque as both a stack and a queue.
• LeetCode-style problems to drill the pattern.

The cue

Stack or queue? The question is which order you need

Stack (LIFO) when the most recent thing must be handled first: nested structure (brackets, expressions), undo, DFS, or “the next greater element” — anything where an item waits for something later to resolve it.

Queue (FIFO) when things must be handled in arrival order: BFS, level-order traversal, scheduling, or a sliding window over a stream.

The single sharpest instance of the distinction: BFS and DFS are the same algorithm with a different container. Swap the deque for a list and breadth becomes depth. If you can state that, you understand both.

Reach for something else when you need the smallest rather than the newest or oldest (a heap), or when you need to evict from both ends (a monotonic deque).

Stack: last in, first out

A stack only cares about one end. Python’s list is already perfect for this — append and pop (no argument) both operate on the end, both $O(1)$ amortized.

stack_basics.py

stack = []
 
stack.append(1)
stack.append(2)
stack.append(3)
print("after pushes:", stack)
 
top = stack.pop()
print("popped:", top)
print("stack now:", stack)
 
print("peek (no pop):", stack[-1])
print("is empty?", len(stack) == 0)

Undo/redo, “match the brackets”, and depth-first traversal (both recursion and its explicit-stack equivalent) all lean on exactly this shape.

Queue: first in, first out

A queue needs cheap operations at both ends: push at the back, pop from the front. A plain list is the wrong tool here — pop(0) has to shift every remaining element down by one, which is $O(n)$.

why_not_list_pop0.py

# DON'T use a list as a queue if you pop from the front repeatedly.
queue_as_list = [1, 2, 3, 4, 5]
 
# Each pop(0) shifts every remaining element left by one slot -> O(n)
front = queue_as_list.pop(0)
print("popped from front:", front)
print("remaining:", queue_as_list, "  <- everything shifted, that cost O(n)")

collections.deque is implemented as a doubly linked sequence of fixed-size blocks, so both ends are cheap — no shifting, ever.

deque_queue.py

from collections import deque
 
queue = deque()
queue.append(1)   # enqueue: add at the back, O(1)
queue.append(2)
queue.append(3)
print("queue:", queue)
 
front = queue.popleft()   # dequeue: remove from the front, O(1)
print("dequeued:", front)
print("queue now:", queue)

Rule of thumb

Only ever touch the end? A plain list is simplest. Need to add/remove from the front too (BFS, sliding windows, a real queue)? Reach for deque — never list.pop(0).

Monotonic stack: Next Greater Element

A monotonic stack keeps its elements in strictly increasing (or decreasing) order by popping anything that violates the order before pushing the new element. It’s the standard trick for “find the next bigger/smaller thing to the right” problems, and it does the whole array in one $O(n)$ pass — each element is pushed and popped at most once.

next_greater_element.py

def next_greater_elements(nums):
    result = [-1] * len(nums)
    stack = []   # holds INDICES, kept so nums[stack] is decreasing
 
    for i, x in enumerate(nums):
        # pop every index whose value is smaller than the current one --
        # x IS their next greater element
        while stack and nums[stack[-1]] < x:
            j = stack.pop()
            result[j] = x
        stack.append(i)
 
    return result
 
 
nums = [2, 1, 2, 4, 3]
print(next_greater_elements(nums))
# 2 -> 4, 1 -> 2, 2 -> 4, 4 -> -1 (none), 3 -> -1 (none)

Watch the stack grow and shrink as it scans the array — every pop happens because the current bar is taller than the one on top of the stack:

sketch Monotonic stack: Next Greater Element p5.js Pause Restart

Bars are scanned left to right. A gray outline marks the current index. Whenever the current bar is taller than the top of the stack (shown stacked on the right), that shorter bar is popped -- the current bar is its next greater element.

deque as both a stack and a queue

collections.deque is $O(1)$ at both ends, so it works perfectly as either a stack or a queue — one structure, two disciplines.

deque_both_roles.py

from collections import deque
 
# used as a STACK: push/pop the same end
stack = deque()
stack.append(1)
stack.append(2)
stack.append(3)
print("stack pop:", stack.pop())        # LIFO: 3
 
# used as a QUEUE: push at the back, pop from the front
queue = deque()
queue.append(1)
queue.append(2)
queue.append(3)
print("queue popleft:", queue.popleft())   # FIFO: 1

Complexity summary

Structure	Operation	Complexity
list as stack	append / pop()	$O(1)$ amortized
list as queue	pop(0)	$O(n)$
deque as queue	append / popleft()	$O(1)$
deque as stack	append / pop()	$O(1)$
Monotonic stack scan	whole array, one pass	$O(n)$ total

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

3 problems

2 easy1 medium0 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

• ○20Valid ParentheseseasyThe definitive stack problem: push openers, and every closer must match the topNeetCode 150Blind 75LeetCode Top Interview 150amazongooglemetamicrosoftbloomberg
• ○232Implement Queue using StackseasyTwo stacks with amortised $O(1)$ dequeue -- only refill the out-stack when it empties
• ○739Daily TemperaturesmediumA monotonic stack of *indices*, so the answer is a distance rather than a valueNeetCode 150amazonmetabloomberg

Practice — real LeetCode problems

Each exercise is the actual LeetCode problem with its real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected output.

LC 20 — Valid Parentheses · Easy

Problem. Given a string of ()[]{}, decide whether the brackets are correctly closed in the correct order and matched by type.

Constraints. 1 <= len(s) <= 10^4.

Examples. "()" gives True · "()[]{}" gives True · "(]" gives False · "([)]" gives False

pch.exerciseTag pch.exerciseTitle

Editorial

The defining stack problem: the most recently opened bracket must be the first closed, which is LIFO by definition.

Time $O(n)$. Space $O(n)$ — worst case all openers.

Two distinct failure modes, both needed:

• A closer with an empty stack — "]". Popping without checking raises IndexError.
• Leftovers at the end — "(". The loop finishes happily, so the final emptiness check is the only thing that catches it.

And "([)]" is why a counter is insufficient: every bracket type is balanced in count, yet the nesting is wrong. Only a stack sees that.

Follow-ups: “One bracket type only?” — an integer counter suffices; it must never go negative and must end at zero. “Minimum additions to make it valid (LC 921)?” — count unmatched closers plus leftover openers. “Longest valid substring (LC 32)?” — much harder: push indices and measure gaps.

LC 1047 — Remove All Adjacent Duplicates In String · Easy

Problem. Repeatedly remove two adjacent equal letters until no such pair remains. Return the final string; the answer is unique.

Constraints. 1 <= len(s) <= 10^5, lowercase letters.

Examples. "abbaca" gives "ca" · "azxxzy" gives "ay"

pch.exerciseTag pch.exerciseTitle

Editorial

The naive reading suggests repeated passes until nothing changes, which is $O(n^2)$. A stack does it in one pass.

Time $O(n)$. Space $O(n)$.

The reason cascades work automatically: after popping a cancelled pair, the new top is whatever preceded them — and the next character is compared against that. So in "azxxzy", removing xx leaves z on top, and the incoming z cancels it immediately. No rescanning is needed because the stack already holds the reduced prefix.

"aaa" giving "a" is a good check: the first two cancel, and the third has nothing left to pair with.

Follow-ups: “Remove runs of k adjacent duplicates (LC 1209)?” — push (char, count) pairs and pop when the count reaches k. “Is the result order-independent?” — yes, the problem states the answer is unique, and the stack argument shows why. “Do it in place?” — use the input list as the stack with a write pointer, giving $O(1)$ extra space for a mutable sequence.

LC 682 — Baseball Game · Easy

Problem. Given a list of operations, compute the total score. Each entry is an integer (record it), "+" (record the sum of the previous two), "D" (record double the previous), or "C" (invalidate the previous record and remove it).

Constraints. 1 <= len(operations) <= 1000, and every operation is valid when it appears.

Examples. ["5","2","C","D","+"] gives 30 · ["5","-2","4","C","D","9","+","+"] gives 27

pch.exerciseTag pch.exerciseTitle

Editorial

A straightforward stack simulation, and a good illustration of why the undo operation ("C") is what makes a stack the right structure — a running total alone could not un-add a value it no longer remembers.

Time $O(n)$. Space $O(n)$.

The trap is "-2". Dispatching with op.isdigit() returns False for a negative number, so it would fall through to an operator branch and either crash or corrupt the score. Testing for the three operator strings explicitly and treating everything else as a number is both simpler and correct. The same trap appears in LC 150 Evaluate RPN.

Follow-ups: “Support a redo?” — a second stack holding invalidated records. “What if "+" could appear with fewer than two records?” — the constraints guarantee validity; a defensive version would check len(stack) >= 2. “Return the running score after each operation?” — keep a rolling total alongside the stack.

Dry run

Queue from two stacks (LC 232) — the amortised argument is the point.

operation	in stack	out stack	cost
push 1	[1]	[]	$O(1)$
push 2	[1,2]	[]	$O(1)$
push 3	[1,2,3]	[]	$O(1)$
pop	[]	[3,2] → pop 1	$O(n)$ — one transfer
pop	[]	[3] → pop 2	$O(1)$
pop	[]	[] → pop 3	$O(1)$

Only transfer when out is empty. Each element is moved between stacks exactly once in its lifetime, so although a single pop can cost $O(n)$, the amortised cost per operation is $O(1)$.

Transferring on every pop is the wrong solution

Moving elements back and forth per operation gives genuine $O(n)$ per pop. The “only when empty” guard is the entire difference between $O(1)$ amortised and $O(n)$ — and it is the thing being tested.

Why deque and not list as a queue. list.pop(0) shifts every remaining element, so it is $O(n)$; used as a queue in a loop that makes an $O(n)$ traversal $O(n^2)$. It passes the samples and TLEs on the real tests, which is the worst failure mode there is.

The variant map

Need	Python	Costs
Stack	list with append / pop	$O(1)$ both
Queue	collections.deque with append / popleft	$O(1)$ both
Both ends	collections.deque	$O(1)$ all four
Min or max in $O(1)$ alongside	stack of (value, running_min) pairs	$O(1)$, LC 155
Window maximum	monotonic deque	$O(n)$ total, LC 239
Priority order	heapq	$O(\log n)$ push/pop

Min Stack: store the running minimum with each entry

Push (value, min(value, current_min)). Then get_min is just reading the top pair — $O(1)$, no scanning, and pops restore the previous minimum automatically because it was stored alongside. Trying to keep a single min variable fails on pop, because you cannot recover the previous minimum.

Pitfalls

• list.pop(0) as a queue. $O(n)$ per call, turning a linear traversal quadratic. Use deque.popleft().
• Popping an empty stack. Guard with if stack: — an IndexError mid-demo is avoidable.
• Transferring on every operation in the two-stack queue. Only transfer when the output stack is empty.
• Keeping a single min variable in Min Stack. A pop cannot restore the previous minimum. Store it per entry.
• Forgetting the final emptiness check in bracket matching. Leftover openers mean unbalanced input; the scan finishing is not the same as success.

Interview follow-ups

They ask	What they’re checking	The answer
“Implement a queue with two stacks”	Amortised reasoning	Transfer only when the output stack is empty; each element moves once, so $O(1)$ amortised
“Now a stack from queues”	Flexibility	Possible but worse — one operation must rotate $n - 1$ elements, so it is genuinely $O(n)$ with no amortisation available
”$O(1)$ get_min on a stack”	Whether you see the trick	Store (value, running_min) pairs. A single variable cannot survive a pop
“Why deque rather than list for a queue?”	Python fluency	list.pop(0) is $O(n)$ because of the shift; deque.popleft() is $O(1)$
“How are BFS and DFS related?”	Conceptual depth	Identical algorithms with different containers — queue gives breadth, stack gives depth. That is the whole difference
“Bounded queue, and it may block”	Practical modelling	That is a producer-consumer problem: queue.Queue with a maxsize, or a condition variable. See Phase 22

Self-check

pch.quizTag Stacks and queues — self-check

1. In the two-stack queue, when should elements be transferred?

   A On every pop, to keep the stacks balanced B Only when the output stack is empty — each element then moves once, giving O(1) amortised C On every push D Never — one stack is enough
   pch.quizShowAnswer

   B — Only when the output stack is empty — each element then moves once, giving O(1) amortised — Transferring per operation gives genuine O(n) per pop. The 'only when empty' guard is exactly what makes the amortised bound work, and it is the point of the question.

2. How do you support O(1) get_min on a stack?

   A Scan the stack when asked B Push (value, running_min) pairs, so the top always carries the current minimum C Keep a single min variable updated on push D Sort the stack
   pch.quizShowAnswer

   B — Push (value, running_min) pairs, so the top always carries the current minimum — A single variable cannot survive a pop — there is no way to recover the previous minimum. Storing it alongside each entry makes pops restore it for free.

3. What is the relationship between BFS and DFS?

   A They are unrelated algorithms B They are the same algorithm with a different container — a queue gives breadth, a stack gives depth C DFS is BFS with memoisation D BFS is only for trees
   pch.quizShowAnswer

   B — They are the same algorithm with a different container — a queue gives breadth, a stack gives depth — The clearest statement of the stack-versus-queue distinction, and a good thing to say out loud: it shows you understand both rather than having memorised two templates.

4. Why is list.pop(0) a problem when using a list as a queue?

   A It raises an error B It shifts every remaining element left, making it O(n) — which turns a linear traversal quadratic C It removes the wrong element D It is fine for queues
   pch.quizShowAnswer

   B — It shifts every remaining element left, making it O(n) — which turns a linear traversal quadratic — It passes the sample tests and TLEs on the full ones, which is the worst failure mode. collections.deque.popleft() is O(1).

Recall card

• Stack (LIFO) — nested structure, undo, DFS, next-greater. Something waits for a later item to resolve it.
• Queue (FIFO) — arrival order, BFS, level order, scheduling.
• The key insight — BFS and DFS are the same algorithm; only the container differs.
• Python — list for a stack, collections.deque for a queue. Never list.pop(0).
• Two-stack queue — transfer only when the output stack is empty; $O(1)$ amortised.
• Min Stack — store (value, running_min) pairs, not a single variable.

Recap

• Stack = LIFO, built from a plain list (append/pop), both $O(1)$ amortized.
• Queue = FIFO. Never use list.pop(0) ($O(n)$) — use collections.deque (append/popleft, both $O(1)$).
• A monotonic stack answers “next greater/smaller” queries for an entire array in one $O(n)$ pass.
• deque is flexible enough to serve as either a stack or a queue.

Next: Hash Tables — how dict and set get $O(1)$ average lookup, and the collision handling underneath.