SyntaxPilot
Courses/C++/Lesson 25

C++ · Lesson 25 of 40 · 10 min

STL 5: stack, queue, priority_queue

queued

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:

  1. Read the code left to right.
  2. An opening bracket (, [, {? Push it.
  3. 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.
  4. 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

  1. Back button: a browser goes home → search → product → cart; press Back twice.
  2. Reverse a word with a stack.
  3. Printer queue: jobs with page counts, one page a minute; print when each job finishes.
  4. 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

  1. Stack vs queue? Stack: LIFO, one end (push/top/pop). Queue: FIFO, add at the back, remove from the front.
  2. Why does pop() return void? So removal can't lose an element if copying it throws; read with top()/front() first.
  3. 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).
  4. 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.
  5. Complexity of priority_queue operations? top O(1); push, pop O(log n); building from n elements O(n).
  6. How do you make a min-heap in C++? priority_queue<int, vector<int>, greater<int>>, or push negated values.
  7. Find the k largest of n numbers. A min-heap of size k: O(n log k) time, O(k) memory.
  8. What is a container adaptor? A wrapper (stack, queue, priority_queue) that restricts an underlying container (deque / vector) to certain operations; no iterators.
  9. 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: read top() first. A stack has no [].
  • A stack served the ticket line backwards. A queue is FIFO: push at the back, front and pop at 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_queue is that heap: biggest on top by default; greater<T> makes a min-heap; pairs sort by first, then second.
  • 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.