C++ course menu

C++ stack, queue, deque and priority_queue Explained

Learn the C++ container adaptors: std::stack (LIFO) with balanced brackets and undo, std::queue (FIFO) with a task queue and BFS, std::deque, and std::priority_queue as a max-heap or min-heap with custom comparators.

Intermediate14 min readUpdated October 23, 2026

On this page

std::stack: last in, first out
Checking balanced brackets
std::queue: first in, first out
Breadth-first search
std::deque: both ends
std::priority_queue: most important first
A min-heap
Priorities with pairs
Summary
Common mistakes
Practice
Key takeaway

Some problems need elements processed in a particular order: the most recent first (undo history), the oldest first (a print queue), or the most important first (an emergency room). C++ provides three container adaptors for these: std::stack, std::queue and std::priority_queue. They wrap another container and expose only the operations that make sense.

std::stack: last in, first out#

A stack is like a pile of plates: you add to the top and take from the top.

C++

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

int main() {
    std::stack<std::string> history;
    history.push("open file");
    history.push("type text");
    history.push("bold text");

    std::cout << "Undo: " << history.top() << '\n';
    history.pop();
    std::cout << "Undo: " << history.top() << '\n';
    history.pop();
    std::cout << history.size() << " action left\n";
}

Output

Undo: bold text
Undo: type text
1 action left

Method	Meaning
`push(x)`	Add `x` on top
`top()`	Look at the top element
`pop()`	Remove the top element (returns nothing)
`empty()`, `size()`	Check the stack

pop() does not return the element; read it with top() first. Calling top() or pop() on an empty stack is undefined behaviour.

Checking balanced brackets#

Brackets must close in the reverse order they were opened, which is exactly what a stack tracks:

C++

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

bool balanced(const std::string& text) {
    std::stack<char> open;
    for (char c : text) {
        if (c == '(' || c == '[' || c == '{') {
            open.push(c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (open.empty()) return false;
            char expected = c == ')' ? '(' : c == ']' ? '[' : '{';
            if (open.top() != expected) return false;
            open.pop();
        }
    }
    return open.empty();
}

int main() {
    std::cout << std::boolalpha;
    std::cout << balanced("{[()()]}") << ' ' << balanced("([)]") << ' ' << balanced("((") << '\n';
}

Output

true false false

std::queue: first in, first out#

A queue is like a line at a ticket counter: join at the back, leave from the front.

C++

#include <iostream>
#include <queue>
#include <string>

int main() {
    std::queue<std::string> printer;
    printer.push("report.pdf");
    printer.push("photo.jpg");
    printer.push("invoice.pdf");

    while (!printer.empty()) {
        std::cout << "Printing " << printer.front() << '\n';
        printer.pop();
    }
}

Output

Printing report.pdf
Printing photo.jpg
Printing invoice.pdf

push adds to the back, front() reads the next element, back() reads the newest, and pop() removes from the front.

Breadth-first search#

Queues power breadth-first search (BFS), which explores a graph level by level and finds the shortest path in an unweighted graph:

C++

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

int main() {
    // adjacency list: node -> neighbours
    std::vector<std::vector<int>> graph = {{1, 2}, {3}, {3, 4}, {5}, {5}, {}};

    std::vector<int> distance(graph.size(), -1);
    std::queue<int> q;
    distance[0] = 0;
    q.push(0);

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        for (int next : graph[node]) {
            if (distance[next] == -1) {
                distance[next] = distance[node] + 1;
                q.push(next);
            }
        }
    }

    for (std::size_t i = 0; i < distance.size(); ++i) {
        std::cout << "node " << i << ": " << distance[i] << " steps\n";
    }
}

Output

node 0: 0 steps
node 1: 1 steps
node 2: 1 steps
node 3: 2 steps
node 4: 2 steps
node 5: 3 steps

std::deque: both ends#

std::deque (double-ended queue) is a full container, not an adaptor. It supports fast push_front, push_back, pop_front and pop_back, plus indexing. std::stack and std::queue use a deque underneath by default.

C++

#include <deque>
#include <iostream>

int main() {
    std::deque<int> d = {2, 3};
    d.push_front(1);
    d.push_back(4);
    d.pop_front();
    for (int x : d) std::cout << x << ' ';
    std::cout << "| front " << d.front() << ", d[1] " << d[1] << '\n';
}

