Stacks

Last in, first out

A stack is a collection where you add and remove items at the same end, called the top. The last item pushed is the first one popped: last in, first out, or LIFO. You cannot reach an item in the middle without first removing everything above it.

Operations and their cost

A Python list works as a stack because append and pop work at the end, where nothing has to shift. pop() on an empty list raises IndexError: pop from empty list, and stack[-1] on an empty list raises IndexError too, so check if stack: first. In JavaScript use an array with push and pop, and arr[arr.length - 1] to peek.

Every running program also has a stack: the call stack remembers which function called which, and each recursive call pushes a new frame. You will lean on that in Module 5.

Valid brackets

A string of brackets is valid when every opening bracket is closed by the same kind of bracket, in the right order: "([]{})" is valid, "([)]" is not. The most recent unclosed bracket must be closed first, which is exactly LIFO. Push every opening bracket. On a closing bracket, the top of the stack must be its partner, so pop and compare. At the end the stack must be empty, or some bracket was never closed. O(n) time, and O(n) space in the worst case, such as "((((".

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

print(is_valid("{[()]}"), is_valid("([)]"), is_valid("(("))   # Output: True False False

Postfix (Reverse Polish) expressions

We usually write 3 + 4 × 2 with the operator between the numbers (infix), which needs precedence rules and brackets. In postfix, also called Reverse Polish Notation (RPN), each operator comes after its two operands: "3 4 2 * +" means 3 + (4 × 2) = 11. No brackets or precedence rules are needed, and a stack evaluates it in one pass: push numbers; on an operator, pop two numbers, apply the operator, and push the result.

Order matters for − and ÷: the FIRST pop is the right operand. For "8 3 -", pop 3 (call it b), then 8 (a), and compute a − b = 5, not 3 − 8.

Division that truncates toward zero

Many problems say integer division "truncates toward zero", as in C, C++ and Java: 7 ÷ 2 = 3 and −7 ÷ 2 = −3. Python's // rounds DOWN (toward minus infinity), so −7 // 2 is −4. int(a / b) truncates, but it goes through a float, which can lose precision for very large numbers. A safe integer way is to divide the absolute values and put the sign back.

print(-7 // 2)        # Output: -4  (floor: rounds down)
print(int(-7 / 2))    # Output: -3  (toward zero, via a float)

def div_trunc(a, b):
    q = abs(a) // abs(b)
    return -q if (a < 0) != (b < 0) else q

print(div_trunc(-7, 2), div_trunc(7, -2), div_trunc(-7, -2))   # Output: -3 -3 3

Min-stack: the minimum in O(1)

A min-stack supports push, pop, top and get_min, all in O(1). Calling min(stack) would be O(n). The trick: store next to each value the minimum of the stack at the moment it was pushed. The top pair always knows the current minimum, and popping brings back the older minimum automatically. It costs O(n) extra space.

stack = []                        # pairs (value, minimum so far)
for x in [5, 3, 7, 3]:
    low = min(x, stack[-1][1]) if stack else x
    stack.append((x, low))
print(stack)          # Output: [(5, 5), (3, 3), (7, 3), (3, 3)]
stack.pop()
stack.pop()
print(stack[-1][1])   # Output: 3
stack.pop()
print(stack[-1][1])   # Output: 5

Common mistakes

• Popping or peeking an empty stack (IndexError). Fix: check if stack: first and decide what to return.
• In the bracket check, forgetting the final "is the stack empty?" test, so "((" passes. Fix: return not stack.
• Swapping operands in RPN and computing b − a. Fix: the first pop is the RIGHT operand.
• Using // when the task says "truncate toward zero". Fix: divide absolute values and fix the sign.
• Using insert(0, x) and pop(0) as the stack top: both are O(n). Fix: push and pop at the end.
• A min-stack that calls min() on every get_min. Fix: store the running minimum with each item.