C++ · Advanced

Stack, Queue and Priority Queue in C++

In short: std::stack, std::queue and std::priority_queue are container adaptors: restricted interfaces over an underlying container. A stack hands back the most recently pushed element, a queue the earliest, and a priority_queue the largest according to a comparison, with logarithmic push and pop. Choose by which element you need next.

Three answers to which element comes next

Many problems only ever need the next element in a particular sense: the most recent for undo and matching, the oldest for fair scheduling, the most important for a work queue. The three adaptors in <stack> and <queue> give exactly that and nothing else, which makes intent obvious and prevents the accidental access from the middle that a raw std::vector would allow.

std::stack<T> is last in, first out. push adds on top, top reads the top element and pop removes it. pop returns nothing: read with top, then pop. It is built on a std::deque by default, and both operations take constant time. std::queue<T> is first in, first out: push adds at the back, front reads the oldest element and pop removes it; back reads the newest. A depth-first search and a chain of recursive calls behave like a stack; a breadth-first search and a ticket counter behave like a queue.

std::priority_queue<T> keeps its elements as a binary heap inside a std::vector and top always returns the largest. Push and pop take logarithmic time; top is constant. Largest means largest according to <, so std::priority_queue<int> yields the biggest number first. For the smallest first, give the comparison std::greater<T> as the third template argument and the container as the second: std::priority_queue<int, std::vector<int>, std::greater<int>>. For your own struct, either define operator< for it, as the repair example does, or pass a comparator type. The heap orders elements only by that comparison, so ties come out in an unspecified order unless the comparison breaks them, which is why the example compares names as a second key.

None of the three can be iterated or indexed; to see everything you pop until empty(), which destroys the contents. All three provide size() and empty(), and calling top, front or pop on an empty adaptor is undefined behaviour, so check empty() first. emplace constructs the element in place from constructor arguments, saving a temporary.

A std::vector with push_back, back and pop_back is also a fine stack, and a std::deque a fine queue; the adaptors add no speed, only a narrower interface that states what the code needs.

Syntax

#include <queue>      // std::queue and std::priority_queue
#include <stack>

std::stack<int> s;
s.push(4);  s.push(9);
s.top();               // 9, the most recent
s.pop();               // removes 9, returns nothing

std::queue<std::string> q;
q.push("a");  q.push("b");
q.front();             // "a", the oldest
q.back();              // "b", the newest
q.pop();               // removes "a"

std::priority_queue<int> big;                                      // largest on top
std::priority_queue<int, std::vector<int>, std::greater<int>> small; // smallest on top
big.push(3);  big.top();  big.pop();

while (!s.empty()) { use(s.top()); s.pop(); }   // the only way to walk one

Each adaptor takes the underlying container as an optional template argument; the defaults (std::deque for stack and queue, std::vector for priority_queue) are right for almost every use.

An undo history on a stack

Items added to a shopping list, with undo removing the most recent addition. The final loop shows the stack from top to bottom.

#include <iostream>
#include <stack>
#include <string>

int main() {
    std::stack<std::string> history;    // the most recent addition is on top
    std::string op, item;
    while (std::cin >> op) {
        if (op == "add") {
            std::cin >> item;
            history.push(item);
        } else if (op == "undo") {
            if (history.empty()) {
                std::cout << "nothing to undo\n";
            } else {
                std::cout << "removed " << history.top() << "\n";
                history.pop();          // pop() discards; it returns nothing
            }
        }
    }
    std::cout << history.size() << " items, newest first:\n";
    while (!history.empty()) {
        std::cout << history.top() << "\n";
        history.pop();
    }
    return 0;
}

nothing to undo
removed yeast
removed butter
3 items, newest first:
eggs
salt
flour

Each undo removes whatever was pushed last, which is exactly the meaning of undo, and the empty() check protects the first one. top is read before pop because pop discards without returning. Printing the remaining items requires popping them, so afterwards the stack is empty; a program that needed the list again would copy the stack first or use a vector.

Max-heap, min-heap and a custom ordering

The same five numbers in a max-heap and a min-heap, then repair jobs ordered by urgency with alphabetical tie-breaking through operator<.

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

struct Repair {
    int urgency;
    std::string machine;
};

// The element that compares "largest" is the one top() returns.
bool operator<(const Repair& a, const Repair& b) {
    if (a.urgency != b.urgency) return a.urgency < b.urgency;
    return a.machine > b.machine;     // same urgency: alphabetically first wins
}

int main() {
    std::priority_queue<int> highest;                                     // largest on top
    std::priority_queue<int, std::vector<int>, std::greater<int>> lowest; // smallest on top
    for (int v : {40, 15, 72, 15, 33}) {
        highest.push(v);
        lowest.push(v);
    }
    std::cout << "max-heap top " << highest.top() << ", min-heap top " << lowest.top() << "\n";

    std::priority_queue<Repair> jobs;
    int n;
    std::cin >> n;
    for (int i = 0; i < n; ++i) {
        Repair r;
        std::cin >> r.urgency >> r.machine;
        jobs.push(r);
    }
    while (!jobs.empty()) {
        std::cout << jobs.top().urgency << " " << jobs.top().machine << "\n";
        jobs.pop();
    }
    return 0;
}

