Skip to content
Tutorials Center
My learning

Topics

Lesson 98 of 171 ยท The Standard Library (STL)

Container Adapters: stack, queue and priority_queue

Learn C++ std::stack, std::queue and std::priority_queue - LIFO and FIFO operations, min-heaps with std::greater, custom comparators and top-k problems.

Sometimes the best thing a container can do for you is refuse operations. A stack of undo actions should only ever be touched at the top; a queue of print jobs should only be served from the front. The standard library's container adapters give you exactly those restricted interfaces: std::stack (last in, first out), std::queue (first in, first out) and std::priority_queue (always hands out the most important element next).

They're called adapters because they aren't containers of their own. Each one wraps a real sequence container, a std::deque or std::vector by default, and exposes only the operations that make sense for its job. That makes code clearer (a std::stack documents your intent better than a vector you promise to use only at the back) and prevents whole classes of mistakes. In this lesson you'll use all three, learn why pop() returns nothing, build min-heaps and custom priorities, and solve the classic "top k" problem efficiently.

What the three adapters have in common

Adapter Header Access Default underlying container
std::stack<T> <stack> top() only (LIFO) std::deque<T>
std::queue<T> <queue> front() and back(); remove at the front (FIFO) std::deque<T>
std::priority_queue<T> <queue> top() = the largest element std::vector<T>

All three share push(x), emplace(args...), pop(), empty(), size() and swap(). None of them has iterators, so you can't loop over an adapter, print it with std::println("{}", s), or search it. That's deliberate: if you need to look inside, you need a real container instead.

Why pop() returns void

In every adapter, pop() removes the element without returning it. You read first, then pop:

C++
int value = s.top();   // copy (or std::move) the element out
s.pop();               // then remove it

This two-step design is about exception safety. If pop() returned the element by value and the copy constructor threw while the value was being returned, the element would already be gone from the container and lost forever. Splitting "look" and "remove" means a failure while copying leaves the container untouched. Calling top(), front() or pop() on an empty adapter is undefined behavior, so always check empty() first.

std::stack: last in, first out

A stack is the right tool whenever the most recent unfinished thing must be dealt with first: undo histories, nested brackets, expression evaluation, depth-first search without recursion. The classic exercise is checking that brackets are balanced:

C++ Checking balanced brackets with a stack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

The underlying container of a stack only needs back(), push_back() and pop_back(), so std::vector works too and is often a little faster than the default deque for small elements: std::stack<char, std::vector<char>>. A stack can also be built from an existing container: std::stack<int, std::vector<int>> s{std::vector{1, 2, 3}}; has 3 on top.

std::queue: first in, first out

A queue serves elements in the order they arrived. Use it for job queues, message buffers, simulations, and above all breadth-first search, which explores a graph level by level. Here BFS finds the shortest path through a small maze:

C++ Shortest path in a maze with a queue

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

Because cells leave the queue in the order they were discovered, every cell is first reached by a shortest route; the printed grid shows each cell's distance from the start. Graphs, Recursion and Backtracking builds on this.

A queue needs front(), back(), push_back() and pop_front() from its container. std::deque (the default) and std::list qualify; std::vector doesn't, because it has no pop_front.

std::priority_queue: always the biggest first

A priority queue is a binary heap stored in a vector. push and pop are O(log n) and top() is O(1). By default top() returns the largest element according to operator<:

C++ Max-heap, min-heap and custom priorities

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

The comparator is the part everyone gets backwards. It answers the question "does a come out after b?", which is the same as "is a less than b?" for the default max-heap. The element for which the comparator is false against every other element ends up on top. So:

  • std::less<T> (the default) puts the largest on top.
  • std::greater<T> puts the smallest on top: a min-heap.
  • For a custom type, either give it an operator< (or a defaulted operator<=>, see Operator Overloading), or pass a comparator type as the third template argument. With a lambda, use decltype(lambda) as the type and pass the lambda to the constructor. Since C++20, captureless lambdas are default-constructible, so passing it is optional, but it's clearer.

