λDSA Learning Hubpart of DSA Atlas

Stacks

Beginner~3h · 8 lessons12 practice problems

Last-in-first-out in O(1): balanced parentheses, expression evaluation, min-stack design, and the gateway to monotonic-stack patterns.

0 of 8 lessons checked off

Introduction

What it is

  • A stack is a collection with one rule: you may only add, read, or remove at the top. Last In, First Out (LIFO).
  • It needs just five operations — push, pop, peek, is_empty, size — and every one of them is O(1).

Why it matters

  • Stacks model 'most recent unfinished thing': the newest open bracket must close first, the latest function call must return first, the last edit is undone first.
  • In interviews, an explicit stack is how you convert recursion to iteration, evaluate expressions, and (as a monotonic stack) crush a whole family of 'next greater element' problems from O(n²) to O(n).

How it works

  • Back it with a dynamic array (Python list): append pushes, pop() pops, [-1] peeks — the array end is the top.
  • A linked-list backing pushes/pops at the head instead; same O(1) costs, steadier worst-case latency, more memory per element.

Where it's used

  • The call stack that runs your programs, undo/redo in editors, browser back/forward, and the parser that validated this very page's HTML.

In interviews

  • Valid parentheses, evaluate reverse Polish notation, min stack, daily temperatures (monotonic), simplify path, decode string, largest rectangle in histogram.
Analogy: A stack is a pile of dinner plates: new plates go on top, and you take from the top. Getting the bottom plate means removing every plate above it — so nobody ever asks for the bottom plate.

Interactive diagram

Openers push; each closer must match the top. Scanning "{[()]}" shows why LIFO is exactly the right shape.

Scan the string

Check whether "{[()]}" is balanced. Openers are pushed; each closer must match the most recent unmatched opener — exactly LIFO order.

Lessons in this topic

Check off lessons as you go — your progress is saved in this browser.

  1. Stack fundamentals and LIFO

    The contract, the five operations, and why each is O(1).

    15 min
  2. Array-based stack

    Python list as a stack; amortised append; overflow in fixed buffers.

    15 min
  3. Linked-list-based stack

    Head push/pop; trade-offs vs the array backing.

    15 min
  4. Balanced parentheses

    The canonical stack problem: openers wait, closers must match the top.

    20 min
  5. Expression evaluation & infix/postfix/prefix

    Why postfix needs no parentheses; evaluating RPN with one stack.

    30 min
  6. Min stack (design)

    O(1) get-min by stacking (value, min-so-far) pairs.

    20 min
  7. Next greater element (preview)

    The monotonic stack — full pattern page later in the roadmap.

    15 min
  8. Stack using queues

    The classic conversion exercise and its cost asymmetry.

    15 min

Operations

Push, pop, peek, is_empty, size

All five operations touch only the top element — no traversal ever happens, hence O(1) each.

An empty stack

A stack exposes one end — the top. All three core operations (push, pop, peek) touch only that end, which is why each is O(1).

class Stack:    """Array-backed stack. All operations O(1) (append amortised)."""    def __init__(self) -> None:        self._items: list[int] = []    def push(self, value: int) -> None:        self._items.append(value)          # top = end of the list    def pop(self) -> int:        if not self._items:            raise IndexError("pop from empty stack")        return self._items.pop()    def peek(self) -> int:        if not self._items:            raise IndexError("peek at empty stack")        return self._items[-1]    def is_empty(self) -> bool:        return not self._items    def __len__(self) -> int:        return len(self._items)
Time: O(1) for every operation (push amortised)Space: O(n) total

Edge cases

  • pop/peek on an empty stack must raise, not return None silently.
  • A fixed-capacity backing adds an overflow case — check before push.
  • len on an empty stack is 0, not an error.

Common mistakes

  • Using list.pop(0) or insert(0, x) — that's the WRONG end and costs O(n).
  • Returning None on empty pop, which hides bugs until much later.

Balanced parentheses

Push every opener. On a closer, the stack top must be its partner; anything else — or leftovers at the end — means unbalanced.

Scan the string

Check whether "{[()]}" is balanced. Openers are pushed; each closer must match the most recent unmatched opener — exactly LIFO order.

