Stacks

Last-in, first-out, the structure behind function calls, undo buttons, and expression parsing

A stack is a LIFO (Last In, First Out) data structure. Think of a stack of plates, you add to the top and remove from the top.
Core operations (all O(1)):

push(x), add to top

pop(), remove from top

peek(), view top without removing

is_empty(), check if empty

📞In the Real World...

Every function call in Python creates a "stack frame" on the call stack. When the function returns, the frame is popped. That's why infinite recursion causes a "stack overflow", you've pushed too many frames.

Classic stack problem: valid parenthesespython

def is_valid_parens(s):
    """Check if brackets are correctly matched and nested."""
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}

    for char in s:
        if char in '([{':
            stack.append(char)      # Push opening bracket
        elif char in ')]}':
            if not stack or stack[-1] != pairs[char]:
                return False        # Mismatch or empty stack
            stack.pop()             # Pop matching bracket

    return len(stack) == 0          # Stack must be empty at end

print(is_valid_parens("({[]})"))   # → True
print(is_valid_parens("([)]"))     # → False

🤔Quick Check

Why is a stack (not a queue) used for matching parentheses?

Practice Exercises

0/1 solved

Exercise 1 of 1medium

⏱ 00:00

Evaluate Reverse Polish Notation

Evaluate an expression in Reverse Polish Notation (postfix). Numbers go on the stack; operators pop two numbers, compute, push result.
["2","1","+","3","*"] = ((2+1)*3) = 9
Expected output: 9

solution.py

1 / 1

Solve all 1 exercise to unlock completion

Previous Next