max-heap top 72, min-heap top 15
5 crane
5 press
3 kiln
2 lathe
1 mixer

std::greater<int> reverses the ordering so 15 sits on top of the second heap. For Repair, the heap needs <; the function says a job with lower urgency is less, and among equal urgency the one with the alphabetically later name is less, so crane beats press. Without that second rule the two urgency-5 jobs could come out in either order.

Which adaptor?

Common mistakes

• Reading or popping from an empty adaptor

  Why it goes wrong: top(), front() and pop() do no checking; on an empty container they are undefined behaviour, typically a crash or a garbage value.

  Fix: Test empty() before every read that might find nothing.

   C++ · fixCopy

  if (!s.empty()) { use(s.top()); s.pop(); }

• Expecting pop() to return the removed element

  Why it goes wrong: pop() returns void in all three adaptors, so int x = s.pop(); does not compile.

  Fix: Read with top() or front() first, then call pop().

• Getting the priority_queue direction backwards

  Why it goes wrong: The default is a max-heap: std::priority_queue<int> gives the largest first. Writing std::less to get the smallest changes nothing, because std::less is already the default.

  Fix: Use std::greater<T> as the third template argument for a min-heap, and remember to write the container argument before it.

• Trying to iterate a stack or priority_queue

  Why it goes wrong: The adaptors deliberately provide no begin() or end(), so a range-for over them does not compile.

  Fix: Pop in a loop, working on a copy if the contents are still needed, or use a vector when you need both stack access and iteration.

Where you use this

A stack is the tool whenever the most recent item must be dealt with first: undo history, matching opening and closing brackets or tags, tracking the path while exploring a maze, and evaluating expressions. A queue is the tool for fairness and for level-by-level exploration: breadth-first search over a grid of cells finds the shortest route because it examines all cells one step away before any cell two steps away.

A priority queue turns always take the best remaining option into two lines of code: the next job by urgency, the next event by time in a simulation, the nearest unvisited node in a shortest-path search. Push candidates as you discover them and pop the winner; the heap keeps the ordering in logarithmic time where a sorted vector would pay linear time per insertion.

std::queue<std::pair<int, int>> frontier;   // breadth-first search over a grid
frontier.push({startRow, startCol});
while (!frontier.empty()) {
    auto [r, c] = frontier.front();
    frontier.pop();
    // for each unvisited neighbour: mark it, frontier.push(neighbour)
}

Key points

• std::stack: push, top, pop; last in, first out.
• std::queue: push, front, back, pop; first in, first out.
• std::priority_queue: push, top, pop; largest by < first, logarithmic push and pop.
• For a min-heap write std::priority_queue<T, std::vector<T>, std::greater<T>>.
• pop returns nothing, and every read on an empty adaptor is undefined behaviour: check empty().
• Adaptors cannot be iterated; pop to see the contents, or keep a vector if you need both.

Try it yourself

The program prints the two largest numbers from the input using a priority queue. Change the queue so it is a min-heap and the program prints the two smallest instead: for 9 4 7 1 8 it should print 1 and then 4.

#include <functional>
#include <iostream>
#include <queue>
#include <vector>

int main() {
    std::priority_queue<int> pq;   // change this to a min-heap
    int x;
    while (std::cin >> x) pq.push(x);
    for (int i = 0; i < 2 && !pq.empty(); ++i) {
        std::cout << pq.top() << "\n";
        pq.pop();
    }
    return 0;
}

#include <functional>
#include <iostream>
#include <queue>
#include <vector>

int main() {
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
    int x;
    while (std::cin >> x) pq.push(x);
    for (int i = 0; i < 2 && !pq.empty(); ++i) {
        std::cout << pq.top() << "\n";
        pq.pop();
    }
    return 0;
}

Practise this

Exercises for this lesson are in the C++ practice set.

Open the C++ playground

Related lessons

• Vectors in C++ (std::vector)How std::vector works in C++: creating and growing a vector, indexing with [] and at(), passing vectors to functions, erasing elements and building 2D grids.11 minCompleted
• Maps and Sets in C++How std::map and std::set store sorted keys in C++, how [] and find differ, how to count and look up safely, and when unordered_map is the better choice.12 minCompleted

Frequently asked questions

How this page was checked. Every program on it was run with GCC 13 (C++17) at build time by the publishing checks, and the output shown is what it printed. Running C++ inside the browser is not available yet, so the Run button is absent rather than pretending; copy the code and run it with GCC 13 (C++17) locally.