Stack

Also known as: LIFO

A stack is a LIFO (last-in, first-out) collection: push, pop, and usually peek on one end. Implement with an array or linked list.

Call stacks for recursion, undo buffers, and the explicit stack in iterative DFS are the usual appearances. Parenthesis matching and expression evaluation are standard exercises.

All core operations are $O(1)$ time for a well-implemented stack.

← Back to CS Glossary