Stack Applications

Jr Codex DSA Notes

Level: Intermediate Prerequisites: Chapter 1 Time to complete: ~25 minutes

Recognizing a Stack Problem
Balanced Parentheses
Evaluating a Postfix Expression
Min Stack — O(1) Minimum Retrieval
Summary & Next Steps

1. Recognizing a Stack Problem

Stacks show up whenever a problem needs to match the most recent unmatched thing — the most recent open bracket, the most recent unresolved operation, the most recent state you might need to undo. Whenever you catch yourself thinking "I need to remember what came just before this, and discard it once it's resolved," that's a stack.

2. Balanced Parentheses

Determine whether every opening bracket in a string has a matching, correctly-ordered closing bracket.

def is_balanced(s):
    stack = []
    pairs = {")": "(", "]": "[", "}": "{"}
 
    for char in s:
        if char in "([{":
            stack.append(char)                    # push an opening bracket
        elif char in ")]}":
            if not stack or stack.pop() != pairs[char]:
                return False                        # mismatched or nothing to match
    return len(stack) == 0                          # every opener must be matched
 
print(is_balanced("({[]})"))   # True
print(is_balanced("({[}])"))   # False — [ closed by } out of order
print(is_balanced("((("))       # False — unmatched openers remain

Every closing bracket must match the most recently opened, still-unmatched bracket — exactly the LIFO behavior from Chapter 1. Time complexity: O(n), one pass; space: O(n) worst case (an all-openers string).

3. Evaluating a Postfix Expression

Postfix (Reverse Polish) notation places operators after their operands (3 4 + instead of 3 + 4), which avoids the need for parentheses or operator-precedence rules entirely — and is naturally evaluated with a stack.

def evaluate_postfix(tokens):
    stack = []
    operators = {
        "+": lambda a, b: a + b,
        "-": lambda a, b: a - b,
        "*": lambda a, b: a * b,
        "/": lambda a, b: a / b,
    }
 
    for token in tokens:
        if token in operators:
            b = stack.pop()               # second operand was pushed most recently
            a = stack.pop()
            stack.append(operators[token](a, b))
        else:
            stack.append(int(token))
 
    return stack.pop()
 
print(evaluate_postfix(["3", "4", "+", "2", "*"]))   # (3 + 4) * 2 = 14

Numbers get pushed as they're seen; an operator pops the two most recent numbers, applies itself, and pushes the result back — ready to be used by a later operator. Note the order: b is popped before a, since b (the second operand) was pushed after a.

4. Min Stack — O(1) Minimum Retrieval

Design a stack that supports push, pop, and get_min — all in O(1). The naive approach (min(stack) on demand) is O(n) per call; the fix is to track the running minimum alongside every push using a second stack.

class MinStack:
    def __init__(self):
        self._stack = []
        self._min_stack = []       # _min_stack[i] = the min of _stack[0..i]
 
    def push(self, value):
        self._stack.append(value)
        current_min = min(value, self._min_stack[-1]) if self._min_stack else value
        self._min_stack.append(current_min)
 
    def pop(self):
        self._min_stack.pop()
        return self._stack.pop()
 
    def get_min(self):
        return self._min_stack[-1]
 
s = MinStack()
s.push(5)
s.push(2)
s.push(7)
print(s.get_min())   # 2
s.pop()               # removes 7
print(s.get_min())   # 2 — unaffected, 7 was never the min
s.pop()               # removes 2
print(s.get_min())   # 5 — correctly falls back once 2 is gone

The _min_stack mirrors every push/pop of the main stack one-for-one, always holding "the minimum as of this point," so popping the main stack automatically restores the correct previous minimum without recomputing anything. This is a direct application of the time-space tradeoff from Module 1 Chapter 4: O(n) extra space buys O(1) minimum retrieval instead of O(n).

5. Summary & Next Steps

Key Takeaways

Stacks solve "match against the most recent unresolved thing" problems — balanced brackets, postfix evaluation, undo functionality.
Postfix evaluation never needs precedence rules or parentheses because the operator always applies to exactly the two most recently pushed operands.
Min Stack trades O(n) space (a parallel stack) for O(1) minimum retrieval — the time-space tradeoff from Module 1 in concrete form.

Concept Check

What property of stacks makes them the right fit for checking balanced parentheses?
In evaluate_postfix, why is b = stack.pop() executed before a = stack.pop(), rather than the reverse?
Why does MinStack.get_min() stay correct after a pop(), without ever rescanning the remaining elements?

Next Chapter

→ Chapter 3: Queue & Circular Queue

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index