LIFO Semantics (Stack Discipline)¶

Last-in-first-out ordering naturally models nested contexts, recursive descent, and reversible operations - any situation where the most recent item must be resolved before returning to earlier items.

Tension Addressed¶

Simplicity vs. Capability

Recognizable As¶

Call stacks; undo systems; expression parsing; depth-first traversal; backtracking algorithms; browser history; any "go back" operation

Canonical Sources¶

Dijkstra, "Recursive Programming" (1960); Knuth, TAOCP Vol. 1, Section 2.2.1 (1968)

Transfers To¶

Language Implementation (call frames), User Interface (undo/redo), Parsing (expression evaluation), Graph Algorithms (DFS)

The stack is one of the most powerful abstractions in computing - its simplicity (two operations: push and pop) belies its ubiquitous applicability.