Stack (data structure)

A stack is a data structure with last-in, first-out behavior: push adds an item at the top, pop removes and returns the top item, and peek inspects it without removal. Push $A,B,C$: successive removals return $C,B,A$. Inspection and removal require a nonempty stack, or a specified empty-case result. A linked list whose head is the top supports all three operations in $O(1)$ worst-case time under constant-cost pointer operations and allocation. The stack interface itself does not fix these costs. ^[ref]

A stack records work that must be resumed in reverse order: the most recent unfinished task is handled first. Depth-first search uses this discipline to finish a newly entered branch before resuming the older branch that led to it. Breadth-first search uses a FIFO queue to resume the oldest pending vertex instead. Both are small interfaces whose removal rule changes the shape of a graph search.