Stack Fundamentals & Building a Stack Class

This is the first real data structure of the tier, and it is deliberately the simplest one: a stack. Every structure built across the rest of this tier follows the same underlying idea - constrain how data can be accessed, and in exchange get useful guarantees plus O(1) operations, instead of a general-purpose but unconstrained Python list.

A stack only ever exposes one end for both adding and removing items - think of a stack of plates, where the last plate placed on top is the first one taken back off. That single rule, last in first out, is the entire definition of a stack, and it turns out to model an enormous number of real problems.

• -Undo/redo history in an editor - the most recent change is always the first one undone.
• -The call stack every function call already uses, even though it is managed automatically - a function only returns after everything it called has finished, in reverse order of being called.
• -Depth-first search and backtracking, covered fully in a later tier, both explore "go as deep as possible, then back up," which is exactly a stack's access pattern.
• -Matching balanced brackets or parentheses, and evaluating expressions - both classic stack exercises.

Notice both push and pop operate on the END of the underlying list, using append and pop with no index argument - and both of those are O(1) operations on a Python list, since the list already tracks free capacity at its end and never has to shift any other element to make room or close a gap. That single design choice - always working at the same end - is what makes a Python list a perfect backing store for a stack.