Stacks Explained: LIFO, Operations, and the Problems Stacks Solve

The stack is the simplest structure in this course and one of the most consequential: your program is running on one right now (the call stack — next-lesson-but-one's subject). A stack is any collection restricted to one end: you push items onto the top, pop them off the top, and peek at the top without removing it. That restriction — Last In, First Out (LIFO) — sounds limiting, but it precisely matches every problem involving nesting, reversal, or 'return to the most recent unfinished thing'.

In plain words: the plate stack analogy

Picture a stack of plates in a cafeteria. The kitchen adds freshly washed plates to the top; diners take from the top. If you want the plate at the very bottom, you must first remove every plate above it — that's the contract. When a problem has that shape (the last thing opened is the first that must close), a stack isn't just *an* option, it's *the* structure. Nesting is inherently LIFO: the most recently opened bracket must be the first closed, the most recently called function is the first to return.

  Plate C  ←  TOP  (most recently pushed)
  ─────────
  Plate B
  ─────────
  Plate A  ←  BOTTOM (pushed first)
  ─────────

  push(D) →   Plate D  ← new TOP
              Plate C
              Plate B
              Plate A

  pop() →  removes Plate D, returns "D"
           TOP is now Plate C again

The interface and its costs

Every core operation is O(1). The stack's power lies entirely in the discipline it enforces, not in algorithmic cleverness. That last row is important: if you find yourself searching a stack's interior, you're fighting the abstraction and almost certainly want a different structure.

Two implementations: array vs linked list

class Stack:
    data = []          # dynamic array

    push(x):
        data.append(x)     # O(1) amortized — O(n) only on rare resize

    pop():
        if isEmpty(): raise Error("underflow")
        return data.removeLast()   # O(1)

    peek():
        if isEmpty(): raise Error("empty")
        return data[data.length - 1]  # O(1)

    isEmpty():
        return data.length == 0

class Node:
    value
    next = null

class Stack:
    head = null    # top of the stack
    count = 0

    push(x):
        node = new Node(x)
        node.next = head
        head = node
        count++          # O(1) — insert at head

    pop():
        if isEmpty(): raise Error("underflow")
        value = head.value
        head = head.next
        count--
        return value     # O(1) — delete at head

    peek():
        return head.value

• Dynamic array (the usual choice): push = append, pop = remove-last — cache-friendly, compact, amortized O(1). Occasional resize doubles capacity in O(n) but happens geometrically rarely.
• Singly linked list: push/pop at the head — guaranteed worst-case O(1) with no resize pauses, at the cost of per-node pointer overhead and poorer cache behavior.

Classic application 1: balanced brackets

Is the string '([]{})' properly nested? '([)]' is not — the pairs interleave illegally. This is the canonical stack problem, executed by your editor, compiler, and JSON parser on every keystroke.

function isBalanced(s):
    stack = empty Stack
    pairs = {')': '(', ']': '[', '}': '{'}

    for ch in s:
        if ch in {'(', '[', '{'}:
            stack.push(ch)
        elif ch in {')', ']', '}'}:
            if stack.isEmpty():
                return false       # closer with no opener
            top = stack.pop()
            if top != pairs[ch]:
                return false       # mismatched type, e.g. '([)]'
    return stack.isEmpty()         # true only if all openers closed

Character  Action            Stack (bottom → top)
─────────  ────────────────  ────────────────────
(          push              ( )
[          push              ( [
)          pop → '[' ≠ '('   MISMATCH → return false

Result: NOT balanced ✗

Trace — '([{}])'
Character  Action          Stack
─────────  ──────────────  ─────────────────────
(          push            (
[          push            ( [
{          push            ( [ {
}          pop '{' ✓       ( [
]          pop '[' ✓       (
)          pop '(' ✓       (empty)
End        isEmpty? yes    → return true ✓

Classic application 2: expression evaluation (RPN & shunting-yard)

Postfix notation (RPN) writes operators after their operands: '3 4 + 2 ×' means (3 + 4) × 2. Evaluation is one stack pass: push numbers; on an operator, pop two operands, apply, push the result. The final stack holds one value — the answer.

Token   Action                     Stack (bottom → top)
──────  ─────────────────────────  ───────────────────
3       push 3                     3
4       push 4                     3  4
+       pop 4 and 3, push 3+4=7    7
2       push 2                     7  2
×       pop 2 and 7, push 7×2=14   14

Result: 14  ✓

Handles operator precedence automatically — no parentheses needed.

Infix expressions ('3 + 4 × 2') are converted to postfix with Dijkstra's shunting-yard algorithm: one stack for operators (popped by precedence), one output stream. Together these two passes are, in essence, how calculators and compiler front-ends evaluate arithmetic.

Classic application 3: undo, redo, and browser history

Every user action pushes its inverse onto an undo stack; Ctrl+Z pops and applies. Redo is a second stack — each undo pushes onto redo, and a fresh action clears the redo stack (you can't redo into a divergent timeline). Browser navigation is identical with page URLs instead of text edits.

undoStack = []
redoStack = []

perform(action):
    apply(action)
    undoStack.push(action)
    redoStack.clear()      # diverged — no going "forward"

undo():
    if undoStack.isEmpty(): return
    action = undoStack.pop()
    unapply(action)
    redoStack.push(action)

redo():
    if redoStack.isEmpty(): return
    action = redoStack.pop()
    apply(action)
    undoStack.push(action)

The monotonic stack — the interview power tool

A monotonic stack keeps its contents sorted by evicting anything that would violate the order before each push. It solves the entire family of 'nearest greater/smaller element' problems in O(n) that look O(n²) at first glance.

function nextGreater(arr):
    n = len(arr)
    result = [-1] * n          # default: no greater element
    stack = []                 # stack of indices, values decreasing

    for i in 0..n-1:
        # while the current element beats the stack top's value,
        # the current element IS the answer for that index
        while stack is not empty and arr[i] > arr[stack.top()]:
            idx = stack.pop()
            result[idx] = arr[i]
        stack.push(i)

    # indices remaining on the stack have no greater element → -1
    return result

i=0  arr[0]=2  stack empty, push 0      stack: [0]          (values [2])
i=1  arr[1]=1  1 < 2, push 1             stack: [0,1]        (values [2,1])
i=2  arr[2]=5  5>arr[1]=1 → pop 1, result[1]=5
               5>arr[0]=2 → pop 0, result[0]=5
               push 2                   stack: [2]          (values [5])
i=3  arr[3]=3  3 < 5, push 3            stack: [2,3]        (values [5,3])

End: indices 2,3 remain → result[2]=-1, result[3]=-1

Final: result = [5, 5, -1, -1]
       arr   = [2, 1,  5,  3]

Problems that are this monotonic-stack template in disguise: daily temperatures (days until warmer), stock span (consecutive prior days ≤ today's price), largest rectangle in histogram, trapping rain water. Recognizing the pattern is the skill — the code is almost identical each time.

Under the hood: complexity, invariants, and edge cases

Edge cases every stack implementation must handle: underflow (pop or peek on an empty stack — must raise an error or return a sentinel); unbounded growth (a stack tracking open brackets or recursion frames can grow without limit if the input is pathological — consider a max-size check in resource-constrained settings); thread safety (a bare array/list stack is not thread-safe; use a concurrent stack or external lock if shared across threads).

Common pitfalls

• Popping an empty stack. Always guard with isEmpty(). Half of all first-attempt stack solutions crash here — it's the segfault/exception of stack code.
• Forgetting the end-of-input check. In bracket matching, a non-empty stack at the end means unclosed openers. Passing the per-character checks is not enough.
• Using index access on a stack (stack[i]). You don't have a stack problem if you need interior access. Reconsider the structure.
• Missing the monotonic-stack signal. Phrases like 'next greater', 'previous smaller', 'how many days until' are the tell. Nested loops there leave O(n) on the table.
• Confusing the two-stack undo model. Forgetting to clear the redo stack on a fresh action allows redoing into a diverged history.

When to use stacks — and variations

• Use stacks when: the problem involves nesting (brackets, HTML tags, recursive structure), returning to 'the most recent state' (undo, backtracking, DFS), or processing things in reverse arrival order.
• Min-stack variation: augment the stack with a parallel stack of running minimums so peek_min() is O(1). Every push records min(new_value, current_min); every pop removes both entries. Used in 'design a stack with getMin() in O(1)' — a classic interview question.
• Two-stack queue: simulate a queue with two stacks (inbox and outbox). Enqueue pushes to inbox; dequeue pops from outbox, refilling outbox from inbox when empty. All operations are amortized O(1) — a useful teaching bridge before Lesson 7.

Practice problems

1. Balanced parentheses: given a string of brackets, return true iff every opener is matched and properly nested. Extend it to detect the *position* of the first mismatch.
2. Daily temperatures: given an array of daily temperatures, for each day find how many days until a warmer temperature (or 0 if none). Solve in O(n) with a monotonic stack.
3. Min-stack: design a stack that supports push, pop, top, and getMin — all in O(1) time. No built-in min data structures allowed.

Key takeaways

• A stack is LIFO discipline: push, pop, peek — all O(1). The plate-stack analogy makes the contract concrete and memorable.
• Array-backed stacks are the practical default; linked-list stacks give worst-case O(1) at a cache cost.
• Nesting (brackets, parsers), reversal, and 'return to most recent state' (undo, back buttons, DFS) are inherently stack-shaped problems.
• Postfix evaluation and shunting-yard turn arithmetic into two clean stack passes.
• The monotonic stack solves nearest-greater/smaller families in amortized O(n) — one of the highest-value interview patterns per line of code.

The stack's sibling flips the discipline: First In, First Out. That's the queue — next lesson, along with its two-ended cousin the deque. Then Lesson 8 reveals the most important stack of all: the one your programs run on. Quiz yourself on stacks in the **AI Learning app**.

AI Learning: AI/ML/DS Q&A

A private, offline app to learn Artificial Intelligence, Machine Learning & Data Science at your own level: ~10,000 Q&A, illustrated guides, cheat sheets, quizzes and mock tests.

Coming soon toGoogle Play