Last-In, First-Out Matching

Foundations

In Arrays & Strings, any index was one O(1) read away. A stack gives that up: it is a list you touch only at one end, called the top. Push adds an element on top; pop removes the top element and returns it. In Python, append and pop do exactly that in O(1), because the top is the list's last slot, stack[-1]. The rule is last in, first out: a pop always returns the newest element still inside.

Last in, first out is the shape of nested work. When one task starts inside another, the inner one must finish first, as when a function f calls g, and g returns before f can. Push each task as it starts and pop it as it ends, and whatever ends next is always the task on top, so nothing below it ever needs a search.

Push the elements of nums = [7, 1, 5, 3, 6] from index 0 onward, and the stack fills bottom to top: after three pushes it holds 7, 1, and 5, with 5 on top. A pop now returns 5, the newest, while 7, pushed first, stays at the bottom. Push everything and pop until empty, and the values come out as 6, 3, 5, 1, 7, the reverse of the order they went in.

Case Scenario

Valid Parentheses applies that rule to brackets in a string, indexed from 0. Each opening bracket starts unfinished work, so it is pushed; each closing bracket must finish the most recent unfinished one, so it pops the top and checks that the two match. In s = "([]{})", "]" closes "[" while "(" waits underneath, and the string is valid because the stack ends empty.

The direct approach deletes matched pairs: remove every "()", "[]", and "{}", then repeat until nothing changes. A valid string shrinks to empty, but each round rescans the whole string, and deep nesting such as "((((()))))" needs about n/2 rounds, O(n²) in all. Every round also rereads brackets that the round before already passed over.