Last in, first out. Only the top is reachable — and that single restriction is exactly what makes stacks perfect for undo history, bracket matching, and the call stack behind every recursive function.
Overview
Quick Context
A stack is a collection where you may only touch one end — the top. The last thing you put in is the first thing you take out, which is why it is called LIFO: Last In, First Out. Think of a stack of plates.
Controls
The Stack
step 0
bottom
Insight
A stack allows exactly three operations, all at the same end: push (add to top), pop (remove top), peek (look at top).
Where stacks are used
• The call stack for function calls
• Undo / redo history
• Browser back button
• Bracket & syntax matching
• Depth-first search
• Expression evaluation
size0
top–
Complexity
Push / Pop / PeekO(1)
SearchO(n)
SpaceO(n)
Stacks (LIFO)
One end, three operations, and a surprising amount of the computing world built on top.
Three Operations, All O(1)
push(x) — put x on top.
pop() — remove and return the top item.
peek() — read the top without removing it.
All three are O(1) because they never touch the rest of the structure. That guarantee is the reason stacks are used in performance-critical places like the call stack.
Note what you cannot do: reach the middle. Searching a stack is O(n) and requires popping everything above what you want. The restriction is the feature — it makes the structure simple and fast.
The call stack is a stack
The most important stack in any program is the one you do not write. Every function call pushes a frame holding local variables, arguments and the return address; every return pops it.
That is why:
Recursion depth costs memory — each level is a frame.
Infinite recursion raises RecursionError — the stack has a limit.
A traceback reads bottom-up — it is a printout of the stack, most recent call last.
Understanding that makes recursion, DFS and backtracking all one idea rather than three. Recursion is a stack you get for free; an explicit stack is recursion you manage yourself.
Bracket Matching: The Classic Application
Switch to bracket mode and step through. The rule is beautifully simple:
See an opening bracket → push it.
See a closing bracket → pop and check it matches. If it does not, the expression is invalid.
At the end, the stack must be empty — anything left over is an unclosed bracket.
A stack is exactly right here because brackets nest: the most recently opened one must always close first. Every code editor that highlights a missing brace runs this algorithm.
Last in, first out
A stack allows two operations: add to the top, and remove from the top. Nothing else — no indexing, no removing from the middle.
That restriction is the point. A stack models any situation where the most recent thing must be dealt with first, and there are more of those than one expects.
Operation
Meaning
Cost
push
Add to the top
O(1)
pop
Remove and return the top
O(1)
peek / top
Look without removing
O(1)
is_empty
Nothing left
O(1)
In Python a plain list is a stack: append to push, pop to pop.
stack = []
stack.append(1)
stack.append(2)
stack.pop() # 2 - the most recent
stack[-1] # 1 - peek without removing
Both are O(1) amortised, because they operate on the end of the array. The mistake to avoid is pop(0) — removing from the front shifts every element, making it O(n). That is what collections.deque is for.
Matching and undoing
The two archetypal stack problems.
Balanced brackets. Push each opening bracket; on a closing bracket, pop and check it matches:
def balanced(s):
pairs = {")": "(", "]": "[", "}": "{"}
stack = []
for ch in s:
if ch in "([{":
stack.append(ch)
elif ch in pairs:
if not stack or stack.pop() != pairs[ch]:
return False
return not stack # anything left open means unbalanced
The final return not stack is the part people forget: "(((" has no mismatch and is still unbalanced.
Undo. Push each action as it happens; undo pops the most recent. Redo needs a second stack — popping from undo pushes onto redo, and any new action clears redo. That pair of stacks is exactly how every text editor's undo works.
Both problems share a shape: the most recent unresolved item is the one that must be resolved next, and that is precisely what LIFO provides.
Bracket matching, and the errors a stack can name
A stack turns a problem that looks like it needs lookahead into one pass with one pointer. Bracket matching is the standard demonstration, but the version worth writing is the one that reports WHICH bracket went wrong and where -- because that is what a parser or a linter actually has to do.
example_01.pyPython
PAIRS = {")": "(", "]": "[", "}": "{"}
OPEN = set(PAIRS.values())
def check(s):
stack = [] # holds (character, index)
for i, c in enumerate(s):
if c in OPEN:
stack.append((c, i))
elif c in PAIRS:
if not stack:
return "unexpected %s at %d" % (c, i)
want = PAIRS[c]
got, at = stack.pop()
if got != want:
return "%s at %d closed by %s at %d" % (got, at, c, i)
if stack:
c, at = stack[-1]
return "%s at %d never closed" % (c, at)
return "balanced"
tests = [
"(a[b]{c})",
"([)]",
"(()",
"())",
"",
"no brackets here",
"{[()]}",
]
for t in tests:
print("%-20r %s" % (t, check(t)))
# Three different failures, three different messages, one pass and one
# stack. Note "([)]": every bracket is paired and the counts are equal --
# two opens, two closes -- so a counter would call it balanced. Only the
# ORDER is wrong, and order is exactly what a stack remembers.
print()
print("counting instead of stacking says '([)]' is fine:",
"([)]".count("(") == "([)]".count(")") and
"([)]".count("[") == "([)]".count("]"))
# The reason a stack is the right structure: the constraint is "the most
# recent unclosed bracket must be the next one closed". Most recent first
# IS last-in-first-out, so the data structure is a restatement of the
# rule.
#
# The same shape solves anything with nesting. An evaluator for postfix
# arithmetic is the same loop with numbers instead of brackets:
def rpn(expr):
stack = []
for tok in expr.split():
if tok in "+-*/":
b, a = stack.pop(), stack.pop()
stack.append({"+": a + b, "-": a - b,
"*": a * b, "/": a // b}[tok])
else:
stack.append(int(tok))
return stack.pop()
print()
for e in ("3 4 +", "3 4 + 2 *", "5 1 2 + 4 * + 3 -"):
print("%-20s = %d" % (e, rpn(e)))
# That last one is (5 + ((1 + 2) * 4)) - 3 = 14, evaluated with no
# parentheses and no precedence rules -- the order is already in the
# arrangement. Which is why compilers convert to postfix before
# generating code, and why the machine they generate it for is itself a
# stack.
Output
Things to try
Push A, B, C then pop. C comes back first — LIFO in one action.
Try to reach the bottom item. You cannot, without popping everything above it. That is the trade-off for O(1) access to the top.
Pop from an empty stack. The lab reports stack underflow — a real error class you will meet.
Switch to bracket matching with the valid expression and step through. Watch the stack grow on openers and shrink on closers, finishing empty.
Now run the mismatched one. The algorithm stops the moment a closer disagrees with the top of the stack — it does not need to read the rest.
What to remember
A stack restricts you to one end, and that restriction buys O(1) push, pop and peek. It models anything where the most recent item must be handled first: nested brackets, function calls, undo history, and depth-first traversal.
Expression evaluation and parsing
Stacks are how arithmetic is actually evaluated by machines.
Postfix (reverse Polish) evaluation needs one stack and no precedence rules at all:
def eval_postfix(tokens):
stack = []
for t in tokens:
if t in "+-*/":
b, a = stack.pop(), stack.pop() # note the order
stack.append({"+": a+b, "-": a-b, "*": a*b, "/": a/b}[t])
else:
stack.append(float(t))
return stack.pop()
eval_postfix("3 4 + 2 *".split()) # (3+4)*2 = 14
The b, a = pop(), pop() order matters for subtraction and division — the second pop is the left operand.
Infix to postfix is the shunting-yard algorithm: operands go straight to the output, operators onto a stack, and an incoming operator pops any of higher or equal precedence first. Parentheses push and pop directly.
That is how calculators, spreadsheet formula engines and compilers turn 2 + 3 * 4 into something evaluable, and it is the reason precedence and associativity can be handled without recursion.
The same structure underlies recursive-descent parsing — where the call stack does the work — and the shift-reduce parsers used by tools like yacc.
The monotonic stack
A stack whose contents are kept in sorted order, which solves a specific family of problems in O(n) that look like they need O(n²).
Next greater element: for each item, find the first larger item to its right.
def next_greater(arr):
out = [-1] * len(arr)
stack = [] # holds indices, values decreasing
for i, x in enumerate(arr):
while stack and arr[stack[-1]] < x:
out[stack.pop()] = x # x is the answer for everything smaller
stack.append(i)
return out
Each index is pushed and popped at most once, so the whole scan is O(n) despite the inner loop.
The insight generalises: whenever the answer for an earlier element becomes known the moment a later element arrives, a monotonic stack finds all the answers in one pass. It solves the largest rectangle in a histogram, trapping rainwater, stock spans and daily temperatures — all classic O(n²)-looking problems.
Where stacks appear
The call stack in every program.
Undo and redo in editors.
Browser history — back is a pop.
Depth-first search — explicit or via recursion.
Backtracking — the state to restore is on the stack.
Expression evaluation and parsing.
Bracket and tag matching in editors and validators.
Virtual machines. The JVM and CPython are stack machines — bytecode operates on an operand stack.
Questions people ask
Should I use a list or deque as a stack? A list is fine and slightly faster for stack use, because append and pop at the end are O(1). deque matters when you need efficient operations at both ends.
What is stack overflow? Exceeding the call stack's size, usually through unbounded recursion. Python raises RecursionError; lower-level languages crash.
Why is pop(0) slow? It removes from the front, shifting every remaining element — O(n). Use deque.popleft().
How is a stack different from a queue? LIFO against FIFO. A stack gives depth-first behaviour, a queue breadth-first.
Can a stack be implemented with a linked list? Yes — push and pop at the head, both O(1). An array is usually faster because of cache behaviour.
What is a monotonic stack for? Problems where an element's answer is determined by the next larger or smaller element, solved in one O(n) pass.
Recap in one screen
Push and pop at one end only; that restriction is what makes it useful.
A Python list is a stack: append and pop, both O(1) amortised. Never pop(0).
The call stack is a stack, which is why recursion has a depth limit and tracebacks read as they do.
Matching brackets, undo/redo, DFS and expression evaluation are all the same LIFO shape.
A monotonic stack turns several classic O(n²) problems into single O(n) passes.
Where to practise this
The stack questions interviewers actually ask, each with a runnable editor and a stepped walkthrough:
Valid parentheses — the classic, and the empty-stack check at the end.
Run it in Python
A stack built on a plain list, then put to work on the two jobs it is famous for: matching brackets and evaluating postfix. Both are traced push by push.
stacks.pyPython 3
# A stack: add and remove at one end only. Last in, first out.
class Stack:
def __init__(self):
self._items = []
def push(self, x):
self._items.append(x) # append is amortised O(1)
def pop(self):
if not self._items:
raise IndexError("pop from an empty stack")
return self._items.pop() # pop() with no index: the END
def peek(self):
return self._items[-1] if self._items else None
def __len__(self):
return len(self._items)
s = Stack()
for x in "ABC":
s.push(x)
print(f"push {x} -> top is {s.peek()}, size {len(s)}")
print(f"pop -> {s.pop()}, top is now {s.peek()}")
# --- job 1: balanced brackets ------------------------------------------
def balanced(text):
pairs = {")": "(", "]": "[", "}": "{"}
stack = Stack()
for ch in text:
if ch in "([{":
stack.push(ch)
elif ch in pairs:
if len(stack) == 0 or stack.pop() != pairs[ch]:
return False # closer with no matching opener
return len(stack) == 0 # anything left open is unbalanced
print()
for text in ["(a[b]{c})", "(a[b)c]", "((()", "()"]:
print(f"{text:>10}: {balanced(text)}")
# --- job 2: evaluating postfix -----------------------------------------
def postfix(expr):
stack = Stack()
for token in expr.split():
if token.isdigit():
stack.push(int(token))
else:
b, a = stack.pop(), stack.pop() # note the order
stack.push({"+": a + b, "-": a - b,
"*": a * b, "/": a // b}[token])
print(f" {token:>3} -> {stack._items}")
return stack.pop()
print()
print("3 4 + 2 * =")
print("result:", postfix("3 4 + 2 *"))
Output
How the code works
self._items.append(x) / self._items.pop()Both act on the end of the list, which is why both are O(1). Using insert(0, x) and pop(0) would be the same stack with every operation turned into O(n).
if not self._items: raise IndexErrorPopping an empty stack is a bug in the caller, not a value to return. Returning None instead hides the mistake until something far away fails.
if len(stack) == 0 or stack.pop() != pairs[ch]:Two different failures: a closer with nothing open, and a closer that does not match what is open. Both have to be checked, and forgetting the first crashes on ")".
return len(stack) == 0The last check catches "((()" — every closer matched, but three openers were never closed. A stack that is not empty at the end is the whole test.
b, a = stack.pop(), stack.pop()The second operand comes off first, because it went on last. Reverse these two names and + and * still look correct while - and / silently invert.
Change one thing
Feed balanced a string of 10,000 unmatched openers. It returns False without slowing down — the stack only ever grows.
Evaluate "5 1 2 + 4 * + 3 -" by hand, then run it. This is the notation compilers actually emit.
Add a min() in O(1) by pushing (value, min_so_far) pairs. A classic interview question, and four lines here.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.
Check yourself
0 of 3
Answer without scrolling back up.
Why does the balanced-brackets check test that the stack is empty at the end?
"((()" has every closer matched and is still unbalanced. Without the final check it passes.
In the postfix evaluator, why is it 'b, a = stack.pop(), stack.pop()' in that order?
Swap the names and + and * still look right while - and / silently invert - the worst kind of bug to find.
A stack built on a Python list uses append and pop with no index because:
insert(0, x) and pop(0) shift every other element. Same stack, every operation turned into O(n).
Cheat sheet
Stacks (LIFO)
Last in, first out. Only the top is reachable — and that single restriction is exactly what makes stacks perfect for undo history, bracket matching, and the call stack behind every recursive function.
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.