Stacks, queues and priority queues are three of the most used data structures in computer science. A stack checks balanced brackets and powers undo; a queue drives breadth-first search and task scheduling; a priority queue is the heart of Dijkstra's algorithm, CPU schedulers and "top K" problems.
In C++ you do not have to write any of them yourself. The STL provides std::stack, std::queue and std::priority_queue. Interestingly, these are not new containers. They are container adaptors: thin wrappers that take a container you already know (deque, vector or list from the previous chapters) and expose only a restricted interface.
What Is a Container Adaptor?
A container adaptor is a class template that stores an underlying sequence container and offers a limited, purpose-specific interface on top of it. It hides every operation that would break the data structure's rules.
For example, a stack must only let you touch the top. A deque lets you do anything, so std::stack wraps a deque and only exposes push, pop and top.
Adaptor | Header | Rule | Default underlying container | Other allowed containers |
|---|---|---|---|---|
|
| LIFO (last in, first out) |
|
|
|
| FIFO (first in, first out) |
|
|
|
| Highest priority first |
|
|
Two important consequences of being adaptors:
They have no iterators. You cannot write a range-based
forover astd::stack. If you need to look at all elements, you probably want the underlying container itself.They do not check for emptiness. Calling
top(),front()orpop()on an empty adaptor is undefined behavior, not an exception.
std::stack – Last In, First Out
Think of a stack of plates: you put a plate on top, and you take the top plate off. The last plate placed is the first one removed.
push(10) push(20) push(30) pop()
┌────┐
┌────┐ │ 30 │ ← top
┌────┐ │ 20 │ │ 20 │ ┌────┐
│ 10 │ │ 10 │ │ 10 │ │ 20 │ ← top
└────┘ └────┘ └────┘ │ 10 │
└────┘Member | Meaning | Cost (default deque) |
|---|---|---|
| Put an element on top | O(1) |
| Remove the top element (returns nothing) | O(1) |
| Reference to the top element | O(1) |
| Is it empty? How many elements? | O(1) |
#include <iostream>
#include <stack>
int main() {
std::stack<int> st;
st.push(10);
st.push(20);
st.push(30);
std::cout << "Top: " << st.top() << ", size: " << st.size() << '\n';
st.top() = 35; // top() returns a reference
while (!st.empty()) {
std::cout << "Popping " << st.top() << '\n';
st.pop(); // pop() returns void
}
std::cout << "Empty now? " << std::boolalpha << st.empty() << '\n';
}Output:
Top: 30, size: 3
Popping 35
Popping 20
Popping 10
Empty now? trueBecause top() returns a reference, st.top() = 35; modified the element in place.
Why Does pop() Return void?
Students coming from Java or Python often expect int x = st.pop();. In C++ that does not compile, and the reason is exception safety. If pop() removed the element and then returned it by value, the copy into x could throw (imagine a large std::string and memory running out). The element would already be removed from the stack, but never delivered to you: it would be lost forever. Splitting the job into top() (read) and pop() (remove) makes each step safe. It also avoids an unnecessary copy when you only want to discard the element.
Example: Balanced Brackets
This is a classic interview problem. Every opening bracket is pushed; every closing bracket must match the most recent unmatched opening bracket, which is exactly the top of the stack.
#include <iostream>
#include <stack>
#include <string>
bool isBalanced(const std::string& s) {
std::stack<char> st;
for (char c : s) {
if (c == '(' || c == '[' || c == '{') {
st.push(c);
} else if (c == ')' || c == ']' || c == '}') {
if (st.empty()) return false; // closing with nothing open
char open = st.top();
st.pop();
if ((c == ')' && open != '(') ||
(c == ']' && open != '[') ||
(c == '}' && open != '{'))
return false; // wrong kind of bracket
}
}
return st.empty(); // something left open?
}
int main() {
for (std::string s : {"{[()()]}", "([)]", "((", "a*(b+c)"}) {
std::cout << s << " -> " << (isBalanced(s) ? "balanced" : "not balanced") << '\n';
}
}Output:
{[()()]} -> balanced
([)] -> not balanced
(( -> not balanced
a*(b+c) -> balancedTrace for ([)]: push (, push [, then ) arrives but the top is [, a mismatch, so the function returns false. Each character is processed once, so the algorithm runs in O(n) time and O(n) extra space.
std::queue – First In, First Out
A queue works like a ticket counter: people join at the back and are served from the front.
front back
pop() ◄── [ Asha ][ Ravi ][ Meena ] ◄── push()Member | Meaning | Cost (default deque) |
|---|---|---|
| Add at the back | O(1) |
| Remove from the front (returns nothing) | O(1) |
| References to the first / last element | O(1) |
| As usual | O(1) |
#include <iostream>
#include <queue>
#include <string>
int main() {
std::queue<std::string> counter;
counter.push("Asha");
counter.push("Ravi");
counter.push("Meena");
std::cout << "Front: " << counter.front() << ", Back: " << counter.back() << '\n';
while (!counter.empty()) {
std::cout << "Serving " << counter.front() << '\n';
counter.pop();
}
}Output:
Front: Asha, Back: Meena
Serving Asha
Serving Ravi
Serving MeenaWhy is the default container deque and not vector? A queue removes from the front. vector has no pop_front because it would be O(n), while deque::pop_front is O(1) (see list, deque & array).
Example: Breadth-First Search
BFS explores a graph level by level. A queue guarantees that all vertices at distance d are processed before any vertex at distance d + 1, which is why BFS finds shortest paths in unweighted graphs.
0 ─── 1
│ │
2 ─── 3 ─── 5
│
4#include <iostream>
#include <queue>
#include <vector>
int main() {
// Undirected graph with 6 vertices as an adjacency list
std::vector<std::vector<int>> adj = {
{1, 2}, // 0
{0, 3}, // 1
{0, 3, 4}, // 2
{1, 2, 5}, // 3
{2}, // 4
{3} // 5
};
std::vector<int> dist(adj.size(), -1);
std::queue<int> q;
dist[0] = 0;
q.push(0);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (dist[v] == -1) { // not visited yet
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
for (std::size_t i = 0; i < dist.size(); ++i)
std::cout << "dist[" << i << "] = " << dist[i] << '\n';
}Output:
dist[0] = 0
dist[1] = 1
dist[2] = 1
dist[3] = 2
dist[4] = 2
dist[5] = 3Each vertex enters the queue at most once and each edge is examined at most twice (once from each end), so BFS takes O(V + E) time.
std::priority_queue – Highest Priority First
A priority queue is a collection where every removal takes out the element with the highest priority, regardless of insertion order.
std::priority_queueimplements it as a binary heap stored inside avector.
By default, "highest priority" means "largest according to operator<", so std::priority_queue<int> is a max-heap.
How the Heap Works
A binary max-heap is a complete binary tree where every parent is ≥ its children. It is stored level by level in an array: the children of index i are at 2i + 1 and 2i + 2.
50 index: 0 1 2 3 4
/ \ value: 50 40 30 10 20
40 30
/ \
10 20top() is simply element 0: O(1).
push(x) appends
xat the end and "sifts it up", swapping with its parent while it is larger. The tree height is log2 n, so this is O(log n).pop() moves the last element to the root and "sifts it down", swapping with the larger child: O(log n).
Building from n elements at once (the iterator-range constructor) uses the bottom-up heap construction, which is O(n), better than n separate pushes (O(n log n)).
Member | Meaning | Cost |
|---|---|---|
| Insert an element | O(log n) |
| Remove the top element | O(log n) |
| const reference to the highest-priority element | O(1) |
constructor from a range | Build a heap from existing data | O(n) |
Notice that top() returns a const reference. If you could change the top element, you would break the heap ordering.
Max-Heap and Min-Heap
#include <functional> // std::greater
#include <iostream>
#include <queue>
#include <vector>
int main() {
std::vector<int> nums = {40, 10, 50, 30, 20};
std::priority_queue<int> maxHeap; // default: largest on top
for (int x : nums) maxHeap.push(x);
std::cout << "Max-heap order: ";
while (!maxHeap.empty()) {
std::cout << maxHeap.top() << ' ';
maxHeap.pop();
}
std::cout << '\n';
std::priority_queue<int, std::vector<int>, std::greater<int>>
minHeap(nums.begin(), nums.end()); // build in O(n)
std::cout << "Min-heap order: ";
while (!minHeap.empty()) {
std::cout << minHeap.top() << ' ';
minHeap.pop();
}
std::cout << '\n';
}Output:
Max-heap order: 50 40 30 20 10
Min-heap order: 10 20 30 40 50 The full template is std::priority_queue<T, Container, Compare>. To get a min-heap we pass std::greater<int> as the comparator, but because the comparator is the third parameter we must also spell out the second one, std::vector<int>.
The comparator logic feels backwards at first, so remember this rule:
The comparator
comp(a, b)answers "doesahave lower priority thanb?" The element that is "greatest" by this comparison ends up on top. Withstd::less(the default) the largest value is on top; withstd::greaterthe smallest value is on top.
A quick alternative trick for a min-heap of numbers is to push -x into a max-heap and negate again when reading, but the std::greater version is clearer (and does not overflow for INT_MIN).
Custom Priorities with a Struct
Let's model a hospital emergency room: more severe patients first; for equal severity, whoever arrived first.
#include <iostream>
#include <queue>
#include <string>
#include <vector>
struct Patient {
std::string name;
int severity; // higher = more urgent
int arrival; // lower = came earlier
};
// Comparator returns true if a has LOWER priority than b
struct LessUrgent {
bool operator()(const Patient& a, const Patient& b) const {
if (a.severity != b.severity) return a.severity < b.severity;
return a.arrival > b.arrival; // tie: earlier arrival first
}
};
int main() {
std::priority_queue<Patient, std::vector<Patient>, LessUrgent> er;
er.push({"Kiran", 2, 1});
er.push({"Divya", 5, 2});
er.push({"Arjun", 3, 3});
er.push({"Sana", 5, 4});
while (!er.empty()) {
const Patient& p = er.top();
std::cout << p.name << " (severity " << p.severity << ")\n";
er.pop();
}
}Output:
Divya (severity 5)
Sana (severity 5)
Arjun (severity 3)
Kiran (severity 2)Divya and Sana both have severity 5. The comparator says the one with the larger arrival number has lower priority, so Divya (arrival 2) comes before Sana (arrival 4). A priority queue is not stable: without that tie-breaking rule, elements of equal priority could come out in any order.
The comparator here is a function object: a struct with an overloaded operator(), which we saw in the Operator Overloading chapter. It must be a strict weak ordering: in particular, comp(a, a) must be false. Using <= instead of < breaks this rule and gives undefined behavior.
Example: Top K Elements in O(n log k)
To find the 3 highest scores, keep a min-heap of size k. Its top is the smallest of the best k seen so far; whenever the heap grows beyond k, throw that smallest away.
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
// k largest elements using a min-heap of size k: O(n log k)
std::vector<int> topK(const std::vector<int>& v, std::size_t k) {
std::priority_queue<int, std::vector<int>, std::greater<int>> heap;
for (int x : v) {
heap.push(x);
if (heap.size() > k) heap.pop(); // throw away the smallest
}
std::vector<int> result;
while (!heap.empty()) {
result.push_back(heap.top());
heap.pop();
}
return result; // in increasing order
}
int main() {
std::vector<int> scores = {67, 92, 45, 88, 99, 73, 81};
for (int s : topK(scores, 3)) std::cout << s << ' ';
std::cout << '\n';
}Output:
88 92 99 Each push/pop costs O(log k) because the heap never holds more than k + 1 elements, giving O(n log k) overall. That is better than sorting everything (O(n log n)) when k is small.
Choosing the Underlying Container
You can pass the container as the second template argument. For example, a stack on a vector avoids the deque's block allocations and is a common choice:
#include <iostream>
#include <stack>
#include <vector>
int main() {
std::stack<int, std::vector<int>> st; // stack on top of a vector
st.push(1);
st.push(2);
std::stack<int> empty;
// empty.top(); // undefined behavior: no check, no exception!
// empty.pop(); // undefined behavior too
if (!empty.empty()) std::cout << empty.top() << '\n';
else std::cout << "Stack is empty, nothing to read\n";
std::cout << "st.top() = " << st.top() << '\n';
}Output:
Stack is empty, nothing to read
st.top() = 2The container must provide the operations the adaptor uses:
stack:back(),push_back(),pop_back()queue:front(),back(),push_back(),pop_front()priority_queue: random-access iterators,front(),push_back(),pop_back()
C++23 Additions
C++23 made the adaptors easier to fill from existing data. stack and queue gained constructors that take an iterator pair (priority_queue always had one), and all three gained push_range and constructors taking std::from_range:
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
int main() {
std::vector<int> v = {1, 2, 3, 4};
std::stack<int> st(v.begin(), v.end()); // C++23: iterator-pair constructor
std::queue<int> q;
q.push_range(v); // C++23: push_range
std::cout << "stack top = " << st.top() << ", queue front = " << q.front() << '\n';
}Output (compiled with -std=c++23, GCC 15):
stack top = 4, queue front = 1The last element pushed (4) is on top of the stack, while the first (1) is at the front of the queue, exactly as LIFO and FIFO say.
Comparison
|
|
| |
|---|---|---|---|
Removal order | Newest first (LIFO) | Oldest first (FIFO) | Highest priority first |
Read the next element |
|
|
|
Insert / remove cost | O(1) / O(1) | O(1) / O(1) | O(log n) / O(log n) |
Default container |
|
|
|
Typical uses | Undo, brackets, expression evaluation, DFS, recursion simulation | BFS, task scheduling, buffering | Dijkstra, Prim, Huffman coding, scheduling, top-K, merging k sorted lists |
Common Mistakes
Calling
top()/front()/pop()on an empty adaptor. There is no check and no exception: it is undefined behavior. Always testempty()first.Writing
int x = st.pop();.pop()returnsvoid. Read withtop()/front(), thenpop().Using a reference after popping.
const auto& p = pq.top(); pq.pop(); use(p);is a bug.prefers to slot 0 of the underlying vector; afterpop()that slot holds a different element (the new top), or, if the queue had only one element, an object that has been destroyed (undefined behavior). Use the reference beforepop(), or make a copy:auto p = pq.top();.Expecting
priority_queue<int>to give the smallest first. The default is a max-heap; usestd::greater<int>for a min-heap.Writing the comparator the "natural" way round. For a min-heap of structs you return
a.key > b.key, not<.Trying to iterate over an adaptor with a range-based
for. Adaptors have nobegin()/end().Using
std::queue<int, std::vector<int>>. It compiles until you callpop(), which needspop_front(), and then fails.
Interview / GATE-Style Questions
Q1. Why does std::stack::pop() return void instead of the removed element?
For exception safety. If pop() removed the element and then returned it by value, an exception thrown while copying the return value would lose the element permanently. Separating top() and pop() means the element is only removed after you have safely read it. It also avoids a copy when you just want to discard the element.
Q2. What are the time complexities of push, pop and top for std::priority_queue? How long does it take to build one from n elements?
push and pop are O(log n); top is O(1). Building from n elements with the range constructor is O(n) (bottom-up heapify). Pushing n elements one by one is O(n log n).
Q3. What does this print? std::priority_queue<int, std::vector<int>, std::greater<int>> pq; push 5, 1, 8, 3; pop once; print top.
It is a min-heap, so the top is 1. After one pop, 1 is removed and the new top is 3.
Q4. A sequence 1, 2, 3, 4, 5 is pushed onto a stack in that order; pops may be interleaved with pushes. Is 4, 5, 3, 2, 1 a valid output? Is 4, 3, 5, 1, 2?
4 5 3 2 1 is valid: push 1–4, pop 4, push 5, pop 5, then pop 3, 2, 1. 4 3 5 1 2 is not valid: after popping 4, 3 and 5, the stack holds 2 on top of 1, so 1 cannot be popped before 2.
Q5. How can you implement a queue using two stacks, and what is the cost per operation?
Use an in stack for pushes and an out stack for pops. To pop, if out is empty, move every element from in to out (this reverses their order, putting the oldest on top), then pop from out. Each element is moved at most once, so every operation is O(1) amortized, although a single pop can take O(n).
Summary
stack,queueandpriority_queueare container adaptors: they wrap a sequence container and expose a restricted interface. They have no iterators.stackis LIFO (push/pop/top),queueis FIFO (push/pop/front/back); both default todequeand are O(1).priority_queueis a binary heap on avector: max-heap by default, min-heap withstd::greater; push/pop O(log n), top O(1).pop()returnsvoid, and accessing an empty adaptor is undefined behavior.C++23 adds iterator-pair constructors for
stack/queueandpush_rangefor all three.
Next, in set & map, we move to containers that keep their elements sorted automatically and let us search by key in O(log n).