Back to Topics
Stack
A stack is a Last-In-First-Out (LIFO) data structure. Elements are pushed onto the top and popped from the top. Stacks are essential for problems involving nested structures, backtracking, and maintaining a running context — such as matching brackets, evaluating expressions, and tracking the next greater element.
Key Ideas
- LIFO: the last element pushed is the first popped
- Push and pop are O(1) — no shifting needed
- Use a stack when you need to 'remember' previous state to process the current element
- Monotonic stack maintains elements in sorted order to efficiently find next/previous greater/smaller
- Call stack in recursion is itself a stack — iterative DFS uses an explicit stack
- Bracket matching: push opening brackets, pop and compare on closing bracket
Complexity
| Operation | Time | Space |
|---|---|---|
| Push | O(1) | O(1) |
| Pop | O(1) | O(1) |
| Peek | O(1) | O(1) |
| Search | O(n) | O(1) |
Common Patterns
Bracket / Delimiter MatchingPush opening chars; on closing char, pop and verify the pair matches.
Monotonic StackMaintain a strictly increasing/decreasing stack to find the next greater/smaller element in O(n).
Iterative DFSReplace recursion with an explicit stack to avoid call-stack overflow on deep graphs/trees.
Expression EvaluationTwo stacks (values and operators) or postfix conversion to evaluate arithmetic expressions.
Code Example
Valid parentheses — bracket matchingpython
def is_valid(s: str) -> bool:
stack: list[str] = []
pairs = {')': '(', ']': '[', '}': '{'}
for ch in s:
if ch in '([{':
stack.append(ch)
elif ch in ')]}':
if not stack or stack[-1] != pairs[ch]:
return False
stack.pop()
return len(stack) == 0💡
Whenever you see 'previous', 'next greater/smaller', or nested structure, think monotonic stack.