Data structures

A stack keeps items like a pile of plates: you put a plate on top and take one from the top, so the newest item leaves first. Each operation takes $O(1)$ time. If the oldest item must leave first, use a queue; if the smallest, use a priority queue.

A queue keeps items like a line at a shop: newcomers join at the back, and the person at the front is served first, so the oldest item leaves first. Each operation takes $O(1)$ time. If the newest item must leave first, use a stack; if the smallest, use a priority queue.

A deque is a queue open at both ends: items can be added and removed at the front and at the back, each in $O(1)$ time, and any item can be read by its position. The name is short for double-ended queue and is said "deck".

A priority queue keeps a set of numbers that changes over time and gives you the smallest (or the largest) of them at any moment, whatever order they came in.

A set keeps different numbers (or words) in sorted order while you add and remove them. It tells you whether a number is there and finds the nearest number above or below a given one, each in O(\log n). A map is a set whose keys each carry a value, such as a number and how many times it occurred.

A map is a set of keys where each key carries a value with it, such as a number and how many times it occurred. The keys are kept sorted and found in O(\log n), exactly as in a set; the set page shows how.

A monotonic stack finds, for every element of an array, the nearest greater (or smaller) element to its right or left, in $O(n)$ for the whole array. It is a stack of positions whose values stay sorted, and it also finds the largest rectangle in a histogram. If you need the minimum of every window of fixed length, use a monotonic queue instead.

A monotonic queue finds the minimum (or maximum) of every window of $k$ consecutive elements of an array in $O(n)$ for the whole array. It is a deque of positions whose values increase from front to back. If you need window sums, use prefix sums; if the ranges come as arbitrary queries, use a sparse table.

A disjoint set union (DSU) keeps elements split into groups (disjoint sets) that merge over time, and tells quickly whether two elements are in the same group. If the groups never change, one search finds them all, as in connected components.

A trie (prefix tree) stores a set of words so that words with the same beginning share one path. It answers "is this word here?" and "how many words start with these letters?" in time proportional to the length of the word. If you only need to find whole words, a set of strings (or a map to count copies) is simpler.

A sparse table answers a range-minimum query, "what is the smallest element between positions l and r?", in constant time, for an array that doesn't change. Building it takes O(n \log n) time and memory, and the same works for the maximum. If the array changes between queries, use a segment tree instead.

A Fenwick tree, also called a binary indexed tree, keeps the sums of an array that changes: it adds a number to one element and answers "what is the sum of elements $l$ to $r$?" in O(\log n) time each. For the minimum or maximum of a changing array, use a segment tree.

A segment tree answers queries about a range of an array, such as "what is the smallest element between positions $l$ and $r$?", while elements of the array change: both a query and an update take O(\log n) time. For sums only, a Fenwick tree is shorter; for an array that never changes, a sparse table answers the minimum in $O(1)$.