Three containers that aren't really containers — they wrap one and expose a restricted interface that enforces a discipline: last-in-first-out, first-in-first-out, or always-largest-first.
🎯 Match the data structure to the algorithm's disciplineA container adaptor doesn't store anything new — it wraps an existing container and hides most of its interface, leaving only the operations that enforce one discipline: stack = LIFO, queue = FIFO, priority_queue = highest-priority-first (a heap).
Under the hood, a stack<int> is just a deque<int> (by default) with a smaller door. By exposing only push/pop/top, it makes the LIFO rule impossible to violate. The restriction is the feature — it makes your intent obvious and your code harder to misuse.
stack<int, std::vector<int>>) but rarely need to.Source: cppreference — Container adaptors.
A pile of plates: you add and remove from the same end (the top). Natural fit for undo histories, depth-first search, and matching brackets.
#include <stack> std::stack<int> s; s.push(1); s.push(2); s.push(3); // bottom -> [1, 2, 3] <- top s.top(); // 3 — peek at the top (does NOT remove) s.pop(); // removes 3, returns nothing (void!) s.top(); // 2 s.size(); // 2 s.empty(); // false
-std=c++17+).pop() returns nothing
For all three adaptors, pop() returns void. To use the element you're removing, read it first: auto x = s.top(); s.pop();. And there's no iteration and no peeking inside — that's the point of the restriction.A line at a counter: you add at the back, remove from the front. The backbone of breadth-first search and producer/consumer task queues.
#include <queue> std::queue<std::string> jobs; jobs.push("a"); jobs.push("b"); // front -> [a, b] <- back jobs.front(); // "a" — next to be served jobs.back(); // "b" — most recently added jobs.pop(); // removes "a" (the front) jobs.front(); // "b"
stack adds and removes at the same end (LIFO). queue adds at one end, removes at the other (FIFO). DFS uses a stack; BFS uses a queue.Not insertion order at all — every pop gives you the greatest element remaining. It's a binary heap inside: push and pop are O(log n), top is O(1). Powers Dijkstra's algorithm, scheduling, and "top-K" problems.
#include <queue> #include <vector> std::priority_queue<int> pq; // MAX-heap by default pq.push(3); pq.push(1); pq.push(4); pq.top(); // 4 — the largest, regardless of insert order pq.pop(); // removes 4 pq.top(); // 3 // MIN-heap: smallest first — supply std::greater as the comparator std::priority_queue<int, std::vector<int>, std::greater<>> minpq; minpq.push(3); minpq.push(1); minpq.push(4); minpq.top(); // 1 — the smallest
priority_queue<T, vector<T>, greater<>>. Worth memorizing — it's the form you'll write for Dijkstra and "k smallest" problems.Source: cppreference — std::priority_queue (max-heap default; O(log n) push/pop).
| Adaptor | Discipline | Key ops | Classic use |
|---|---|---|---|
stack | LIFO (same end) | push, pop, top | undo, DFS, bracket matching |
queue | FIFO (both ends) | push, pop, front, back | BFS, task/job queues |
priority_queue | largest first (heap) | push, pop, top | Dijkstra, scheduling, top-K |
vector/deque directly. Adaptors are for when the discipline is exactly what you want to enforce.std::stack is "an adaptor." That means:std::priority_queue<int>, after pushing 3, 1, 4 — what does top() return?auto x = s.top(); s.pop(); rather than auto x = s.pop();?stack = LIFO (push/pop the same end, top). queue = FIFO (push at back, pop at front). DFS uses stack; BFS uses queue.priority_queue give you on top()/pop()?top and O(log n) for push/pop. It's a binary heap.std::priority_queue<T, std::vector<T>, std::greater<>> — the greater comparator flips it to smallest-first.pop() return void?top()/front() first, then pop() to remove it.vector/deque directly instead.Try: "use a stack to check balanced parentheses", or "sketch Dijkstra with a min-heap priority_queue". Next we shift from storing data to moving through it — iterators and ranges.