Stack

A stack is a way of organizing items so that the most recently added item is the first one you take out—like a stack of plates in a cafeteria. You can only interact with the top of the stack. Two core operations tell the whole story: - push(x): put item x on top (add a plate to the top). - pop(): remove and return the top item (take the top plate). This “Last In, First Out (LIFO)” rule is the defining behavior: if you push A, then B, then C, the pops come out as C, then B, then A. Even though this isn’t a single numeric equation, it acts like a precise law of motion for data: the stack’s state evolves deterministically under push and pop. A common invariant description is: the stack has an ordered list of elements, and only the end (“top”) is accessible. If the stack has size n, then pushing makes the size n+1, and popping (when non-empty) makes it *n$-1$* while returning the last pushed element still inside.

Stacks emerged from the practical need to make early computers translate and evaluate mathematical expressions and to manage nested computations efficiently. In the 1950s, programmers and language designers faced a concrete problem: how do you evaluate expressions like `((a+b)c) - d` or handle nested function calls in a way that is both systematic and fast? The breakthrough was realizing that nesting in expressions and programs naturally matches a LIFO discipline: the last “unfinished” subtask is the next one you must complete. This idea became central to compiler design (parsing and expression evaluation), to procedure calls (what we now call the call stack*), and to structured programming. The stack is one of those concepts that feels obvious in hindsight—yet it was a major step in turning programming languages into something that could be implemented cleanly and reliably on real machines.

Pioneered by: There isn’t a single sole discoverer, but Friedrich L. Bauer and Klaus Samelson are widely credited with introducing and popularizing stack-based methods for expression evaluation and compilation in the late 1950s (notably in work on “sequential formula translation”). The stack concept then became foundational across programming languages and computer architecture.

• Function calls and recursion in most programming languages (the call stack stores return addresses, local variables, and saved states)
• Undo/redo in editors (undo is typically a stack of actions; redo is another stack)
• Browser navigation history (the “Back” behavior is naturally stack-like, often modeled with two stacks)
• Expression evaluation and parsing in compilers/interpreters (e.g., converting infix to postfix and evaluating postfix using a stack)
• Depth-first search (DFS) in graphs/trees (explicit stack replaces recursion for traversal)