Stack
DSA · Stacks and Queues
Theory
A stack is a Last-In-First-Out (LIFO) collection: the last item pushed is the first one popped, like a pile of plates. It supports push (add to top), pop (remove from top) and peek (look at the top), all in O(1). In Python a list works as a stack using append() and pop(). The function call stack that runs your programs is itself a stack.
Why we use it
Stacks naturally handle anything that must be undone or matched in reverse order.
When to use it
Use a stack for undo/redo, matching brackets, evaluating expressions, browser back navigation, DFS, and backtracking.
How it works
- Empty stack
- Push? Yes: Add item on top. No: Pop: remove the top item.
- Stack empty when popping? Yes: Underflow error. No: Return the popped item.
- LIFO: last in, first out
Syntax
stack = []
stack.append(x) # push O(1)
stack.pop() # pop O(1)
stack[-1] # peek O(1)
not stack # is emptyExample
def is_balanced(expr):
pairs = {")": "(", "]": "[", "}": "{"}
stack = []
for ch in expr:
if ch in "([{":
stack.append(ch)
elif ch in pairs:
if not stack or stack.pop() != pairs[ch]:
return False
return len(stack) == 0
for e in ["(a+b)*[c-d]", "{[}]", "((x)"]:
print(e, "balanced:", is_balanced(e))
undo = []
for action in ["type A", "type B", "bold"]:
undo.append(action)
print("Undo last:", undo.pop(), "| remaining:", undo)Key points
- LIFO: last in, first out
- push, pop and peek are O(1)
- Python list append/pop works as a stack
- Used for undo, brackets and DFS