Definition
A stack is a last-in-first-out (LIFO) data structure supporting two operations: push (add an item to the top) and pop (remove the most recently added item). Stacks are used to track suspended contexts during recursive computation, to evaluate expressions with nested parentheses, and to implement function calls in most programming languages.
Why it matters
How it works
Implement a stack as an array or linked list with two operations. Push: add an element to the top (stack[++top] = x for an array; head = new Node(x, head) for a list). Pop: remove and return the top element. Variants include double-ended (deque), priority stacks (heaps), and persistent stacks (functional). Most CPUs have a hardware stack register and dedicated push/pop instructions.