The Plate Stack
A Stack is a linear data structure that follows the LIFO (Last-In, First-Out) principle. The last item added is the first item removed. Think of a stack of dinner plates: you can only add a plate to the top, and you can only take the top plate off. You cannot access the plate at the bottom without removing everything above it.
Core operations — all O(1):
| Operation | Description |
|---|---|
push(item) |
Add item to the top |
pop() |
Remove and return the top item |
peek() |
Return the top item without removing it |
is_empty() |
Check if the stack has no items |
In Python, a regular list works as a stack: append() is push, pop() is pop, and [-1] is peek.
Real-World Use Cases
- Undo/Redo: Every action is pushed onto a stack. Ctrl+Z pops the last action and reverses it.
- Browser History: Each page visit is pushed. The "Back" button pops the current page.
- Call Stack: When function A calls function B, B's frame is pushed onto the call stack. When B returns, its frame is popped and execution resumes in A. Stack overflow errors occur when this stack grows too deep (infinite recursion).
- Balanced Parentheses: Push every opening bracket; pop when you see a closing bracket and verify they match. If the stack is empty at the end, the expression is balanced.
- Expression Evaluation: Compilers use stacks to evaluate arithmetic expressions and convert between infix, prefix, and postfix notation.
Key Point: Any algorithm that involves "remembering where you came from" to backtrack is a candidate for a stack. Depth-First Search (DFS) on graphs uses a stack (either explicitly or via the call stack through recursion). When you see a problem involving nested structures — parentheses, HTML tags, directory paths — think stack first.