vizlearn
Home / Algorithms

Stacks (LIFO)

Algorithms & Data StructuresBy Updated

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.

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 / Peek O(1)
Search O(n)
Space O(n)

Overview

A stack stores items so the most recently added is the first removed: last in, first out (LIFO). This order fits nested or unfinished work because only the top item is directly available.

Push, pop, and peek

  • Push adds an item to the top.
  • Pop removes and returns the top item.
  • Peek reads the top without removing it.

These operations are O(1) on a typical stack implementation; Python list append and pop at the end are amortized constant time. Searching for a buried item takes O(n), because items above it must be removed or scanned by another method.

Choose Mode in the visualizer. In stack mode, try Push, Pop, and Peek; in bracket mode, compare a valid sequence with a mismatched one. The top is the only item directly accessible.

Worked example: balanced brackets

When scanning ([{}]), push each opening bracket. On a closing bracket, pop and check that it matches the most recent opener. The order matters: the last bracket opened must close first. The sequence is valid only if no mismatch occurs and the stack is empty at the end.

def balanced(text):
    matching = {")": "(", "]": "[", "}": "{"}
    stack = []
    for char in text:
        if char in "([{":
            stack.append(char)
        elif char in matching:
            if not stack or stack.pop() != matching[char]:
                return False
    return not stack

The final check catches leftover open brackets such as (((, which have no mismatch but are still incomplete.

Where stacks appear

Function calls use a call stack to remember arguments, local variables, and where to resume. Recursive algorithms rely on it; extremely deep recursion can exceed a language’s stack limit. An explicit stack is also used by depth-first search, expression evaluation, and undo systems, where the latest unresolved task or action is handled first.

In Python, append and pop at the end of a list are a simple stack. Do not use pop(0) for a stack: removing from the front shifts the remaining list. Use a deque when efficient operations at both ends are required.

Common mistakes with Stacks

  • Popping an empty stack: check before removal when the input may be malformed.
  • Checking only for mismatches: verify the stack is empty at the end.
  • Using a stack for FIFO order: a queue is the right structure when the oldest item should leave first.
  • Reaching into the middle: that breaks the simple LIFO interface and costs linear time.

Sources and next steps

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
Output
How the code works
  1. 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).
  2. 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.
  3. 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 ")".
  4. 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.
  5. 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.




Predict, then reveal
About to run: switch Mode to Bracket matching. Before it does — what happens to the readout?
Committing to an answer first is the point — the reveal runs the experiment on the visualisation above and reads the real value back, so nothing here is scripted.
Check yourself
0 of 3
Answer without scrolling back up.
  1. Why does the balanced-brackets check test that the stack is empty at the end?
  2. In the postfix evaluator, why is it 'b, a = stack.pop(), stack.pop()' in that order?
  3. A stack built on a Python list uses append and pop with no index because:





 Cheat sheet
Stacks (LIFO)
Push, pop and peek at the top of a LIFO structure, and see how the call stack, bracket matching and DFS all share this idea.
ALGORITHMS · vizlearn.in/dsa/stacks.html
More in Algorithms
AlgorithmsQueues (FIFO)AlgorithmsLinked ListsAlgorithmsHash Tables and HashingAlgorithmsBinary Search Trees
About the author
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.
About VizLearnGitHubLinkedInContact