What Is a Stack?#
A stack is a Last-In, First-Out (LIFO) data structure. The last element you push in is the first one you get out — like a stack of plates: you always take from the top.
Core Operations#
| Operation | Description | Time |
|---|---|---|
push(item) | Add item to the top | O(1) |
pop() | Remove and return top | O(1) |
peek() | View top without removing | O(1) |
is_empty() | Check if stack has items | O(1) |
All core operations are O(1) — that's what makes stacks powerful.
Implementation#
Interactive Lab#
Watch items get pushed onto and popped off the stack in real time.
The Call Stack#
Your programming language uses a stack under the hood for function calls. Every function call pushes a frame; every return pops it. Recursive functions push many frames — too many causes a "stack overflow".
Classic Problem: Balanced Brackets#
Stacks are perfect for checking whether brackets are matched. The code above includes a full solution — the key insight: push every opening bracket; when you see a closing bracket, pop and verify it matches.
Key Applications#
- Function call stack (all languages, always running)
- Balanced parentheses / bracket matching
- Undo operations in editors (each action is a push)
- Browser back button (page history)
- Depth-First Search (iterative version uses a stack)
- Expression evaluation — converting infix to postfix (shunting-yard)
Key Takeaway#
Stacks are beautifully simple — four operations, all O(1). Whenever you see a problem involving "most recent", "last seen", or "reverse order", a stack is likely the right tool. They're the backbone of recursion, parsing, and state management.