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), and that's what makes stacks so useful.
Implementation#
Interactive Lab#
Let's take the example of this visualization: a stack already holding 10, 20, 30, with 30 sitting on top. Press play and watch the pop. 30 is the one that leaves, even though it arrived last, and top drops to 20. Nothing below the top is touched or shifted, which is exactly why every operation in the table above is O(1).
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, and 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 idea: 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)
What to Remember#
Stacks are 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.