Stacks

Last-in, first-out — the structure behind matching brackets, undo, and the call stack itself

LIFOthe last thing pushed is the first thing popped
append/popO(1) at the end — O(n) the moment you touch the front
Monotonic stacknext greater/smaller element in O(n) total
Replace the call stackan explicit stack turns recursion into a loop

1.LIFO principle

A stack is Last-In-First-Out: the most recently added item is always the first one removed. Everything below it stays buried until it is.

Key features

push adds to the top; pop removes from the top — no other position is ever touched directly
The only item directly reachable is the top — reaching anything below it means popping everything above it first
Contrast with a queue (FIFO): a stack always serves the newest item first, a queue always serves the oldest

Command

lifo.pypython

stack = []
stack.append('a')
stack.append('b')
stack.append('c')

print(stack.pop())   # 'c' — the most recently pushed item, out first
print(stack)          # ['a', 'b'] — 'a' is still buried under 'b'

LIFO means the last thing pushed is the first thing popped — picture a stack of plates, not a line of people.

2.Implementing a stack with list (append/pop from the end)

Python's list already is a stack — append() pushes onto the end, and pop() with no argument removes and returns the top, both in O(1).

Key features

stack[-1] peeks the top without removing it — check it before popping if you need to compare against it
pop() on an empty list raises IndexError — check `if stack:` first if an empty stack is a normal case, not a bug
append/pop from the end are amortized O(1); pop(0) or insert(0, x) are O(n) — see algorithms.big-o-and-complexity-analysis.list-fast-ops

A Python list already is a stack — append() to push, pop() to pop, and stack[-1] to peek. Never touch index 0.

3.Valid parentheses / balanced brackets

Scan left to right: push every opening bracket. On a closing bracket, it must match whatever is on top of the stack — if it does not, or the stack is empty, the string is not balanced.

Key features

A matching dict like {")": "(", "]": "[", "}": "{"} turns "does this closing bracket match?" into one O(1) lookup
Two failure shapes: a closing bracket when the stack is empty (nothing to match), or a mismatched pair on top — both mean "not balanced"
A non-empty stack after the scan ends means some opening bracket was never closed

Push opens. On a close, the stack must be non-empty and its top must be the matching open — a non-empty stack at the end means something was never closed.

4.Monotonic stack pattern (next greater/smaller element)

Keep the stack always increasing or always decreasing by popping off elements that break the order before pushing the new one — each pop tells you the next greater (or smaller) element for whatever it pops.

Key features

A decreasing stack finds "next greater element"; an increasing stack finds "next smaller element" — same algorithm, comparison flipped
Each index is pushed once and popped at most once, so the whole scan is O(n) total, even though there is a while loop inside a for loop
Store INDICES on the stack, not values, so the answer array can be filled in by position once an index's "next greater" is found

Push while the stack still satisfies the order; the moment a new value breaks it, popping IS the answer for what got popped — each index is pushed and popped at most once, so the total work is O(n).

5.Evaluating expressions (postfix/infix, conceptually)

Postfix (Reverse Polish) notation puts operators after their operands, so a stack evaluates it in one left-to-right pass: push numbers, and on an operator, pop the top two operands, combine them, and push the result back.

Key features

For a binary operator, pop the SECOND-pushed operand first: b = stack.pop(); a = stack.pop(); push(a OP b) — swapping a and b breaks subtraction and division
A well-formed postfix expression always leaves exactly one value on the stack at the end — that value is the result
Converting infix to postfix (the shunting-yard algorithm) is a separate, harder problem — most interview questions hand you postfix directly and ask only for evaluation

Postfix needs no precedence rules because a stack already enforces the right order: pop two operands, combine, push the result — repeat until one value is left.

6.Using a stack to simulate recursion iteratively (e.g. DFS)

Every recursive call already uses a stack — the call stack — to remember where to return to. Swapping in your own explicit stack (a list) turns the same traversal into a loop, with no risk of hitting Python's recursion limit.

Key features

Depth-first search is the classic case: "visit a node, then recurse into its first child" and "visit a node, then push its children onto a stack" produce the same visiting order
An explicit stack has no recursion-limit ceiling — it grows on the heap, not Python's call stack, so it survives inputs deep enough to raise RecursionError with real recursion
Push children in REVERSE order when the traversal must match recursion's left-to-right visiting order, since a stack pops the most recently pushed child first

An explicit stack replaces the call stack, not the algorithm — push what still needs visiting, pop to visit it, and push children in reverse to keep the same left-to-right order recursion would give.

7.Min-stack (stack that tracks its own running minimum in O(1))

A min-stack answers 'what is the smallest value currently in the stack?' in O(1) by keeping a second stack alongside the first, tracking the running minimum at every point in time.

Key features

Recomputing min() after every push/pop would be O(n) per operation — the parallel stack trades a little extra space for true O(1)
The min-stack's top always reflects the minimum of everything CURRENTLY in the main stack, not the minimum ever seen — popping the true minimum off makes the next-smallest value resurface
Every push adds exactly one entry to both stacks, so they always stay the same length — even when the new value is not a new minimum, the current minimum gets pushed again

Push the running minimum onto a parallel stack alongside every value — popping both together means the min-stack's top is always correct for whatever remains, in O(1), with no rescan.

8.Why appending/popping from the end of a Python list is O(1) but from the front is O(n)

A Python list is stored as one contiguous block of memory. Adding or removing at the end just touches the last slot; adding or removing at the front has to shift every remaining element over by one.

Key features

append() and pop() with no argument touch only the last slot — O(1) amortized, nothing to shift
insert(0, x) and pop(0) both shift every other element by one position — O(n), and it gets slower as the list grows
This is exactly why a list makes a fine stack (only ever touches the end) but a poor queue — collections.deque exists specifically to make BOTH ends O(1)

Command

front_vs_end.pypython

lst = [10, 20, 30, 40]

lst.append(50)      # O(1) — touches only the last slot
lst.pop()             # O(1) — touches only the last slot

lst.insert(0, 5)      # O(n) — shifts every existing element right by one
lst.pop(0)             # O(n) — shifts every remaining element left by one

list only gets O(1) at the end — the moment code touches index 0 (insert(0, ...), pop(0)), the cost becomes O(n), which is why deque exists for anything needing fast operations on both ends.

Spotted a mistake on this page? Tell us.

Read Sheet