C++ stack, queue and priority_queue: How the Adapters Work and the Mistakes They Invite
Key takeaways
std::stack, std::queue and std::priority_queue are not containers of their own. They are thin wrappers that restrict another container to one access pattern. Knowing what they wrap explains their odd API (pop() returning void, no iterators, a comparator that seems backwards) and the bugs people hit with them.
What an adapter is
The standard library has three container adapters. Each one owns an ordinary sequence container and exposes only the operations of one abstract data type:
| Adapter | Access pattern | Default underlying container | Operations |
|---|---|---|---|
std::stack<T> | LIFO: last in, first out | std::deque<T> | push, pop, top, empty, size |
std::queue<T> | FIFO: first in, first out | std::deque<T> | push, pop, front, back, empty, size |
std::priority_queue<T> | Largest element first | std::vector<T> (as a binary heap) | push, pop, top, empty, size |
Deliberately missing: iterators, indexing, clear(), and any way to look below the top. If you need to traverse the elements, you do not want an adapter; use the underlying container directly (std::vector as a stack, std::deque as a queue). The point of the adapter is the restriction — a std::stack in a function signature tells the reader that only the top matters.
Complexity follows from the underlying container. push/pop on stack and queue are O(1). On priority_queue they are O(log n), because every insertion and removal restores the heap property, and top() is O(1).
std::stack
#include <stack>
#include <iostream>
std::stack<int> s;
s.push(1);
s.push(2);
s.push(3);
while (!s.empty()) {
std::cout << s.top() << ' '; // 3 2 1
s.pop();
}A typical use is matching brackets, where the most recent open bracket is the only one that matters:
bool balanced(const std::string& text) {
std::stack<char> open;
for (char c : text) {
if (c == '(' || c == '[' || c == '{') {
open.push(c);
} else if (c == ')' || c == ']' || c == '}') {
if (open.empty()) return false;
char expected = c == ')' ? '(' : c == ']' ? '[' : '{';
if (open.top() != expected) return false;
open.pop();
}
}
return open.empty();
}The open.empty() check before top() is not optional. Calling top(), front() or pop() on an empty adapter is undefined behavior; there is no bounds check and no exception. On a closing bracket with nothing open, the unchecked version reads garbage or crashes, and it only happens on malformed input — exactly the case tests tend to skip.
Choosing the container for a stack
std::stack<int, std::vector<int>> s; // contiguous storagestd::vector is usually at least as good as the default deque for a stack: push_back/pop_back are amortized O(1), memory is contiguous and cache-friendly, and it can reuse its capacity. deque is the default mostly for historical reasons and because it never relocates existing elements. One platform detail worth knowing: MSVC’s std::deque allocates in very small blocks (a block holds only one element once elements exceed a small size), so on that standard library a deque of large objects behaves more like a list of heap allocations. If a stack of big structs is a hot path on Windows, measure vector against the default.
std::queue
#include <queue>
std::queue<std::string> jobs;
jobs.push("parse");
jobs.push("compile");
jobs.push("link");
std::cout << jobs.front() << ' ' << jobs.back() << '\n'; // parse link
jobs.pop(); // removes "parse"std::queue needs pop_front, so it only works with deque or list:
std::queue<int, std::vector<int>> q;
q.push(1);
q.pop(); // error: 'class std::vector<int>' has no member named 'pop_front'The declaration compiles; the error appears only when you instantiate pop(), which can be confusing the first time.
BFS, and the visited-marking bug
Breadth-first search is the canonical queue algorithm:
std::vector<int> bfsDistances(const std::vector<std::vector<int>>& graph, int start) {
std::vector<int> dist(graph.size(), -1);
std::queue<int> q;
dist[start] = 0;
q.push(start);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : graph[u]) {
if (dist[v] == -1) { // mark when enqueuing, not when dequeuing
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
return dist;
}The comment marks the most common BFS bug I see in code reviews and interview solutions: marking a node as visited when it is popped instead of when it is pushed. The result is still correct on small inputs, but a node reachable from many neighbors is pushed once per neighbor before any of them is processed. On dense graphs the queue grows toward the number of edges instead of the number of nodes, which shows up as a time limit or memory blowup only on large tests.
std::priority_queue
std::priority_queue<int> maxHeap; // largest on top
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap; // smallest on top
for (int x : {3, 1, 4, 1, 5}) {
maxHeap.push(x);
minHeap.push(x);
}
std::cout << maxHeap.top() << ' ' << minHeap.top() << '\n'; // 5 1The comparator is where priority_queue confuses everyone once. It is not “sort order”; it answers “is a lower priority than b?”. The element for which no other element compares higher ends up on top. std::less means smaller values are lower priority, so the maximum is on top; std::greater flips it into a min-heap.
Custom comparators
struct Task {
int priority;
std::string name;
};
auto byPriority = [](const Task& a, const Task& b) { return a.priority < b.priority; };
std::priority_queue<Task, std::vector<Task>, decltype(byPriority)> tasks(byPriority);
tasks.push({1, "low"});
tasks.push({5, "high"});
tasks.push({3, "mid"});
while (!tasks.empty()) {
std::cout << tasks.top().name << ' '; // high mid low
tasks.pop();
}Pass the lambda to the constructor as well as to decltype. Before C++20, lambda types have no default constructor, so std::priority_queue<Task, std::vector<Task>, decltype(byPriority)> tasks; does not compile. Since C++20, captureless lambdas are default-constructible and the constructor argument becomes optional.
Equal priorities are not FIFO
A heap does not preserve insertion order among equal elements. If two tasks have the same priority, either may come out first, and the order can change as other elements are pushed. For a job scheduler that expectation matters, so add a sequence number as a tie-breaker:
using Entry = std::tuple<int, long, std::string>; // (-priority, sequence, name)
std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> jobs;
long seq = 0;
for (auto name : {"a", "b", "c"}) jobs.push({-1, seq++, name});
// pops a, b, c: equal priority, then lower sequence firstTuples compare lexicographically, so the sequence only matters when priorities tie. Negating the priority lets one std::greater produce “highest priority, then oldest”.
top() is const: you cannot move out of it
top() returns a const T&, because modifying the top element could break the heap invariant. For expensive-to-copy elements (large strings, vectors), popping requires a copy:
Task t = tasks.top(); // copy
tasks.pop();Casting away const to std::move from top() is a common trick and it works in practice with libstdc++ and libc++ because pop() only moves elements around, but it relies on implementation details. If this copy shows up in a profile, manage the heap yourself with std::vector plus std::push_heap/std::pop_heap: after pop_heap, the largest element sits at back() and can be moved out legitimately.
For the same reason, you cannot change an element’s priority in place. There is no “decrease-key” operation.
Dijkstra without decrease-key
The standard workaround is lazy deletion: push a new entry whenever a distance improves, and skip stale entries when they come out.
using Edge = std::pair<int, int>; // (neighbor, weight)
std::vector<int> dijkstra(const std::vector<std::vector<Edge>>& g, int src) {
std::vector<int> dist(g.size(), std::numeric_limits<int>::max());
using Item = std::pair<int, int>; // (distance, node)
std::priority_queue<Item, std::vector<Item>, std::greater<Item>> pq;
dist[src] = 0;
pq.push({0, src});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue; // stale entry: a shorter path was already found
for (auto [v, w] : g[u]) {
if (d + w < dist[v]) {
dist[v] = d + w;
pq.push({dist[v], v});
}
}
}
return dist;
}The heap can hold several entries per node, so its size is bounded by the number of edges, not nodes. That is the accepted trade-off; the continue line is what keeps it correct and efficient, and forgetting it turns the algorithm into repeated relaxation of already-finished nodes.
Thread safety
None of the adapters is safe for concurrent use. A work queue shared between threads needs a lock, and the check-then-act sequence must be atomic:
template <typename T>
class BlockingQueue {
std::queue<T> q_;
std::mutex m_;
std::condition_variable cv_;
public:
void push(T value) {
{
std::lock_guard lock(m_);
q_.push(std::move(value));
}
cv_.notify_one();
}
T pop() {
std::unique_lock lock(m_);
cv_.wait(lock, [this] { return !q_.empty(); });
T value = std::move(q_.front()); // front() is not const: moving out is fine
q_.pop();
return value;
}
};The broken version checks empty() in one locked section and calls front() in another. Between the two, another consumer can take the last element, and the second call hits an empty queue — undefined behavior that appears only under load. The predicate form of wait also handles spurious wakeups. For a fuller treatment, see condition_variable basics.
What this minimal version lacks is a way to stop. At shutdown, consumer threads blocked in pop() wait forever, and join() on them hangs the program. The usual fix is a closed_ flag set under the lock, followed by cv_.notify_all(); pop() waits for !q_.empty() || closed_ and returns an empty std::optional<T> once the queue is closed and drained. It is also unbounded: if producers are faster than consumers, memory grows without limit, so a production work queue usually has a capacity and a second condition variable that blocks producers when it is full.
Building a priority_queue from existing data
Pushing n elements one at a time costs O(n log n). If the elements are already in a vector, hand them to the constructor instead, which builds the heap with std::make_heap in O(n) and, when you move the vector in, allocates nothing new:
std::vector<int> values = loadScores(); // already filled
std::priority_queue<int> pq(std::less<int>{}, std::move(values));The same constructor is the only way to control the capacity of the underlying vector, since the adapter has no reserve(): reserve on a vector first, then move it in. The adapter’s underlying container is a protected member named c, so a small derived class can also expose it, for example to iterate over all queued items for debugging. That is legitimate, but at that point it is worth asking whether you want a plain vector with the heap algorithms instead.