std::queue<T> is the first-in, first-out (FIFO) sibling of std::stack: items go in at the back, come out from the front, and the order is preserved. std::priority_queue<T> looks similar from the outside but reorders elements internally so the largest one is always next out. Both are container adapters from <queue>, both have a deliberately small interface, and both follow the same top()-then-pop() pattern shown with std::stack in the previous chapter.

The <queue> header provides two different adapters:

They share the adapter idea: wrap an existing container, expose a small interface, hide everything else. They differ in the order they deliver elements:

std::stack is the third adapter, which is LIFO. The three adapters together cover the common access patterns that aren't "iterate everything."

This chapter walks through std::queue first, then std::priority_queue.

A queue models any line where the order of arrival matters. People at a checkout, packets in a network buffer, orders waiting to be processed by a fulfilment worker. The first item added is the first one served.

The vocabulary: the end for adding is the back, the end for removing is the front. Adding is push (at the back), removing is pop (at the front), peeking at the next out is front, peeking at the most recently added is back.

The diagram shows three orders in a queue. New orders are pushed at the back; the next order to be processed comes off the front. ORD-1 arrived first, so it leaves first. This is the order an e-commerce fulfilment worker would process incoming orders: in the sequence they came in.

In code, the same picture looks like this:

Orders come out in the same order they went in. That's the entire point of FIFO.

The full interface is small and mirrors std::stack almost exactly, with front and back standing in where the stack would have had top.

That's the full surface. No iteration, no random access, no find. For any of those, a std::deque directly is the better fit (the queue is wrapping one anyway).

Like std::stack, pop() returns void. The reasoning is the same: returning the element by value could throw on the way out, and the element would already have been removed. The standard splits the two operations so the caller can copy or move out of front() first, then call pop() once it's safe.

The pattern is auto x = std::move(q.front()); q.pop();. Read the value, then remove it. This idiom shows up everywhere the adapters do.

Every operation on std::queue is O(1). The default underlying container is a std::deque, which can push at the back and pop at the front in constant time without shifting elements. A std::vector would not work here, because pop_front on a vector is O(n).

That last point is worth emphasizing. std::vector cannot be used as the underlying container for std::queue, because vectors don't have pop_front, which the queue needs. The deque is the default precisely because it supports cheap insertion and removal at both ends.

This is the same trap as with std::stack. All three operations on an empty queue are undefined behavior. No bounds check, no exception, no sentinel.

Guard with empty() or loop while !q.empty(). There is no other safe pattern.

A common e-commerce pattern is a worker that pulls orders off a queue and processes them in arrival order. The queue keeps incoming work in line so the worker handles one thing at a time, in the order it came in.

The worker doesn't need to think about ordering. The queue guarantees that whatever was enqueued first comes out first. If a faster worker added orders while a slower one was processing, the queue would grow at the back, and the slower worker would catch up by draining the front.

Like std::stack, std::queue accepts a second template parameter for the underlying container. The requirements are stricter: the container must support front(), back(), push_back(), and pop_front(). That rules out std::vector (no cheap pop_front). The two realistic choices are std::deque<T> (the default) and std::list<T>.

The deque is the default for the same reason it's the default for std::stack: it supports both ends cheaply and never reallocates its whole storage. A list-backed queue gives stable iterators and per-element allocation, which can help when individual elements are very large and bulk copying must be avoided, but it pays one heap allocation per push.

Per-push allocation on std::list shows up in profiles when push rates are high. For a busy work queue, stick with the default std::deque unless there's a specific reason to switch.

A priority queue serves elements in priority order rather than insertion order. By default, "highest priority" means "greatest value": the element that compares largest comes out first. It's a max-heap with a friendly interface.

The diagram shows the conceptual tree of a max-heap holding 100, 80, 60, 50, 20, 30. The root is the largest element; every node is greater than or equal to its children. That invariant is what makes top() return the maximum in O(1) and push/pop cost O(log n).

The actual storage is a flat array (a std::vector<T> by default) where the heap structure is implicit: the children of index i live at indices 2i+1 and 2i+2. The library handles all of that. Callers push and pop without touching indices.

The API:

Same shape as std::queue, but the access pattern is different. top() is the maximum, not the oldest. There is no front/back distinction because the heap doesn't preserve insertion order.

A small program that uses a priority queue to ship the highest-value orders first. A logistics team often wants premium orders fulfilled before bulk standard orders.

The orders come out by priority, not by arrival. ORD-4 was pushed last but shipped first because its priority was the highest. ORD-1 was pushed first but shipped last.

A priority_queue push is O(log n) because the new element moves up the heap until the invariant is restored. A pop is also O(log n) because the rearrangement after removing the root has to walk down the tree. top() is O(1) because the root of a heap is always at a known location (index 0 in the backing vector).

The standard library also ships a lower-level set of algorithms (std::make_heap, std::push_heap, std::pop_heap, std::sort_heap) that operate on a raw range and build heaps without the adapter wrapper. They give more control but require manual management of the underlying container. Use them when that control is needed; otherwise the adapter is simpler.

The default ordering is std::less<T>, which gives "largest first." For "smallest first", pass std::greater<T> as the third template parameter. The underlying container must also be specified explicitly when the comparator changes, because the comparator is the third parameter and the container is the second.

A common reason to want a min-heap is a "top-N popular products" tracker. Keep the heap at size N with the current N-th largest sales count at the top. When a new product's sales beat the smallest in the heap, pop the smallest and push the new one. This gives the top N in O(m log N) for m products, beating sorting the whole list when N is small.

A min-heap of size N keeps the answer set bounded. Each new product is compared against the smallest in the heap; if it's bigger, the smallest is evicted. At the end the heap holds the top N by sales, and draining it gives them in ascending order. Reverse the output buffer for descending order.

There's also a shortcut when the type is built-in: std::priority_queue<int, std::vector<int>, std::greater<int>> is a min-heap of int. The std::greater comparator inverts the default ordering.

The same elements come out in increasing order. The comparator decides what "higher priority" means.

A callable other than a struct or function object, including a lambda, also works. The catch is that lambdas have a unique unnameable type per expression, so decltype is needed to spell out the priority queue's type.

Orders come out by promised delivery time, most urgent first, regardless of when they entered the queue. The lambda comparator returns true when the first argument has lower priority than the second, which is the convention std::priority_queue expects (it expects a Compare that defines "less than"; the top of the heap is the element that no other element is "less than").

A common confusion: in a max-heap with std::less (the default), top() is the largest. With std::greater, top() is the smallest. The naming feels backwards because the comparator is "less than" and the result is "largest first." A way to keep it straight: the comparator answers "is a worse priority than b?" The element no one beats is the one on top.

Combining the pieces into a small program that takes a stream of orders, separates them into a regular FIFO queue and an express priority queue, and shows how each is drained.

Two adapters, two different ordering rules, the same small API. The express queue reorders on each push; the standard queue keeps strict arrival order. Whichever access pattern the calling code needs, the type itself documents the contract.

The three adapters share the same skeleton: an underlying container, a small forwarding interface, no iteration, no random access, and pop() returns void. They differ in the order they hand elements out.

Choose based on the access pattern the code actually needs. For "the most recent thing added", a stack. For "the next thing in arrival order", a queue. For "the highest-priority thing regardless of arrival", a priority queue.

All three protect against accidental misuse by hiding the operations that don't belong to their pattern. A reader looking at std::priority_queue<ShippingTask> knows immediately that the code processes tasks by priority, not by arrival. A raw std::vector<ShippingTask> would force the reader to find every access site to figure out what the order actually is.