C++ stack, queue & priority_queue: Container Adapters Guide
Table of Contents
What Are Container Adapters?
Container adapters are wrappers around existing STL containers that restrict the interface to enforce specific access patterns. Instead of providing full random access or iteration, they expose only the operations appropriate for their data structure: last-in-first-out (stack), first-in-first-out (queue), or priority-based access (priority_queue).
All three adapters live in <stack>, <queue> headers. They delegate all actual storage to an underlying container — by default, std::deque for stack and queue, std::vector for priority_queue. You can swap the backing container as a template parameter.
std::stack — LIFO
std::stack enforces Last In, First Out access. You can only see and remove the top (most recently added) element:
#include <stack>
#include <iostream>
#include <string>
int main() {
std::stack<int> stk;
// Push elements — O(1)
stk.push(10);
stk.push(20);
stk.push(30);
stk.emplace(40); // construct in-place
// Access top element — O(1)
std::cout << "Top: " << stk.top() << "\n"; // 40
// Pop — O(1), returns void (not the element!)
stk.pop();
std::cout << "Top after pop: " << stk.top() << "\n"; // 30
// Size and empty check
std::cout << "Size: " << stk.size() << "\n"; // 3
std::cout << "Empty: " << stk.empty() << "\n"; // 0
// Drain the stack
while (!stk.empty()) {
std::cout << stk.top() << " ";
stk.pop();
}
// Output: 30 20 10
// Initialize from another container (C++23: range constructor)
// Or push in a loop:
std::stack<std::string> words;
for (const auto& w : {"hello", "world", "stack"}) {
words.push(w);
}
}Stack has no iterators — you cannot iterate over its elements. The only way to see all elements is to pop them one by one. This restriction is the point: it enforces the LIFO discipline.
std::queue — FIFO
std::queue enforces First In, First Out access. Elements are added at the back and removed from the front:
#include <queue>
#include <iostream>
int main() {
std::queue<int> q;
// Enqueue — add to back, O(1)
q.push(10);
q.push(20);
q.push(30);
q.emplace(40);
// Access front and back — O(1)
std::cout << "Front: " << q.front() << "\n"; // 10
std::cout << "Back: " << q.back() << "\n"; // 40
// Dequeue — remove from front, O(1)
q.pop();
std::cout << "Front after pop: " << q.front() << "\n"; // 20
// Size
std::cout << "Size: " << q.size() << "\n"; // 3
// Process queue
while (!q.empty()) {
std::cout << q.front() << " ";
q.pop();
}
// Output: 20 30 40
}Like stack, queue has no iterators. It only lets you see front() and back(). The backing container is std::deque by default, which provides O(1) push_back and pop_front.
std::priority_queue — The Heap
std::priority_queue always gives you the largest (highest priority) element first. Internally, it uses a binary max-heap built on top of a vector:
#include <queue>
#include <iostream>
int main() {
std::priority_queue<int> pq;
// Push — O(log n)
pq.push(30);
pq.push(10);
pq.push(50);
pq.push(20);
pq.push(40);
// Top always returns the largest — O(1)
std::cout << "Top: " << pq.top() << "\n"; // 50
// Pop removes the largest — O(log n)
pq.pop();
std::cout << "Top after pop: " << pq.top() << "\n"; // 40
// Drain — always gets next largest
while (!pq.empty()) {
std::cout << pq.top() << " ";
pq.pop();
}
// Output: 40 30 20 10
// Initialize from a vector
std::vector<int> data = {5, 2, 8, 1, 9};
std::priority_queue<int> pq2(data.begin(), data.end());
// Builds heap in O(n) — faster than n individual pushes
}Min-Heap Priority Queue
By default, priority_queue is a max-heap. To get a min-heap (smallest element first), reverse the comparator:
#include <queue>
#include <vector>
#include <functional> // std::greater
// Min-heap: smallest element on top
std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
min_pq.push(30);
min_pq.push(10);
min_pq.push(50);
min_pq.push(20);
std::cout << min_pq.top() << "\n"; // 10 (smallest)
min_pq.pop();
std::cout << min_pq.top() << "\n"; // 20
// Drain
while (!min_pq.empty()) {
std::cout << min_pq.top() << " ";
min_pq.pop();
}
// Output: 20 30 50The template parameters are: priority_queue<Type, Container, Compare>. std::greater<int> reverses the default std::less<int>, turning the max-heap into a min-heap. You must also specify the container (vector<int>) when providing a custom comparator.
Custom Backing Containers
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <deque>
// Stack backed by vector (default is deque)
std::stack<int, std::vector<int>> vec_stack;
vec_stack.push(1);
vec_stack.push(2);
// Stack backed by list
std::stack<int, std::list<int>> list_stack;
// Queue backed by list (default is deque)
std::queue<int, std::list<int>> list_queue;
// Priority queue backed by deque (default is vector)
std::priority_queue<int, std::deque<int>> deque_pq;
// Requirements for backing containers:
// stack: needs back(), push_back(), pop_back() → vector, deque, list
// queue: needs front(), back(), push_back(), pop_front() → deque, list (NOT vector)
// priority_queue: needs front(), push_back(), pop_back(), random access → vector, dequePriority Queue with Custom Types
#include <queue>
#include <string>
#include <iostream>
struct Task {
int priority;
std::string name;
// For max-heap: higher priority = higher value
bool operator<(const Task& other) const {
return priority < other.priority; // lower priority is "less"
}
};
int main() {
std::priority_queue<Task> task_queue;
task_queue.push({3, "Fix bug"});
task_queue.push({1, "Update docs"});
task_queue.push({5, "Security patch"});
task_queue.push({2, "Add feature"});
while (!task_queue.empty()) {
const auto& task = task_queue.top();
std::cout << "[P" << task.priority << "] " << task.name << "\n";
task_queue.pop();
}
// [P5] Security patch
// [P3] Fix bug
// [P2] Add feature
// [P1] Update docs
// Using a lambda comparator
auto cmp = [](const Task& a, const Task& b) {
return a.priority > b.priority; // min-heap by priority
};
std::priority_queue<Task, std::vector<Task>, decltype(cmp)> min_tasks(cmp);
min_tasks.push({3, "Fix bug"});
min_tasks.push({1, "Update docs"});
std::cout << min_tasks.top().name << "\n"; // Update docs (lowest priority)
}Real-World Examples
#include <stack>
#include <queue>
#include <string>
#include <iostream>
// Balanced parentheses checker (stack)
bool is_balanced(const std::string& expr) {
std::stack<char> stk;
for (char c : expr) {
if (c == '(' || c == '[' || c == '{') {
stk.push(c);
} else if (c == ')' || c == ']' || c == '}') {
if (stk.empty()) return false;
char top = stk.top();
stk.pop();
if ((c == ')' && top != '(') ||
(c == ']' && top != '[') ||
(c == '}' && top != '{')) {
return false;
}
}
}
return stk.empty();
}
// BFS shortest path (queue)
void bfs(const std::vector<std::vector<int>>& graph, int start) {
std::vector<bool> visited(graph.size(), false);
std::queue<int> q;
q.push(start);
visited[start] = true;
while (!q.empty()) {
int node = q.front();
q.pop();
std::cout << node << " ";
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
}
// Merge K sorted lists (priority queue / min-heap)
struct ListNode {
int val;
int list_idx;
int elem_idx;
bool operator>(const ListNode& other) const {
return val > other.val;
}
};
std::vector<int> merge_k_sorted(
const std::vector<std::vector<int>>& lists)
{
std::priority_queue<ListNode, std::vector<ListNode>,
std::greater<ListNode>> min_heap;
// Initialize with first element of each list
for (int i = 0; i < lists.size(); ++i) {
if (!lists[i].empty()) {
min_heap.push({lists[i][0], i, 0});
}
}
std::vector<int> result;
while (!min_heap.empty()) {
auto [val, li, ei] = min_heap.top();
min_heap.pop();
result.push_back(val);
if (ei + 1 < lists[li].size()) {
min_heap.push({lists[li][ei + 1], li, ei + 1});
}
}
return result;
}Common Mistakes
Calling top() or front() on empty adapters. This is undefined behavior. Always check .empty() first.
Expecting pop() to return the element. All three adapters’ pop() methods return void. Read the element with top() or front() before popping.
Trying to iterate. Container adapters intentionally have no iterators. If you need to iterate, use the underlying container directly instead of the adapter.
Wrong comparator direction for min-heap. std::greater creates a min-heap (counterintuitive). The comparator tells the heap what should go lower, not higher. greater means “put greater elements lower” → smallest on top.
Using vector as queue backing. std::queue<int, std::vector<int>> won’t compile — vector doesn’t have pop_front(). Use deque (default) or list.
Summary
std::stack provides LIFO access with push/top/pop. std::queue provides FIFO access with push/front/pop. std::priority_queue provides priority-based access using a binary heap — max-heap by default, min-heap with std::greater. All three are adapters that wrap an underlying container and restrict its interface. They have no iterators by design. In the next lesson, you’ll dive deep into iterators — the glue that connects all STL containers to algorithms.
