These three are not containers. They are adaptors — thin wrappers that take an existing container and expose a smaller interface.

That is the point. A std::stack is a std::deque with most of its operations removed, so that the type itself says "this is a stack" and the compiler enforces it.

The three

#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <vector>

int main() {
    std::stack<int> s;
    s.push(1);
    s.push(2);
    s.push(3);
    std::cout << "stack top " << s.top() << ", size " << s.size() << "\n";
    while (!s.empty()) {
        std::cout << s.top() << " ";
        s.pop();                       // pop() returns void — see below
    }
    std::cout << "\n";

    std::queue<std::string> q;
    q.push("first");
    q.push("second");
    q.push("third");
    std::cout << "queue front " << q.front() << ", back " << q.back() << "\n";
    while (!q.empty()) {
        std::cout << q.front() << " ";
        q.pop();
    }
    std::cout << "\n";

    // priority_queue is a MAX heap by default: largest comes out first.
    std::priority_queue<int> pq;
    for (int x : {3, 1, 4, 1, 5, 9, 2, 6}) {
        pq.push(x);
    }
    std::cout << "max heap: ";
    while (!pq.empty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }
    std::cout << "\n";

    // Min heap: pass std::greater as the comparator.
    std::priority_queue<int, std::vector<int>, std::greater<int>> minpq;
    for (int x : {3, 1, 4, 1, 5, 9, 2, 6}) {
        minpq.push(x);
    }
    std::cout << "min heap: ";
    while (!minpq.empty()) {
        std::cout << minpq.top() << " ";
        minpq.pop();
    }
    std::cout << "\n";
    return 0;
}

stack top 3, size 3
3 2 1 
queue front first, back third
first second third 
max heap: 9 6 5 4 3 2 1 1 
min heap: 1 1 2 3 4 5 6 9

std::stack — last in, first out. push, pop, top, empty, size. That is all.

std::queue — first in, first out. push, pop, front, back, empty, size.

std::priority_queue — largest first, by default. Internally a binary heap: push and pop are O(log n), top is O(1).

Note the max-heap default catches people out. std::priority_queue<int> gives you the largest element first. For a min heap you must spell out all three template arguments, because the comparator is the third one:

std::priority_queue<int, std::vector<int>, std::greater<int>> minpq;

Why pop() returns nothing

Every one of these has pop() returning void, so you must write:

// int value = s.top();     // read
// s.pop();                 // then remove

rather than the obvious int value = s.pop();. That looks like an oversight and is a deliberate decision about exception safety (lesson 15.2).

Imagine pop() did return the element. It would have to:

1. Remove the element from the container.
2. Return a copy of it.

If step 2 throws — a copy constructor that allocates, on a machine out of memory — the element is already gone from the container and the copy never reached the caller. The value is destroyed and nobody has it. There is no way to recover.

Splitting into top() and pop() makes that impossible: top() returns a reference and cannot lose anything, and pop() returns nothing so it cannot throw on the way out.

This is a real design principle you will meet again: do not combine an operation that can fail with one that changes state, because there is nowhere to put the failure.

Choosing the underlying container

Each adaptor has a second template parameter naming the container it wraps:

// template <typename T, typename Container = std::deque<T>>       class stack;
// template <typename T, typename Container = std::deque<T>>       class queue;
// template <typename T, typename Container = std::vector<T>,
//           typename Compare = std::less<T>>                      class priority_queue;

std::deque backs stack and queue because it grows at either end without moving anything. priority_queue uses vector, because a heap needs random access.

You can substitute:

// std::stack<int, std::vector<int>> s;      // vector-backed: usually faster
// std::queue<int, std::list<int>> q;        // list-backed: stable references

A vector-backed stack is often measurably faster than the deque default, because a stack only ever grows at one end — which is exactly what a vector is good at. It is worth trying if a stack is on your hot path.

The requirement is just that the container provides the operations the adaptor uses: back, push_back, pop_back for a stack; those plus front and pop_front for a queue.

A custom priority

#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <vector>

struct Job {
    std::string name;
    int priority;
};

// Higher priority number comes out first, so "less than" means lower priority.
struct ByPriority {
    bool operator()(const Job& a, const Job& b) const { return a.priority < b.priority; }
};

int main() {
    std::priority_queue<Job, std::vector<Job>, ByPriority> jobs;
    jobs.push({"backup", 1});
    jobs.push({"alert", 9});
    jobs.push({"report", 5});
    jobs.push({"cleanup", 2});

    while (!jobs.empty()) {
        std::cout << jobs.top().name << "(" << jobs.top().priority << ") ";
        jobs.pop();
    }
    std::cout << "\n";

    // A stack backed by a vector instead of the default deque.
    std::stack<int, std::vector<int>> vs;
    vs.push(10);
    vs.push(20);
    std::cout << "vector-backed stack top: " << vs.top() << "\n";
    return 0;
}

alert(9) report(5) cleanup(2) backup(1) 
vector-backed stack top: 20

The comparator's direction is the thing to get right, and it reads backwards. std::priority_queue puts the greatest element on top according to the comparator, so a.priority < b.priority means "a is lower priority", and the highest number comes out first. Flip it to > and you get a lowest-first queue.

If you find yourself unsure, write it, run it with three elements, and look. That is faster than reasoning about it, and this lesson's own examples were checked that way.

What you cannot do, and why that is the feature

// std::stack<int> s;
// s[0];                    // no operator[]
// for (int x : s) { }      // no begin() or end()
// s.begin();               // does not exist

An adaptor has no iterators. You cannot loop over a stack, sort it, or use any algorithm on it.

That is not a limitation to work around — it is the interface saying what a stack is. If you need to iterate, you did not want a stack; you wanted a vector or a deque that you happen to be using in a stack-like way. Reach for the container directly.

The same reasoning applies to std::queue. If you need to inspect the middle of the queue, use a std::deque.

When to use them

std::stack — anything with nesting or backtracking: matching brackets, expression parsing, undo history, depth-first search, evaluating postfix notation.

std::queue — anything processed in arrival order: task queues, breadth-first search, producer/consumer buffers, request handling.

std::priority_queue — scheduling by urgency, Dijkstra's shortest path, A* search, merging sorted streams, "top k" problems.

The last of those is worth naming, because it is common and the naive approach is much worse: to find the 10 largest of a million values, keep a min-heap of size 10 and push each value, popping when the size exceeds 10. That is O(n log k) and uses O(k) memory, against sorting the whole million at O(n log n).

Try it

Checkpoint

• Adaptors wrap a container and expose a smaller interface, on purpose.
• stack is LIFO, queue is FIFO, priority_queue is a binary heap.
• std::priority_queue is a max heap by default; a min heap needs all three template arguments.
• pop() returns void so that a throwing copy cannot destroy an element nobody received.
• Never combine an operation that can fail with one that changes state.
• stack and queue are backed by deque; priority_queue by vector. All are substitutable.
• A vector-backed stack is often faster than the default.
• Adaptors have no iterators — if you need to iterate, you wanted the container.
• The priority_queue comparator reads backwards: a < b means a comes out later.
• For the k largest of n values, use a min heap of size k: O(n log k) and O(k) memory.