Day 10: Stack Data Structure Explained Simply

Why is the strict rule "last one in, first one out" the secret behind your code editor's Undo button and your browser's crash recovery?


In 30 Seconds

A Stack is a linear data structure that enforces one strict rule: LIFO (**Last-In, First-Out** [the newest item added is always the very first item removed]). You can only add items to the very top (push) and remove items from the very top (pop). You are never allowed to pull an item out from the middle or the bottom. This deliberate restriction makes stacks blazingly fast ($O(1)$ for every operation) and ideal for tracking nested tasks.


The Real-World Analogy: A Spring-Loaded Cafeteria Plate Dispenser

Picture the stainless-steel plate warmer at an all-you-can-eat buffet.

  • A kitchen worker washes five clean plates and pushes them down onto the spring-loaded cylinder one after another: Plate 1 goes in first, followed by 2, 3, 4, and finally Plate 5 sitting right on top.
  • When a hungry customer walks up, they grab Plate 5 off the top—never Plate 1 from the bottom.
  • The last plate placed onto the stack is always the first plate taken off.

Picture This

Here is a visual diagram showing how push and pop modify a LIFO Stack from the top end only:

30 (TOP) 20 10 PUSH(30) POP() -> 30
  PUSH(30)                     TOP -> [ 30 ]  <-- Added last, removed first!
     |                                [ 20 ]
     v                                [ 10 ]
  +------+                           +------+
  |  20  |   --->   POP() returns 30, leaving [20] as the new TOP.
  |  10  |
  +------+

And here is how a Stack checks balanced brackets in code ("{[()]}"):

  Input:  {   [   (   )   ]   }
          |   |   |   |   |   |
  Stack:  {   [   (   |   |   |
                  ^---+   |   |   <-- ')' matches top '(', pop '('!
              ^-----------+   |   <-- ']' matches top '[', pop '['!
          ^-------------------+   <-- '}' matches top '{', pop '{'!
  
  End result: Stack is empty -> Valid syntax!

How It Actually Works

  1. Pick a Backing Store: Build a stack using a dynamic array (Python list) or a singly linked list where head acts as the top.
  2. Push to the Top ($O(1)$): Append the new item to the end of the array and update your top tracker.
  3. Peek Before You Leap ($O(1)$): Read the top item without removing it so you can inspect what's next safely.
  4. Pop from the Top ($O(1)$): Remove and return the most recently added item, raising an underflow error if empty.

Show Me The Code

# Day 10: Stack Data Structure Implemented from Scratch in Python

class Stack:
    def __init__(self):
        self._items = []

    def push(self, item):
        """Places an item onto the top of the stack in O(1) amortized time."""
        self._items.append(item)

    def pop(self):
        """Removes and returns the top item in O(1) time."""
        if self.is_empty():
            raise IndexError("Stack Underflow: Cannot pop from an empty stack.")
        return self._items.pop()

    def peek(self):
        """Looks at the top item without removing it in O(1) time."""
        if self.is_empty():
            return None
        return self._items[-1]

    def is_empty(self):
        return len(self._items) == 0


if __name__ == "__main__":
    undo_history = Stack()
    undo_history.push("Typed 'Hello'")
    undo_history.push("Bolded 'Hello'")
    undo_history.push("Deleted 'o'")

    print("Top action right now:", undo_history.peek())  # Output: Deleted 'o'
    print("Undoing:", undo_history.pop())                # Output: Deleted 'o'
    print("Now at top:", undo_history.peek())            # Output: Bolded 'Hello'

Dry Run

StepOperationStack State (Bottom -> Top)Return Value
1push(5)[5]None
2push(12)[5, 12]None
3peek()[5, 12]12
4pop()[5]12

Speed & Memory

OperationBest CaseAverage CaseWorst CaseWhy?
Push$O(1)$$O(1)$$O(1)$*Appends straight to the top (*amortized for dynamic arrays).
Pop$O(1)$$O(1)$$O(1)$Removes the last element with zero shifting.
Peek$O(1)$$O(1)$$O(1)$Direct lookup of the top slot.

Where You'll See It In Real Life

  • Undo / Redo in Editors: Pressing Ctrl+Z pops the latest edit off your action stack.
  • Compiler Bracket Checking: Code editors verify that every opening bracket has a matching closing partner in exact reverse order.
  • Program Call Stack: Programming languages track active function calls and local variables using an execution stack.

Traps To Avoid

  • Trap 1: Calling pop() without checking is_empty().
    Fix: Always verify the stack isn't empty to avoid runtime underflow errors.
  • Trap 2: Using insert(0, item) and pop(0) on a Python list.
    Fix: Push and pop from the end (append / pop) so operations run in $O(1)$ instead of $O(N)$.
  • Trap 3: Accessing middle elements by index.
    Fix: Respect LIFO boundaries; use an array if you need random middle access.

Practice

  1. Easy: Write a function reverse_string(text) that uses a Stack to reverse a word.
  2. Medium: Write is_valid_brackets(s) to verify balanced parentheses, brackets, and curly braces.
  3. Hard: Design a MinStack class supporting push, pop, top, and get_min all in $O(1)$ time. (Hint: Use a second stack tracking the running minimum!)

TL;DR

  • A Stack follows LIFO (**Last-In, First-Out**): the newest item added is always removed first.
  • push, pop, and peek all run in $O(1)$ constant time.
  • Stacks power Undo features, bracket validators, and function call management.

References Consulted


Covered Log Update

Already covered: [Big-O notation, Arrays, Two Pointers, Strings, Sliding Window, Prefix Sums, Recursion basics, Singly Linked List, Doubly Linked List, Stack]