Output

2 3 4 | front 2, d[1] 3

std::priority_queue: most important first#

A priority queue always gives you the largest element first, whatever order elements were added in. It is implemented as a heap: push and pop are O(log n), and top is O(1):

C++

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;
    for (int x : {30, 10, 50, 20, 40}) pq.push(x);

    while (!pq.empty()) {
        std::cout << pq.top() << ' ';
        pq.pop();
    }
    std::cout << '\n';
}

Output

50 40 30 20 10

A min-heap#

To get the smallest first, pass std::greater as the comparator. The full type needs the underlying container too:

C++

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

int main() {
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
    for (int x : {30, 10, 50, 20, 40}) min_heap.push(x);

    std::cout << "smallest: " << min_heap.top() << '\n';
}

Output

smallest: 10

Priorities with pairs#

Pairs compare by their first element, then the second, so {priority, name} pairs work directly:

C++

#include <iostream>
#include <queue>
#include <string>
#include <utility>

int main() {
    std::priority_queue<std::pair<int, std::string>> er;   // higher number = more urgent
    er.push({2, "sprained ankle"});
    er.push({5, "chest pain"});
    er.push({1, "small cut"});
    er.push({4, "high fever"});

    while (!er.empty()) {
        auto [priority, patient] = er.top();
        er.pop();
        std::cout << priority << ' ' << patient << '\n';
    }
}

Output

5 chest pain
4 high fever
2 sprained ankle
1 small cut

A classic interview use: keep the k largest elements of a stream in a min-heap of size k, popping the smallest whenever it grows past k.

Summary#

Adaptor	Order	Add	Look	Remove
`std::stack`	Last in, first out	`push`	`top`	`pop`
`std::queue`	First in, first out	`push`	`front` / `back`	`pop`
`std::priority_queue`	Largest first (by default)	`push`	`top`	`pop`

Adaptors have no iterators: you cannot loop over them with a range-based for. If you need to see every element, use the underlying container (a vector or deque) directly.

Common mistakes#

Practice#

Practice exercise

Using a min-heap of size 3, find the 3 largest values in {12, 45, 7, 89, 23, 56, 34} and print them from largest to smallest.

Show solution

C++

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

int main() {
    std::vector<int> values = {12, 45, 7, 89, 23, 56, 34};
    std::priority_queue<int, std::vector<int>, std::greater<int>> top3;

    for (int v : values) {
        top3.push(v);
        if (top3.size() > 3) top3.pop();   // drop the smallest
    }

    std::vector<int> result;
    while (!top3.empty()) {
        result.push_back(top3.top());
        top3.pop();
    }
    std::reverse(result.begin(), result.end());

    for (int x : result) std::cout << x << ' ';
    std::cout << '\n';
}

Output

89 56 45

This works in O(n log k), and uses memory for only k elements, which matters when the data is huge or arrives as a stream.

Key takeaway#

Finished this lesson?

C++The C++ Standard Template Library (STL): Containers, Iterators and AlgorithmsAn overview of the C++ STL: the three building blocks (containers, iterators, algorithms), sequence vs associative vs unordered containers, container adaptors, how to choose the right container, and Big-O costs of common operations.Intermediate6 min read C++C++ std::vector: Dynamic Arrays Explained with ExamplesLearn std::vector, C++'s most used container: creating vectors, push_back and emplace_back, accessing with [] and at(), size and capacity, inserting and erasing, sorting, removing elements safely, vectors of strings and objects, and passing vectors to functions.Beginner12 min read C++C++ STL Algorithms: sort, find, count, accumulate, transform and MoreLearn the most useful C++ <algorithm> and <numeric> functions: sort with custom comparators, stable_sort, find and find_if, count_if, any_of/all_of, min_element and max_element, accumulate, transform, remove_if with erase, binary_search, reverse, unique, and C++20 ranges.Intermediate14 min read

Practice: C++ STL exercises →

std::stack: last in, first out#

Checking balanced brackets#

std::queue: first in, first out#

Breadth-first search#

std::deque: both ends#

std::priority_queue: most important first#

A min-heap#

Priorities with pairs#

Summary#

Common mistakes#

Practice#

Key takeaway#

Related lessons