Lesson 3 of 14

Stacks and Undo

When you undo edits, the most recent action is reversed first. A stack removes the most recently added item first. This is LIFO: Last In, First Out.

Add and remove at one end

• push: Put an item on top.
• pop: Remove the top item.
• peek: Inspect the top item without removing it.

After add A → add B → add C → remove once, the removed item is C. From bottom to top, A, B remain. Python lists support this through append() and pop(). Popping an empty list raises an error, so check first.

Matching parentheses

In a nested expression such as (()()), the most recently opened parenthesis must close first. A stack fits this rule. This example checks round parentheses and ignores other characters.

def balanced(text):
    stack = []
    for char in text:
        if char == "(":
            stack.append(char)
        elif char == ")":
            if not stack:
                return False
            stack.pop()
    return not stack

print(balanced("(()())"))
print(balanced(")("))

The first result is True; the second is False. The string )( has equal numbers of opening and closing parentheses, but their order is wrong. When a closing parenthesis arrives, its matching opening parenthesis must already be on the stack.

Each character is inspected once, giving O(n) time. If all parentheses open, they all remain stored, giving O(n) worst-case extra space.

Function calls also stack up

When one function calls another, it must remember where execution should return. The most recent call returns first. Recursion from lesson 1 uses this call stack too. Deeper recursion means more calls to remember.

Check your understanding

Add 1 and 2 to an empty stack, then remove one item. Add 3 and remove twice. What comes out?