def is_balanced(s: str) -> bool:    """Validate (), [], {} nesting. O(n) time, O(n) space."""    pairs = {")": "(", "]": "[", "}": "{"}    stack: list[str] = []    for ch in s:        if ch in pairs:                     # a closer            if not stack or stack[-1] != pairs[ch]:                return False            stack.pop()        elif ch in "([{":                   # an opener            stack.append(ch)    return not stack                        # leftovers = unbalanced
Time: O(n)Space: O(n) worst case — all openers

Edge cases

  • A closer with an empty stack — ')(' fails on the first character.
  • Leftover openers — '((' must return False via the final emptiness check.
  • Empty string is balanced.

Common mistakes

  • Only counting opens minus closes — counts pass '([)]' which is invalid.
  • Forgetting the final `not stack` check, accepting '((('.

Evaluate postfix (Reverse Polish) notation

Operands push; an operator pops two, computes, and pushes the result. One pass, no precedence rules needed.

Evaluate postfix (Reverse Polish) notation
def eval_rpn(tokens: list[str]) -> int:    """Evaluate e.g. ["2","1","+","3","*"] → 9. O(n) time/space."""    stack: list[int] = []    ops = {        "+": lambda a, b: a + b,        "-": lambda a, b: a - b,        "*": lambda a, b: a * b,        "/": lambda a, b: int(a / b),   # truncate toward zero    }    for token in tokens:        if token in ops:            b = stack.pop()             # top is the RIGHT operand            a = stack.pop()            stack.append(ops[token](a, b))        else:            stack.append(int(token))    return stack[0]
Time: O(n)Space: O(n)

Edge cases

  • Operand order: the first pop is the right-hand operand — subtraction and division break if swapped.
  • Division truncates toward zero: int(a / b), not a // b, for negative operands.
  • Single-token input like ['42'] returns 42.

Common mistakes

  • Popping a then b in that order and computing a − b (backwards).
  • Using // for division: −7 // 2 = −4 but the expected truncation is −3.

Min stack (O(1) minimum)

Store, alongside each value, the minimum of everything at or below it. Popping automatically 'rolls back' the minimum.

Min stack (O(1) minimum)
class MinStack:    """push/pop/top/get_min all O(1) by pairing each value    with the minimum of the stack up to that point."""    def __init__(self) -> None:        self._items: list[tuple[int, int]] = []   # (value, min_so_far)    def push(self, value: int) -> None:        current_min = min(value, self._items[-1][1]) if self._items else value        self._items.append((value, current_min))    def pop(self) -> int:        if not self._items:            raise IndexError("pop from empty stack")        return self._items.pop()[0]    def top(self) -> int:        return self._items[-1][0]    def get_min(self) -> int:        return self._items[-1][1]
Time: O(1) for all four operationsSpace: O(n) — one extra int per element

Edge cases

  • get_min on empty should raise like pop.
  • Duplicated minimums pop correctly because each entry carries its own min.
  • Pushing a new global minimum: min pairs update naturally.

Common mistakes

  • Keeping a single min variable — unrecoverable after popping the minimum.
  • Scanning the stack in get_min (O(n)) — the design goal was O(1).

Complexity analysis

OperationBestAverageWorstSpace
pushO(1)O(1)O(n) on resize—
popO(1)O(1)O(1)—
peek / is_empty / sizeO(1)O(1)O(1)—
search for a valueO(1)O(n)O(n)O(1)
balanced-parentheses scanO(n)O(n)O(n)O(n)

Searching a stack means popping through it — if you need search, a stack is the wrong structure.

Python implementation

Production-quality code with type hints, validation, and docstrings.

Linked-list-backed stack (steady O(1), no resizes)
from typing import Optionalclass _Node:    __slots__ = ("value", "next")    def __init__(self, value: int, next: Optional["_Node"]):        self.value = value        self.next = nextclass LinkedStack:    """Stack backed by a singly linked list; the head is the top.    Worst-case O(1) per operation (no array resizes)."""    def __init__(self) -> None:        self._top: Optional[_Node] = None        self._size = 0

What interviewers expect you to know

What interviewers expect you to know

  • LIFO contract and the five O(1) operations without hesitation.
  • The stack ↔ recursion equivalence: any recursion can be made iterative with an explicit stack.
  • Postfix evaluation and infix→postfix exist because stacks encode operator precedence.
  • The min-stack pairing trick — the template for 'augment a structure with O(1) aggregates'.

Classic follow-ups

  • "Implement a queue using two stacks" — amortised O(1) via an in-box and a flipped out-box.
  • "Max stack?" — same pairing trick with max; supporting popMax efficiently needs a fancier design (say so).
  • "What breaks with concurrent pushes?" — the read-modify-write on top needs locking; a fine systems tangent to acknowledge.

How to explain a stack solution

  • Name what the stack holds and its invariant: 'the stack holds unmatched openers, newest on top.' If you can't state the invariant, the stack is probably the wrong tool.
  • On monotonic problems, say what popping means ('this index found its answer') — that sentence is the whole algorithm.

Common mistakes

Wrong end of the list

insert(0, x) / pop(0) turn O(1) stack ops into O(n). The top must be the array END: append / pop().

No empty-stack guard

pop and peek on an empty stack should raise immediately. Silent None returns surface as confusing crashes two functions later.

Counting instead of stacking

Balance checking with a counter accepts interleaved '([)]'. Matching kinds requires remembering WHICH opener is unfinished — that's the stack.

RPN operand order flipped

The first pop is the right operand: for '6 2 /' compute 6 / 2, not 2 / 6.

Forgetting leftovers

A scan that ends with a non-empty stack means unclosed openers — return False, not True by default.

Practice problems

Hand-picked from the 355-problem DSA Atlas. Reveal hints and solutions progressively; mark and bookmark as you solve.

Easy (1)

Medium (10)

Decode String
MediumNested-context stack~25 min

Commonly associated with: Google, Amazon, Microsoft, Bloomberg

O(n * maxK) where the product bounds total output length time · O(n) for the two stacks in proportion to bracket nesting depth space

Hard (1)

Topic quiz

6 questions across concepts, code output, complexity, and scenarios. Answer all, then submit for explanations.

  1. Code output1. What does this print?
    stack = []for x in (1, 2, 3):    stack.append(x)stack.pop()stack.append(4)print(stack[-1], stack[0])
  2. Concept2. Why does '([)]' fail a proper balance check even though counts match?
  3. Scenario3. You need undo functionality in an editor. Which structure and why?
  4. Code output4. Evaluating the RPN expression ['4', '13', '5', '/', '+'] returns…
  5. Complexity5. In the MinStack design that stores (value, min_so_far) pairs, get_min costs…
  6. Concept6. Converting recursion to iteration with an explicit stack changes space complexity how?
0 of 6 answered

Frequently asked questions

Should I use Python's list or deque for a stack?

list is idiomatic and fast: append/pop at the end are amortised O(1). deque also works (append/pop on the right) with steadier worst-case latency. Never use the FRONT of a list.

What's the difference between infix, prefix, and postfix?

Where the operator sits: a+b (infix), +ab (prefix/Polish), ab+ (postfix/RPN). Postfix needs no parentheses or precedence rules, which is why compilers and calculators convert to it — using a stack.

When is a stack the wrong choice?

Whenever you need FIFO order (use a queue), random access (array), or lookup by key (hash map). If you find yourself digging below the top, the structure is telling you something.

Summary & cheat sheet

Key takeaways

  • Stack = LIFO with five O(1) operations; the array end is the top.
  • The invariant sentence — 'the stack holds X, newest on top' — designs the algorithm for you.
  • Balanced brackets, RPN evaluation, and undo are pure stack shapes.
  • Min stack: pair each value with the min-so-far for O(1) aggregates.
  • Recursion ↔ stack: same idea, different bookkeeper.

Formulas & cheat sheet

  • Push then pop sequences are balanced-bracket strings (Catalan structure)
  • Valid pop-sequence check: simulate with a stack in O(n)
  • Infix → postfix: operators wait on the stack until higher precedence arrives

Interview checklist

  • I can implement a stack both array-backed and linked.
  • I can write the bracket validator with all three failure modes.
  • I can evaluate RPN with correct operand order and truncation.
  • I can explain the min-stack pairing in one sentence.