= Stack
{disambiguate=data structure}
{wiki=Stack_(abstract_data_type)}
= Stack
{synonym}
= LIFO stack
{c}
{synonym}
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. https://raw.githubusercontent.com/kevin-wayne/algs4/master/src/main/java/edu/princeton/cs/algs4/Stack.java[Sedgewick and Wayne, Algorithms: Stack interface and implementation]{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>.
Back to article page
