stack, queue and priority_queue

A container adaptor is a container with a smaller interface. std::stack keeps the last element pushed on top, std::queue keeps the first one at the front, and std::priority_queue always hands out the largest. None of them lets you look at the middle.

The restriction is the feature: a stack that cannot be indexed cannot be indexed wrongly, and a priority queue that always returns the maximum saves a search. Each adaptor is a class template over an underlying container, which this lesson also makes visible.

The adaptors own their underlying container, so copying a stack copies every element; a function that takes one by reference avoids that, and a const reference when it only reads the top.

A priority queue is a heap inside a vector: the largest element is at the front and every push or pop restores the heap with a logarithmic number of swaps, which is why the adaptor has no ordered iteration to offer.

A stack, a queue and a priority queue can all be cleared by assigning a fresh object to them, which is also how a program resets their underlying container.

stack

push adds to the top, pop removes the top and top reads it. The adaptor has no iterators and no index, so the only element a program can see is the top one.

The program pushes three values and pops one, printing the top after each step. The output is the last-in-first-out order that gives the container its name.

std::stack is the tool for matching brackets, undoing operations and depth-first walks. Its default underlying container is std::deque, which grows at the front and the back without moving elements.

#include <iostream> #include <stack> int main() { std::stack<int> values; values.push(1); values.push(2); values.push(3); std::cout << values.top() << ' '; values.pop(); std::cout << values.top() << ' '; std::cout << values.size() << '\n'; }

g++ -std=c++23 -Wall -Wextra stack.cpp -o stack_demo
./stack_demo

3 2 2

queue

push adds at the back and pop removes from the front. front() and back() read the two ends, and the order is first-in-first-out.

The program pushes three values, pops one and prints the front and the back. The element at the front is the one pushed first, which is the difference from the stack.

A queue is the shape of a work list processed in arrival order, and of the producer-consumer pattern in part 10. Its default container is std::deque for the same reason as the stack's.

#include <iostream> #include <queue> int main() { std::queue<int> values; values.push(1); values.push(2); values.push(3); values.pop(); std::cout << values.front() << ' ' << values.back() << ' ' << values.size() << '\n'; }

g++ -std=c++23 -Wall -Wextra queue.cpp -o queue_demo
./queue_demo

2 3 2

priority_queue

std::priority_queue keeps its elements in a heap and always returns the largest at top(). Pushing and popping cost logarithmic time, and reading the top costs nothing.

The program pushes four values in mixed order and prints them by popping. The output is descending, whatever the insertion order was.

The comparison is the second template argument, so a priority_queue of a custom type takes a comparator, and a min-heap is std::priority_queue<int, std::vector<int>, std::greater<int>>.

#include <iostream> #include <queue> #include <vector> int main() { std::priority_queue<int> values; for (int value : {5, 1, 9, 3}) { values.push(value); } while (!values.empty()) { std::cout << values.top() << ' '; values.pop(); } std::cout << '\n'; }

g++ -std=c++23 -Wall -Wextra priority.cpp -o priority_demo
./priority_demo

9 5 3 1

The container underneath

Every adaptor is template <class T, class Container = ...>, and the second parameter is the container it stores. A stack over std::vector works the same as one over std::deque, and the choice changes how memory is allocated.

The program declares a stack over std::vector explicitly and pushes three values. The size and the top are the same as with the default, because the interface is the same.

The choice matters for performance: a vector-backed stack allocates less often and iterates better, a deque-backed one never moves its elements. std::stack over std::vector is a common choice for a hot path.

#include <iostream> #include <stack> #include <vector> int main() { std::stack<int, std::vector<int>> values; values.push(10); values.push(20); values.push(30); std::cout << values.top() << ' ' << values.size() << '\n'; }

g++ -std=c++23 -Wall -Wextra underlying.cpp -o underlying_demo
./underlying_demo

30 3

An adaptor has no index

A stack deliberately hides the elements below the top, so it has no operator[]. Code that needs the second element has chosen the wrong container.

The program reads values[0] and the compiler says the stack has no subscript operator. The fix is a std::vector or a std::deque, which keep the interface the program is using.

The same is true of top() on a queue and of indexing a priority_queue. If a program needs to look inside, an adaptor is the wrong tool and the plain container is the right one.

#include <stack> int main() { std::stack<int> values; values.push(1); return values[0]; }

g++ -std=c++23 -Wall -Wextra index.cpp -o index

index.cpp: In function 'int main()':
index.cpp:7:18: error: no match for 'operator[]' (operand types are 'std::stack<int>' and 'int')
7 | return values[0];
| ^

Exercises

1. Use a stack to check whether the brackets in a string are balanced.
2. Change the priority queue to a min-heap with std::greater and print the popped order.
3. Build a queue that stores std::string and print the front after three pushes and two pops.

The code on this page was built with g++ 15.2.0 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container. The programs whose section shows a compiler error were compiled until that error and were not run.

Article author: Arthur Isaev