Stack

Back to Index

LIFO (Last In, First Out). Used when you need to process things in reverse order, match brackets, or track “pending” work.

Properties

• Push/pop/peek: O(1)
• Python: use a plain list — append() to push, pop() to pop, [-1] to peek

stack = []
stack.append(val)   # push
stack.pop()         # pop (raises IndexError if empty)
stack[-1]           # peek

When to Use a Stack

• Matching/balancing: parentheses, brackets, tags
• Undo operations: track history of states
• DFS iteratively: explicit stack instead of recursion
• Monotonic problems: next greater/smaller element (Monotonic Stack)
• Expression evaluation: infix to postfix, calculator problems

Valid Parentheses Pattern

stack = []
pairs = {')': '(', ']': '[', '}': '{'}
for ch in s:
    if ch in '([{':
        stack.append(ch)
    elif not stack or stack[-1] != pairs[ch]:
        return False
    else:
        stack.pop()
return not stack

Iterative DFS with Stack

stack = [start]
visited = {start}
while stack:
    node = stack.pop()
    for neighbor in graph[node]:
        if neighbor not in visited:
            visited.add(neighbor)
            stack.append(neighbor)

---

Problems Using This Data Structure