Stacks

Last in, first out. You only touch the top. The restriction is the feature.

Three operations, all O(1)

• push — add to the top
• pop — remove the top (errors on empty)
• peek — read the top
• No searching, no shifting, no random access

Watch it match brackets

Push opens, pop on close, balanced iff the stack ends empty.

Scratch vs library

All O(1) per op. Our Stack ≈1.7× the list — it just wraps list.append.

Where you meet it

• Undo/redo, browser back button
• Expression parsing, bracket matching
• Depth-first search
• The call stack — every program you run

Takeaway

LIFO in one structure. Cheap, and exactly the ordering that "newest first, then unwind" work needs. Next: the mirror image — queues (FIFO).