These are the notes for C++ episode 25, the fifth STL episode. In episodes 23 and 24 you invented trees and hash tables to find anything fast. Here you don't search at all: sometimes you only ever need one item, the last one, the first one, or the most urgent one. You will invent three tools for that: std::stack, std::queue and std::priority_queue (and the heap inside it). Every example below was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13.3, the same command as the SyntaxPilot compiler) and run; outputs and error messages are copied from those runs. Timings change from run to run and machine to machine; compare the ratios.
The problem: the undo button
You type "Hello" in a notes app, make it bold, then delete a line by mistake. You press undo and the line comes back. Undo always takes back the last thing you did, not the first. Let's keep that history in a vector:
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main() {
vector<string> history;
history.push_back("type Hello");
history.push_back("make it bold");
history.push_back("delete a line");
// a teammate writes the Undo button:
cout << "Undo: " << history.front() << endl;
history.erase(history.begin());
return 0;
}
Output:
Undo: type Hello
Wrong: the user wanted the deleted line back, and their very first word disappeared.
Why: a vector lets anyone touch any element at any end. Nothing stopped a teammate from undoing the wrong end. We want a container that only allows the last item, so the wrong undo can't even be written.
Step 1: the stack, last in first out
Real-life example: the plates at a wedding buffet. A clean plate always goes on top (push). A guest always takes the top plate (top, then pop). Nobody pulls a plate from the bottom.
| At the buffet | In C++ (#include <stack>) |
|---|---|
| put a plate on the pile | s.push(x) |
| look at the top plate | s.top() |
| take the top plate away | s.pop() (returns nothing) |
| how many plates / no plates? | s.size() / s.empty() |
This rule is LIFO: last in, first out. All of these operations are O(1).
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main() {
stack<string> history;
history.push("type Hello");
history.push("make it bold");
history.push("delete a line");
cout << "Undo: " << history.top() << endl;
history.pop();
cout << "Undo: " << history.top() << endl;
history.pop();
cout << "Left: " << history.size() << ", empty? "
<< (history.empty() ? "yes" : "no") << endl;
return 0;
}
Output:
Undo: delete a line
Undo: make it bold
Left: 1, empty? no
The last action is undone first, every time.
Two traps that can't compile
A stack has no index, on purpose:
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main() {
stack<string> history;
history.push("type Hello");
cout << history[0] << endl; // the oldest one?
return 0;
}
g++ says:
main.cpp:9:20: error: no match for ‘operator[]’ (operand types are ‘std::stack<std::__cxx11::basic_string<char> >’ and ‘int’)
And pop() only removes; it returns void (nothing):
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main() {
stack<string> history;
history.push("type Hello");
string last = history.pop(); // take it AND remove it?
return 0;
}
g++ says:
main.cpp:9:30: error: conversion from ‘void’ to non-scalar type ‘std::string’ {aka ‘std::__cxx11::basic_string<char>’} requested
Always read top() first, then pop(). (Why doesn't pop return the item? Returning a copy could fail half way for some types, after the item was already removed; splitting the two keeps it safe.)
Step 2: a stack checks your brackets
Every time your compiler says a bracket is missing, a stack is at work:
- Read the code left to right.
- An opening bracket
(,[,{? Push it. - A closing bracket? It must match the bracket on top (the most recent one still open). Pop it. A wrong pair, or nothing open, means broken.
- At the end the stack must be empty, or something was never closed.
#include <iostream>
#include <stack>
#include <string>
using namespace std;
bool balanced(string code) {
stack<char> open;
for (char c : code) {
if (c == '(' || c == '[' || c == '{') open.push(c);
else if (c == ')' || c == ']' || c == '}') {
if (open.empty()) return false; // nothing to close
char o = open.top();
open.pop();
if ((c == ')' && o != '(') || (c == ']' && o != '[') ||
(c == '}' && o != '{')) return false; // wrong pair
}
}
return open.empty(); // anything left open?
}
int main() {
cout << "{ a[i] = f(x); } " << balanced("{ a[i] = f(x); }") << endl;
cout << "{ a[i) = f(x]; } " << balanced("{ a[i) = f(x]; }") << endl;
cout << "if ((x > 1) " << balanced("if ((x > 1)") << endl;
return 0;
}
Output:
{ a[i] = f(x); } 1
{ a[i) = f(x]; } 0
if ((x > 1) 0
Step 3: the ticket counter, where a stack fails
Asha arrives first at the railway ticket counter, then Ravi, then Meena. Reuse the stack?
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main() {
stack<string> line; // the counter, with a stack
line.push("Asha"); // came first
line.push("Ravi");
line.push("Meena"); // came last
cout << "Serving: " << line.top() << endl;
return 0;
}
Output:
Serving: Meena
Meena came last and is served first; Asha, who waited longest, is still waiting. A line needs the opposite rule.
Step 4: the queue, first in first out
FIFO: first in, first out. Join at the back, leave from the front.
| At the counter | In C++ (#include <queue>) |
|---|---|
| join the line | q.push(x) (at the back) |
| who's next? | q.front() |
| who's last? | q.back() |
| next person leaves | q.pop() (from the front, returns nothing) |
size(), empty() |
as usual |
#include <iostream>
#include <queue>
#include <string>
using namespace std;
int main() {
queue<string> line;
line.push("Asha"); // joins at the back
line.push("Ravi");
line.push("Meena");
cout << "First: " << line.front() << ", last: " << line.back() << endl;
while (!line.empty()) {
cout << "Serving: " << line.front() << endl;
line.pop(); // leaves from the front
}
return 0;
}
Output:
First: Asha, last: Meena
Serving: Asha
Serving: Ravi
Serving: Meena
Fair. Printers, ticket counters, messages in a chat server and tasks waiting for a CPU all use queues.
Step 5: the emergency ward, where a queue fails
Each patient gets a severity from 1 to 10. A severity-9 patient goes first even if they came last, so a queue is unfair the other way. And a big city hospital sees 30000 patients. The obvious way: a vector, and each time find the most severe with max_element (from <algorithm>; it returns an iterator to the biggest element).
#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
using namespace std;
using namespace std::chrono;
int main() {
vector<int> ward; // severity of each patient
for (int i = 0; i < 30000; i++) ward.push_back(i * 7919 % 1000);
auto start = steady_clock::now();
long long treated = 0;
while (!ward.empty()) {
auto worst = max_element(ward.begin(), ward.end()); // scan all
treated += *worst;
ward.erase(worst);
}
auto end = steady_clock::now();
cout << "vector: all treated in "
<< duration_cast<milliseconds>(end - start).count() << " ms" << endl;
return 0;
}
Output:
vector: all treated in 2224 ms
Over a second. Every pick scans everyone (n steps), then erase shifts everyone after them. 30000 picks × 30000 ≈ a billion steps: O(n²).
We don't need the whole ward sorted. We only ever need the most urgent one, quickly, again and again.
Step 6: inventing the heap
Picture a company's org chart with one rule: every boss outranks the people in their team. Nobody cares how two teammates compare.
[ 9 ] <- top: outranks everyone
/ \
[ 7 ] [ 5 ]
/ \
[ 1 ] [ 3 ]
stored in a vector, level by level: 9 7 5 1 3
children of index i: 2i+1 and 2i+2; parent of i: (i-1)/2
- Follow the rule upward and the person at the very top outranks everyone. No searching: top() is O(1).
- pop: the top leaves. The stronger of the two deputies moves up, then the stronger of their deputies fills that gap, down one path: about log₂ n moves (≈ 15 for 30000).
- push: a new person joins at the bottom and keeps getting promoted while they outrank their boss: one path again, O(log n).
- A tree with this rule (every parent ≥ its children) is a heap (a binary max-heap). It is stored in a plain vector, no links: the positions say who reports to whom.
You can watch the heap inside a vector with the <algorithm> heap functions:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> v = {3, 9, 5, 1, 7};
make_heap(v.begin(), v.end()); // arrange as a max-heap
cout << "heap in the vector: ";
for (int x : v) cout << x << " ";
cout << "\ntop: " << v.front() << endl;
v.push_back(8); // a new star joins at the bottom...
push_heap(v.begin(), v.end()); // ...and is promoted
cout << "after push 8, top: " << v.front() << endl;
pop_heap(v.begin(), v.end()); // move the top to the end, fix the rest
cout << "popped: " << v.back() << endl;
v.pop_back();
cout << "new top: " << v.front() << endl;
return 0;
}
Output:
heap in the vector: 9 7 5 1 3
top: 9
after push 8, top: 9
popped: 9
new top: 8
9 7 5 1 3 is exactly the org chart above. (Different compilers may arrange equal-ranked parts differently; the top is always the maximum.)
Step 7: priority_queue
priority_queue lives in <queue>. It's a heap with a friendly interface: push, top, pop, size, empty.
#include <iostream>
#include <queue>
#include <chrono>
using namespace std;
using namespace std::chrono;
int main() {
priority_queue<int> ward; // the most severe on top
for (int i = 0; i < 30000; i++) ward.push(i * 7919 % 1000);
auto start = steady_clock::now();
long long treated = 0;
while (!ward.empty()) {
treated += ward.top(); // the worst, instantly
ward.pop(); // about log n steps
}
auto end = steady_clock::now();
cout << "priority_queue: all treated in "
<< duration_cast<milliseconds>(end - start).count() << " ms" << endl;
return 0;
}
Output:
priority_queue: all treated in 2 ms
A few milliseconds against over a second: top is O(1), push and pop are O(log n), so 30000 patients cost about 30000 × 15 steps instead of a billion.
Patients with names: pairs
Pairs compare by first, and on a tie by second. Put the thing you sort by first:
#include <iostream>
#include <queue>
#include <string>
using namespace std;
int main() {
priority_queue<pair<int, string>> ward; // (severity, name)
ward.push({3, "Asha"});
ward.push({9, "Ravi"});
ward.push({5, "Meena"});
ward.push({9, "Kiran"});
while (!ward.empty()) {
cout << ward.top().second << " (severity "
<< ward.top().first << ")" << endl;
ward.pop();
}
return 0;
}
Output:
Ravi (severity 9)
Kiran (severity 9)
Meena (severity 5)
Asha (severity 3)
Ravi before Kiran: both severity 9, and on a tie the bigger second value ("Ravi" > "Kiran" alphabetically) is on top of a max-heap.
The smallest on top: a min-heap
By default the biggest is on top: a max-heap. A food delivery app wants the rider who is the fewest minutes away. Give three types: the element type, the container it is stored in (vector<int>), and the comparator greater<int>:
#include <iostream>
#include <queue>
#include <vector>
#include <functional>
using namespace std;
int main() {
priority_queue<int, vector<int>, greater<int>> eta; // smallest on top
eta.push(30); // minutes to deliver
eta.push(12);
eta.push(45);
eta.push(8);
cout << "Nearest rider: " << eta.top() << " min" << endl;
while (!eta.empty()) { cout << eta.top() << " "; eta.pop(); }
cout << endl;
return 0;
}
Output:
Nearest rider: 8 min
8 12 30 45
Shortest-route algorithms (Dijkstra, in episode 37 on graphs) and task schedulers run on min-heaps like this.
Your own ordering
For your own struct, write a comparator: a struct whose operator()(a, b) returns true when a should come out after b. (It feels backwards: the priority queue keeps the element that is "biggest" by your rule on top.)
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;
struct Order {
string item;
int minutes; // time left to deliver
};
struct Sooner { // "a comes after b" if a has MORE minutes left
bool operator()(const Order& a, const Order& b) const { return a.minutes > b.minutes; }
};
int main() {
priority_queue<Order, vector<Order>, Sooner> orders;
orders.push({"biryani", 25});
orders.push({"chai", 5});
orders.push({"thali", 15});
while (!orders.empty()) {
cout << orders.top().item << " (" << orders.top().minutes << " min)" << endl;
orders.pop();
}
return 0;
}
Output:
chai (5 min)
thali (15 min)
biryani (25 min)
Container adaptors
None of these three stores data in a new way. They adapt an existing container and only allow the right moves:
| Adaptor | Rule | Allowed moves | Built on (default) | Costs |
|---|---|---|---|---|
stack<T> |
LIFO | push, top, pop |
deque<T> |
all O(1) |
queue<T> |
FIFO | push (back), front, back, pop (front) |
deque<T> |
all O(1) |
priority_queue<T> |
biggest first | push, top, pop |
vector<T> (a heap) |
top O(1); push, pop O(log n) |
That's why they're called container adaptors, and why they have no iterators: you can't loop over them with a range-for; you top/front and pop until empty().
Common mistakes (and the real g++ messages)
| Mistake | What happens | Fix |
|---|---|---|
string last = history.pop(); |
error: conversion from ‘void’ to non-scalar type ‘std::string’ {aka ‘std::__cxx11::basic_string<char>’} requested |
string last = history.top(); history.pop(); |
history[0] on a stack |
error: no match for ‘operator[]’ (operand types are ‘std::stack<std::__cxx11::basic_string<char> >’ and ‘int’) |
use top(), or a vector if you need indexes |
q.top() on a queue |
error: ‘class std::queue<std::__cxx11::basic_string<char> >’ has no member named ‘top’; did you mean ‘pop’? |
q.front() |
top() / pop() on an empty container |
compiles; undefined behaviour (often a crash or garbage) | check if (!s.empty()) first |
| Expecting a priority_queue to give the smallest | gives the biggest (max-heap) | priority_queue<int, vector<int>, greater<int>> |
| Looping with range-for over an adaptor | compile error: no begin() |
while (!s.empty()) { ... s.pop(); } |
The queue error, for real:
#include <iostream>
#include <queue>
#include <string>
using namespace std;
int main() {
queue<string> q;
q.push("Asha");
cout << q.top() << endl;
return 0;
}
g++ says:
main.cpp:9:15: error: ‘class std::queue<std::__cxx11::basic_string<char> >’ has no member named ‘top’; did you mean ‘pop’?
Mini project: a bank token counter
Commands: join <name>, next (the counter calls the front of the line), recall (the last person served, from a stack), end.
#include <iostream>
#include <queue>
#include <stack>
#include <string>
using namespace std;
int main() {
queue<string> line; // the bank counter, first come first served
stack<string> served; // for "recall": the last person served
string cmd, name;
while (cin >> cmd && cmd != "end") {
if (cmd == "join") {
cin >> name;
line.push(name);
cout << name << " joined, waiting: " << line.size() << endl;
} else if (cmd == "next") {
if (line.empty()) { cout << "Nobody waiting" << endl; continue; }
cout << "Counter calls: " << line.front() << endl;
served.push(line.front());
line.pop();
} else if (cmd == "recall") {
if (served.empty()) cout << "Nobody served yet" << endl;
else cout << "Last served: " << served.top() << endl;
}
}
return 0;
}
Output:
Asha joined, waiting: 1
Ravi joined, waiting: 2
Counter calls: Asha
Meena joined, waiting: 2
Last served: Asha
Counter calls: Ravi
Counter calls: Meena
Nobody waiting
(Input typed into the program's input box: join Asha, join Ravi, next, join Meena, recall, next, next, next, end.)
Extensions: a vip <name> command that is served before everyone else (hint: a priority_queue<pair<int, int>> of (priority, arrival number), or a second queue checked first).
Practice
- Back button: a browser goes home → search → product → cart; press Back twice.
- Reverse a word with a stack.
- Printer queue: jobs with page counts, one page a minute; print when each job finishes.
- Top 3 scores using a small min-heap (an interview favourite: top k in O(n log k)).
Solutions
1. Before moving to a new page, push the current one; Back pops it.
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main() {
stack<string> back;
string current = "home";
for (string page : {"search", "product", "cart"}) {
back.push(current); // remember where we were
current = page;
}
cout << "On: " << current << endl;
for (int i = 0; i < 2; i++) { // press Back twice
current = back.top();
back.pop();
cout << "Back to: " << current << endl;
}
return 0;
}
Output:
On: cart
Back to: product
Back to: search
2. Push every letter, pop them all: they come out last-first.
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main() {
string word = "SyntaxPilot";
stack<char> s;
for (char c : word) s.push(c);
string reversed;
while (!s.empty()) { reversed += s.top(); s.pop(); }
cout << reversed << endl;
return 0;
}
Output:
toliPxatnyS
3.
#include <iostream>
#include <queue>
#include <string>
using namespace std;
int main() {
queue<pair<string, int>> printer; // (file, pages)
printer.push({"notes.pdf", 4});
printer.push({"ticket.pdf", 1});
printer.push({"report.pdf", 12});
int minute = 0;
while (!printer.empty()) {
auto job = printer.front();
printer.pop();
minute += job.second; // one page a minute
cout << job.first << " done at minute " << minute << endl;
}
return 0;
}
Output:
notes.pdf done at minute 4
ticket.pdf done at minute 5
report.pdf done at minute 17
4. Keep a min-heap of at most 3 scores: whenever it grows to 4, pop the smallest. What's left are the 3 biggest. Each step is O(log 3), so the whole thing is O(n).
#include <iostream>
#include <queue>
#include <vector>
#include <functional>
using namespace std;
int main() {
vector<int> scores = {45, 99, 12, 72, 88, 60, 95};
priority_queue<int, vector<int>, greater<int>> top3; // a min-heap of size 3
for (int s : scores) {
top3.push(s);
if (top3.size() > 3) top3.pop(); // drop the smallest of the four
}
cout << "Top 3 (smallest first): ";
while (!top3.empty()) { cout << top3.top() << " "; top3.pop(); }
cout << endl;
return 0;
}
Output:
Top 3 (smallest first): 88 95 99
Quick quiz
What does this print?
stack<int> s;
s.push(1);
s.push(2);
s.push(3);
s.pop();
s.push(4);
cout << s.top() << " " << s.size();
Answer
4 3. After pushing 1, 2, 3, pop() removes the top, 3. Then 4 goes on top. The stack holds 1, 2, 4: three plates, 4 on top.
Interview questions
- Stack vs queue? Stack: LIFO, one end (
push/top/pop). Queue: FIFO, add at the back, remove from the front. - Why does
pop()returnvoid? So removal can't lose an element if copying it throws; read withtop()/front()first. - How do you check balanced brackets? Push openers on a stack; each closer must match the top; the stack must be empty at the end. O(n).
- What is a heap? How is it stored? A complete binary tree where every parent ≥ its children (max-heap), stored in an array: children of i at 2i+1 and 2i+2.
- Complexity of
priority_queueoperations?topO(1);push,popO(log n); building from n elements O(n). - How do you make a min-heap in C++?
priority_queue<int, vector<int>, greater<int>>, or push negated values. - Find the k largest of n numbers. A min-heap of size k: O(n log k) time, O(k) memory.
- What is a container adaptor? A wrapper (
stack,queue,priority_queue) that restricts an underlying container (deque/vector) to certain operations; no iterators. - Implement a queue using two stacks. Push into stack A; to pop, if B is empty move everything from A to B, then pop B. Amortised O(1).
Glossary
| Term | Meaning, with an example |
|---|---|
stack |
A container adaptor where you only touch the top: undo history, stack<string> history; |
| LIFO | Last in, first out: the last plate put on the pile is the first taken. |
push |
Add an element (top of a stack, back of a queue, into a heap). |
top() |
The top element of a stack, or the biggest (by its order) in a priority_queue. |
pop() |
Remove the top / front element; returns nothing. |
queue |
A container adaptor: join at the back, leave from the front: a ticket line. |
| FIFO | First in, first out: whoever came first is served first. |
front(), back() |
The next and the last element of a queue. |
priority_queue |
A container adaptor that always gives the most important element first, built on a heap. |
| heap (binary max-heap) | A tree stored in a vector where every parent is ≥ its children, so the top is the maximum. |
| min-heap | A heap where every parent is ≤ its children, so the top is the minimum. |
greater<int> |
A comparator that means "bigger comes later"; it turns a priority_queue into a min-heap. |
| comparator | A function object deciding the order of elements. |
| container adaptor | A wrapper that limits an existing container to certain operations. |
max_element |
<algorithm> function returning an iterator to the biggest element of a range; it scans every element. |
make_heap, push_heap, pop_heap |
<algorithm> functions that keep a vector arranged as a heap. |
| undefined behaviour | Code whose result C++ doesn't define, like top() on an empty stack: it may crash or print garbage. |
| balanced brackets | Every opening bracket closed by the matching kind, in the right order. |
| O(n²) | Work that grows with the square of n: 30000 → about a billion steps. |
| triage | Sorting patients by urgency; here, a max-heap of severities. |
Summary
- A vector let someone undo the wrong end. A stack allows only the top: LIFO,
push/top/pop, all O(1). It also checks brackets. pop()returns nothing: readtop()first. A stack has no[].- A stack served the ticket line backwards. A queue is FIFO:
pushat the back,frontandpopat the front. - Scanning a vector for the most urgent patient is O(n) per pick. A heap keeps a loose order (every boss above their team): top in O(1), push and pop in O(log n).
priority_queueis that heap: biggest on top by default;greater<T>makes a min-heap; pairs sort byfirst, thensecond.- Stack, queue and priority_queue are container adaptors over
deque/vector, with no iterators.
Next episode: you've met vector, deque, list, map, set, the hash tables and three adaptors. They're all different inside, so how can one loop and one sort work on most of them? Iterators.