Stacks, Queues and Other Containers

Beyond vectors and maps, the standard library has containers for specific jobs: std::deque and std::list for fast insertion at both ends or in the middle, and the adapters std::stack, std::queue and std::priority_queue for last-in-first-out, first-in-first-out and "most important first" processing.

Overview

Container	Good at
`std::vector`	Almost everything; adding/removing at the end
`std::deque`	Adding/removing at both ends
`std::list`	Inserting/removing anywhere when you hold an iterator; elements never move
`std::stack`	Last in, first out (LIFO)
`std::queue`	First in, first out (FIFO)
`std::priority_queue`	Always taking the largest (or smallest) element next

std::deque

C++

#include <deque>
#include <iostream>

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

Output

2 3 4 5 6 | d[2] = 4

std::stack

A stack only exposes its top element. A classic use is checking that brackets are balanced:

C++

#include <iostream>
#include <stack>
#include <string_view>

bool balanced(std::string_view 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 o = open.top();
            open.pop();
            if ((c == ')' && o != '(') || (c == ']' && o != '[') || (c == '}' && o != '{')) return false;
        }
    }
    return open.empty();
}

int main() {
    for (std::string_view s : {"{[()()]}", "([)]", "f(a[1], {b})", "(("}) {
        std::cout << s << ": " << (balanced(s) ? "balanced" : "not balanced") << '\n';
    }
}

Output

{[()()]}: balanced
([)]: not balanced
f(a[1], {b}): balanced
((: not balanced

Note that pop() returns nothing: read top() first, then pop().

std::queue

A queue serves elements in arrival order — print jobs, messages, breadth-first search:

C++

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

int main() {
    std::queue<std::string> line;
    line.push("Ana");
    line.push("Ben");
    line.push("Chloe");
    while (!line.empty()) {
        std::cout << "serving " << line.front() << '\n';
        line.pop();
    }
}

Output

serving Ana
serving Ben
serving Chloe

std::priority_queue

A priority queue always gives you the largest element first (it's a heap underneath). For "smallest first", pass std::greater as the comparison:

C++

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

struct Job {
    int priority;
    std::string name;
    bool operator<(const Job& other) const { return priority < other.priority; }
};

int main() {
    std::priority_queue<Job> jobs;
    jobs.push({2, "send newsletter"});
    jobs.push({9, "fix outage"});
    jobs.push({5, "review PR"});
    while (!jobs.empty()) {
        std::cout << jobs.top().priority << ' ' << jobs.top().name << '\n';
        jobs.pop();
    }

    std::priority_queue<int, std::vector<int>, std::greater<int>> smallest_first;
    for (int x : {7, 2, 9, 4}) smallest_first.push(x);
    std::cout << "smallest: " << smallest_first.top() << '\n';
}

Output

9 fix outage
5 review PR
2 send newsletter
smallest: 2

std::list

A doubly linked list: inserting or erasing anywhere is constant time if you already have an iterator there, and elements never move in memory. But it has no indexing, and its scattered nodes make it slow to traverse. Use it only when those properties really matter.

C++

#include <iostream>
#include <list>

int main() {
    std::list<int> l{1, 2, 4, 5};
    auto it = l.begin();
    std::advance(it, 2);        // move to the 4
    l.insert(it, 3);            // insert before it
    l.remove(5);
    l.reverse();
    for (int x : l) std::cout << x << ' ';
    std::cout << '\n';
}

Output

4 3 2 1

Choosing a container

Start with std::vector. Its contiguous memory makes it the fastest choice for most tasks, even some that look like they need a list. Switch only when you need something it can't do well: lookup by key (map), uniqueness (set), fast insertion at the front (deque), or a specific access pattern (stack, queue, priority queue).

Try it yourself

Simulate a supermarket checkout queue: customers arrive with a number of items, and each tick the cashier scans 3 items.

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

struct Customer {
    std::string name;
    int items;
};

int main() {
    std::queue<Customer> queue;
    queue.push({"Ana", 5});
    queue.push({"Ben", 2});
    queue.push({"Chloe", 7});
    int tick = 0;
    while (!queue.empty()) {
        ++tick;
        Customer& c = queue.front();
        c.items -= 3;
        if (c.items <= 0) {
            std::cout << "tick " << tick << ": " << c.name << " done\n";
            queue.pop();
        }
    }
}

Edit the code, copy it into main.cpp, then compile and run it with c++ -std=c++20 -Wall main.cpp -o main && ./main. How to set up a C++ compiler

Output

tick 2: Ana done
tick 3: Ben done
tick 6: Chloe done

PreviousMaps and Sets NextIterators