Stacks

Stacks are an abstract data type that stores a collection of elements with last-in, first-out order. The most recently added item is the first to be removed. Stacks support operations such as push (add an element), pop (remove and return the top element), peek or top (return the top element without removing it), is_empty, and size. They are typically used when you need to access data in reverse order of insertion, and they can be bounded (with a maximum capacity) or unbounded in size; bounded stacks may overflow when full.

Implementation: Stacks can be built on arrays (often dynamic arrays that resize) or on linked lists. Array-based stacks offer O(1) amortized time for push and pop, with possible O(n) resizing cost during growth. Linked-list stacks provide O(1) time for push and pop and can grow without relocation but require extra node allocations.

Common uses: function call stacks in programming languages manage active subroutines and local variables; expression evaluation in calculators; parsing and syntax checking; backtracking; undo mechanisms in editors; depth-first search in graphs.

Complexities: push, pop, and peek are typically O(1) time, and space usage is proportional to the number of elements stored. The precise space overhead depends on implementation; array-based stacks store elements contiguously, while linked lists store nodes with pointers.

Variants: specialized stacks include the monotonic stack used in certain algorithms, and concurrent stacks for multi-threaded contexts, which require synchronization.