A stack is a collection in which elements are added and removed at one end only, so the last item put in is the first taken out. This last-in-first-out, or LIFO, discipline is captured by two operations: push, which places an element on top, and pop, which removes and returns the top element. The image is a stack of plates: you add to the top and remove from the top, never reaching into the middle. Knuth treats stacks among the fundamental structures in Volume 1, “Fundamental Algorithms” (Knuth’s pages at Stanford, verified 2026-06-08).
The most important use of a stack is hidden inside almost every running program: the call stack. When a function calls another function, the machine pushes a record of where to return and the local data of the caller; when the called function finishes, that record is popped and execution resumes where it left off. Because calls finish in the reverse order they were made, the LIFO discipline of a stack matches exactly, and it is what makes nested and recursive function calls work.
Stacks underlie several other classic tasks. Evaluating arithmetic expressions, especially converting between infix and postfix forms or processing them directly, relies on pushing operands and operators and popping them in order. The undo feature of an editor is a stack of past states, popped one at a time to step backward. Depth-first traversal of a graph or tree is naturally expressed with a stack, whether an explicit one or the implicit call stack of a recursive procedure.
A stack can be implemented on either of the linear structures. A dynamic array gives push and pop at its end in amortized constant time, while a linked list gives the same operations by inserting and removing at the front. Either way the two operations are O(1), which is the property the stack abstraction promises regardless of how it is built underneath.