Stacks

What we're doing: Push three values, peek the top, then pop them off in LIFO order.

stack = []
stack.append(10)
stack.append(20)
stack.append(30)

print(stack[-1])
print(stack.pop())
print(stack.pop())
print(stack)

5

stack[-1] reads the top (30) without removing it — the stack is unchanged after this line.

6

pop() removes and returns 30, the most recently pushed value.

7

pop() again removes 20 — the next-most-recent push, now that 30 is gone.

30
30
20
[10]

Why this works: 30 was pushed last, so it is both the peeked top and the first value popped. After two pops, only the first-pushed value, 10, remains.

What we're doing: Check whether a string of brackets is balanced, using a stack to track what is still open.

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


print(is_valid("{[()]}"))
print(is_valid("{[(])}"))

5

ch is a closing bracket — it must match whatever the stack currently has on top.

6

not stack catches "nothing open to close"; stack.pop() != pairs[ch] catches "closes the wrong thing" — either one means not balanced.

True
False

Why this works: "{[()]}" closes every bracket in the exact reverse order it opened them, so the stack ends empty. "{[(])}" closes "(" with "]" — a mismatch caught the moment ] is compared against the top of the stack.

What we're doing: For each number, find the next greater number to its right (or -1 if none exists), using a decreasing stack of indices.

def next_greater_elements(nums):
    result = [-1] * len(nums)
    stack = []
    for i, n in enumerate(nums):
        while stack and nums[stack[-1]] < n:
            result[stack.pop()] = n
        stack.append(i)
    return result


print(next_greater_elements([2, 1, 2, 4, 3]))

4

While the current value n is bigger than the value at the index on top of the stack, that index has found its answer.

5

result[stack.pop()] = n records n as the next greater element for the popped index, then discards that index — it no longer needs tracking.

[4, 2, 4, -1, -1]

Why this works: For 2 (index 0) the next greater value is 4 (index 3). For 1 (index 1) it is 2 (index 2). For 2 (index 2) it is 4 (index 3). 4 (index 3) and 3 (index 4) have nothing greater to their right, so both stay -1.

What we're doing: Evaluate a postfix expression using a stack.

def eval_postfix(tokens):
    stack = []
    ops = {
        '+': lambda a, b: a + b,
        '-': lambda a, b: a - b,
        '*': lambda a, b: a * b,
        '/': lambda a, b: int(a / b),
    }
    for tok in tokens:
        if tok in ops:
            b = stack.pop()
            a = stack.pop()
            stack.append(ops[tok](a, b))
        else:
            stack.append(int(tok))
    return stack.pop()


print(eval_postfix(["3", "4", "+", "2", "*"]))

10

b is popped first — it is the operand closer to the operator, i.e. the SECOND one in the original expression.

11

a is popped second — the operand further from the operator, i.e. the FIRST one.

12

a OP b, in that order, matters for non-commutative operators like - and /.

14

Why this works: Postfix "3 4 + 2 *" means (3 + 4) then multiply by 2: push 3, push 4, + combines them into 7, push 2, * combines 7 and 2 into 14 — the exact order a stack naturally processes them in.

What we're doing: Traverse a tree depth-first using an explicit stack instead of recursive calls.

def dfs_iterative(root):
    if root is None:
        return []
    visited = []
    stack = [root]
    while stack:
        node = stack.pop()
        visited.append(node['value'])
        for child in reversed(node['children']):
            stack.append(child)
    return visited


tree = {
    'value': 1,
    'children': [
        {'value': 2, 'children': []},
        {'value': 3, 'children': [{'value': 4, 'children': []}]},
    ],
}
print(dfs_iterative(tree))

7

node is the most recently pushed item — exactly what a recursive call would be visiting right now.

9

reversed(...) pushes the LAST child first, so the FIRST child ends up on top and gets visited next.

[1, 2, 3, 4]

Why this works: Pushing children in reverse order means the first child ends up on top of the stack and gets popped next — reproducing the same left-to-right visiting order recursion would give, just driven by an explicit stack instead of the call stack.

What we're doing: Push a sequence of values onto a min-stack and read the current minimum in O(1) at each step, including after popping the minimum off.

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val):
        self.stack.append(val)
        current_min = val if not self.min_stack else min(val, self.min_stack[-1])
        self.min_stack.append(current_min)

    def pop(self):
        self.stack.pop()
        self.min_stack.pop()

    def get_min(self):
        return self.min_stack[-1]


ms = MinStack()
ms.push(5)
ms.push(2)
ms.push(7)
print(ms.get_min())
ms.pop()
print(ms.get_min())
ms.pop()
print(ms.get_min())

8

current_min is the smaller of the new value and whatever the min-stack currently reports — never a full rescan of self.stack.

9

min_stack grows by exactly one entry on every push, in lockstep with the main stack.

2
2
5

Why this works: After pushing 5, 2, 7 the minimum is 2. Popping 7 leaves [5, 2] — the minimum is still 2, since 2 is still in the stack. Popping again leaves only [5], and get_min() correctly reports 5 — the discarded minimum (2) never lingers, because its min_stack entry was popped at the exact same moment.