Stack
LIFO data structure powering DFS, undo operations, and bracket matching
Free tier: read the explanation here. Upgrade to Pro for Drills, Speed challenges & Mastery badges.
UpgradeKnowledge Debt detected
You can study this freely — but your score may plateau if these foundations have gaps. The Mastery badge requires them to be solid.
Explanation
A is a Last-In, First-Out (LIFO) structure — the last element you add is the first one you get back. Think of a stack of plates: you always add and remove from the top.
Core operations — all O(1):
| Operation | Python | What it does | |---|---|---| | Push | stack.append(x) | Add to top | | Pop | stack.pop() | Remove + return top | | Peek | stack[-1] | Read top without removing | | Is empty | len(stack) == 0 | Check if empty |
Python uses a plain list as a stack. No need to import anything — append() is push, pop() is pop.
stack = []
stack.append(1) # push 1 → [1]
stack.append(2) # push 2 → [1, 2]
stack.append(3) # push 3 → [1, 2, 3]
top = stack[-1] # peek → 3 (stack unchanged)
val = stack.pop() # pop → 3 (stack becomes [1, 2])
val = stack.pop() # pop → 2 (stack becomes [1])When to reach for a stack:
- DFS traversal — the call stack in recursive DFS *is* a stack; iterative DFS uses one explicitly
- Bracket/parenthesis matching — push on open, pop and check on close
- Undo/redo — push actions, pop to undo
- "Next greater element" — monotonic stack pattern
Bracket matching — the classic stack problem:
python def is_valid(s: str) -> bool: stack = [] pairs = {')': '(', '}': '{', ']': '['} for ch in s: if ch in '({[': stack.append(ch) # push open bracket elif ch in ')}]': if not stack or stack[-1] != pairs[ch]: return False # mismatch or empty stack.pop() # matched — pop return len(stack) == 0 # must be fully matched is_valid("()[]{}") # True is_valid("([)]") # False — wrong order is_valid("{[]}") # True
Iterative DFS using a stack (see also: {href=/atoms/algo-dfs}): ``python def dfs_iterative(graph, start): stack = [start] visited = set([start]) while stack: node = stack.pop() # LIFO — last pushed = first explored for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) stack.append(neighbor)
Space complexity: O(n) where n is the number of elements stored. Each element takes O(1) space.
Examples
Monotonic stack — Next Greater Element
Keep a stack of indices whose "next greater" answer is still unknown. When a larger element arrives, it is the answer for everything smaller on the stack.
def next_greater(nums):
"""For each element, find the next larger value to its right."""
result = [-1] * len(nums)
stack = [] # stores indices of elements waiting for their answer
for i, num in enumerate(nums):
# Pop everything smaller than current — current is their answer
while stack and nums[stack[-1]] < num:
idx = stack.pop()
result[idx] = num
stack.append(i)
return result
# [2, 1, 2, 4, 3] → [4, 2, 4, -1, -1]
# [4, 4, 4] → [-1, -1, -1] (no element larger to the right)Evaluate Reverse Polish Notation
RPN eliminates parentheses: push operands, pop two when you see an operator, push the result.
def evaluate(tokens):
"""Evaluate a Reverse Polish Notation expression."""
stack = []
ops = {'+', '-', '*', '/'}
for token in tokens:
if token not in ops:
stack.append(int(token))
else:
b, a = stack.pop(), stack.pop() # order matters for - and /
if token == '+': stack.append(a + b)
elif token == '-': stack.append(a - b)
elif token == '*': stack.append(a * b)
elif token == '/': stack.append(int(a / b)) # truncate toward zero
return stack[0]
# evaluate(["2","1","+","3","*"]) → 9 (because (2+1)*3=9)How well did you understand this?
Practice Problems
Next in Algorithms & Data Structures
Queue