Stacks
A stack is like a pile of plates: you add to the top, you remove from the top. Last In, First Out (LIFO). It's dead simple, but incredibly powerful for problems involving nested structures and matching.
The Core Idea
Push items on, pop items off. The last thing you pushed is the first thing you'll pop. That's it. This simple property makes stacks perfect for tracking "open" things that need to be "closed" in reverse order.
If you need to match things in reverse order (opening and closing brackets, nested function calls), reach for a stack.
The Classic: Valid Parentheses
Given a string of brackets, check if they're properly matched. This is THE stack problem:
def isValid(s):
stack = []
pairs = {')': '(', '}': '{', ']': '['}
for char in s:
if char in pairs:
# Closing bracket
if not stack or stack.pop() != pairs[char]:
return False
else:
# Opening bracket
stack.append(char)
return len(stack) == 0Stack Operations in Python
stack = []
stack.append(x) # Push
stack.pop() # Pop and return top
stack[-1] # Peek at top
len(stack) == 0 # Is empty?When to Use a Stack
- Matching pairs - Brackets, HTML tags, quotes
- Expression evaluation - Calculate "3 + 4 * 2"
- Undo operations - Most recent action first
- DFS traversal - Iterative depth-first search
- Parsing - Nested structures, function calls
In Python, a list works perfectly as a stack. But if you need thread-safety or want to be explicit, check out collections.deque.