emplace(3, "review code") works on an aggregate like Task because C++20 allows parenthesized aggregate initialization.

What a priority_queue can't do

  • No iteration and no sorted view. The internal vector is a heap, not a sorted array.
  • No "decrease key" or removal of arbitrary elements. Algorithms like Dijkstra's work around this by pushing a new entry and skipping stale ones when they're popped.
  • No clear(). Assign an empty adapter: tasks = {}; works for the default comparator; with a lambda comparator, swap with an empty one or pop until empty.

If you need more control, use the heap algorithms from <algorithm> directly on a vector: std::ranges::make_heap, push_heap, pop_heap and sort_heap. That's exactly what priority_queue does internally, and you keep full access to the vector.

Top-k problems

"Find the k largest values" is one of the most common interview and production problems. Sorting everything is O(n log n). A better approach keeps a min-heap of size k: its top is the smallest of the best k seen so far, so any new value bigger than that top replaces it. That's O(n log k), and it needs only O(k) memory, which matters when the data streams in and doesn't fit in memory.

C++ The k largest values with a bounded min-heap

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

Both approaches give the same answer. std::ranges::partial_sort (covered in Algorithms: Searching, Sorting and Counting) is a fine choice when all the data is already in a vector you may reorder; the bounded heap shines when values arrive one at a time. The mirror problem, "k smallest", uses a max-heap of size k.

Merging sorted lists

Another heap classic is merging k sorted sequences: put the first element of each into a min-heap together with which list it came from, then repeatedly pop the smallest and push that list's next element. Each output element costs O(log k).

C++ Merging sorted lists with a min-heap

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

std::tuple compares element by element, so std::greater<Entry> orders entries by value first. Tuples get their own lesson in std::pair and std::tuple.

Choosing the underlying container

The second template parameter lets you pick what an adapter wraps, as long as the container provides the operations the adapter needs:

C++
std::stack<int, std::vector<int>> s;                 // vector is a good stack
std::queue<int, std::list<int>> q;                   // list works for a queue
std::priority_queue<int, std::deque<int>> pq;        // needs random access: vector or deque

In practice, keep the defaults unless profiling says otherwise; std::stack<T, std::vector<T>> is the most common change.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. std::stack<int> s; s.push(1); s.push(2); s.push(3); s.pop(); What does s.top() return now?

    A stack is last in, first out. pop() removes 3 (and returns nothing), leaving 2 on top.
  2. 2. Why does pop() return void in the standard adapters?

    If pop() returned the element and the copy threw, the element would already be removed and lost. Separating read and remove keeps the strong exception guarantee.
  3. 3. Which declaration gives a priority_queue whose top() is the smallest int?

    The default comparator std::less puts the largest element on top. std::greater reverses that, producing a min-heap.
  4. 4. To find the 10 largest values in a stream of millions of numbers, what is the efficient approach?

    A bounded min-heap keeps the best 10 seen so far with the weakest on top, giving O(n log k) time and O(k) memory. A max-heap of everything needs O(n) memory.
  5. 5. Which container can NOT be used as the underlying container of std::queue?

    std::queue removes from the front with pop_front(), which std::vector doesn't provide.

Summary

  • Container adapters wrap a sequence container and expose a restricted interface; they have no iterators.
  • std::stack is LIFO (push, top, pop), std::queue is FIFO (push, front, back, pop); both wrap a std::deque by default.
  • pop() returns nothing: read with top() or front() first. Never call them on an empty adapter.
  • std::priority_queue is a binary heap in a vector: O(log n) push and pop, largest on top. Use std::greater<T> for a min-heap, or a custom comparator that returns true when a should come out after b.
  • Top-k problems use a bounded heap of the opposite kind (min-heap for the k largest) in O(n log k); heaps also merge sorted sequences efficiently.
  • For full control, use the heap algorithms (make_heap, push_heap, pop_heap) on a vector you own.

Next: std::map and std::multimap, the ordered key-value containers.