stack

A stack is a linear data structure that stores a collection of elements with last-in, first-out order. The most recently added element is the first to be removed. Common operations are push (add an element to the top), pop (remove and return the top element), peek (or top) to view the top without removing, and isEmpty or size queries. The top of the stack is conceptually the most accessible end.

Stacks can be implemented using arrays or linked lists. An array-based stack uses a contiguous block with a top index; it may require dynamic resizing to accommodate growth. A linked-list stack uses nodes where each node stores a value and a link to the previous node. Push and pop are typically constant time, O(1), while access to arbitrary elements is not provided. Some languages provide built-in stack types or abstractions.

Common uses include function call management in programming languages (the call stack holds return addresses and local variables), evaluating arithmetic expressions, backtracking algorithms, undo mechanisms, and parsing or recognizing languages with pushdown automata. In automata theory, a pushdown automaton uses a stack to store symbols as it reads input, enabling recognition of context-free languages. Memory considerations include potential stack overflow from excessive recursion or deep nesting, and underflow if a pop is attempted on an empty stack.

Related topics include queues (which follow first-in, first-out order) as an alternative data structure and the distinction between the program call stack and the data structure stack. Security concerns in lower-level languages include stack-based buffer overflows and exploitation through stack manipulation. Many modern languages optimize or remove explicit stack usage via tail-call optimization or heap-allocated frames.