Stacks

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

Picture a stack of plates. You put a clean plate on the top. When you need one, you take it off the top. You never pull a plate from the middle of the pile, that would be silly.
A stack works exactly like that pile. The last thing you put on is the first thing you take off. People call that rule LIFO, last in, first out, but the pile of plates is all you need to remember.
Try both a stack and a queue below, then come back for the four little commands.

A stack has just four moves, and they are all quick:

push(x), put something on the top

pop(), take the top thing off

peek(), look at the top without taking it

is_empty(), is there anything left?

📞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