Coding Patterns
Stack

Stack

The Stack pattern is a fundamental data structure technique that follows the Last-In-First-Out (LIFO) principle. It is the architectural backbone for recursion, undo mechanisms, and nested structural traversal.

Real-World Analogy

Imagine a stack of plates at a buffet:

  • You can only add a new plate to the top.
  • You can only take the top plate off.
  • To get to the bottom plate, you must remove every plate above it first.

In software, this mirrors how function calls are handled (the “call stack”) and how your browser handles the “Back” button (the most recently visited page is the first one you return from).

Visual Explanation

Let’s visualize the basic operations of a stack using a Mermaid diagram. Elements are always added and removed from the same end.

  graph TD
    subgraph Operations
        PUSH[Push: 10]
        POP[Pop: 10]
    end

    subgraph Stack_State [Stack Structure]
        T[Top]
        N1[10]
        N2[20]
        N3[30]
        B[Bottom]
    end

    PUSH --> T
    T --> POP
    T --- N1
    N1 --- N2
    N2 --- N3
    N3 --- B

    style T fill:#f9d,stroke:#333
    style N1 fill:#aaf,stroke:#333
    style B fill:#ddd,stroke:#333

The Mechanics

  1. Push: When you add an element, it becomes the new “Top”.
  2. Pop: When you remove an element, the “Top” is removed, and the element beneath it becomes the new “Top”.
  3. Peek/Top: Looking at the “Top” element without removing it.

When to Use This Pattern

Use the Stack pattern when you encounter these problem characteristics:

  • Nested Structures: Validating parentheses, parsing HTML/XML tags, or evaluating nested mathematical expressions.
  • Reversal Requirements: Reversing a string, a list, or reversing the order of operations.
  • History Tracking: Undo/Redo functionality or “Back” buttons in navigation.
  • LIFO Processing: When the most recently encountered item must be the first one processed (e.g., Depth-First Search).
  • Monotonic Requirements: Finding the “next greater” or “previous smaller” element in an array.

Complexity Analysis

OperationTime ComplexitySpace ComplexityDescription
Push
O(1)
O(1)
Adding an element to the top takes constant time.
Pop
O(1)
O(1)
Removing the top element takes constant time.
Peek
O(1)
O(1)
Accessing the top element takes constant time.
Search
O(N)
O(1)
Finding a specific element requires traversing the stack.
Total SpaceN/A
O(N)
Storing N elements requires linear space.

Common Mistakes

  1. Empty Stack Access: Attempting to pop() or peek() from an empty stack, which causes runtime errors (Stack Underflow).
  2. Wrong Order: Confusing LIFO (Stack) with FIFO (Queue). Always remember: the last one in is the first one out.
  3. Recursion vs. Iteration: Forgetting that recursion uses the system stack. For deep trees, an iterative stack implementation avoids “Stack Overflow” errors.
  4. Monotonic Logic: Using the wrong comparison (e.g., > instead of >=) when maintaining a monotonic stack for “next greater” problems.

Next Steps

Ready to implement? Explore our Code Templates for standardized stack patterns or jump straight into Practice Problems to test your skills.