Stacks — How the Pattern Works
A stack is a Last-In, First-Out (LIFO) data structure that maintains unresolved elements, open nesting scopes, or monotonically ordered candidates so only the newest active item (stack[-1]) interacts with each incoming token. By preserving the invariant that stack[-1] always holds the innermost open delimiter, most recent surviving neighbor, or nearest unresolved element, a stack eliminates repeated full-input rescans and nested lookahead loops. Because every element or index is pushed onto the stack at most once and popped at most once, multi-pass O(n^2) (or exponential) brute-force algorithms collapse into O(n) amortized time.
- Nested or paired delimiters and hierarchical intervals—such as brackets
()[]{}, call-stackstart/endlogs, ork[text]blocks—where the most recently opened scope must close or pause/resume first. - Cascading adjacent deletions or undo actions—such as removing duplicate pairs, deleting
k-length character runs, or resolving".."in Unix paths—where removing elements exposes new interactions at the join boundary. - Expression parsing with parentheses or operator precedence (
+,-,*,/, boolean!/&/|), where lower-precedence terms or outer scopes wait on the stack while higher-precedence or inner operations resolve immediately. - Nearest greater/smaller element queries, line-of-sight visibility, ramp width maximization, or lexicographically smallest subsequences, where a monotonic stack maintains sorted unresolved candidates.
- Lazy recursive unpacking or LIFO-to-FIFO structural adapters, such as flattening nested lists on demand (
next()/has_next()) or implementing a queue inO(1)amortized time with two stacks.
- Accessing
stack[-1]or callingstack.pop()without guardingif stack:—inputs starting with a closing delimiter')'or navigating".."at root"/"will raiseIndexError. - Forgetting leftover state after the scan terminates, such as unclosed
'('indices still sitting onstackin parenthesis validation/removal or the final accumulatednumat the end ofBasic Calculator/Basic Calculator II. - Using Python floor division
//instead of truncation toward zeroint(a / b)for signed integer division (-3 // 2evaluates to-2, whereasint(-3 / 2)truncates toward zero to-1). - Using strict
<instead of<=(or>instead of>=) in monotonic stackwhileconditions when duplicate values exist, or pushing values instead of indices when index distances (i - j) are needed.
def process_cancellation(seq, cancels):
stack = []
for item in seq:
if stack and cancels(stack[-1], item):
stack.pop()
else:
stack.append(item)
return stackdef evaluate_nested(tokens, init_state, combine, step):
stack, state = [], init_state
for tok in tokens:
if tok == "(":
stack.append(state)
state = init_state
elif tok == ")":
state = combine(stack.pop(), state)
else:
state = step(state, tok)
return statedef next_greater_indices(nums):
res = [-1] * len(nums)
stack = [] # indices with monotonically non-increasing nums[idx]
for i, x in enumerate(nums):
while stack and nums[stack[-1]] < x:
res[stack.pop()] = i
stack.append(i)
return res