Skip to content

Intermediate · The Standard Template Library (STL) · topic 23 of 42 · 30 min

set, stack, queue, deque and priority_queue

Explanation

std::set keeps unique values in sorted order and std::unordered_set keeps unique values with hashing. stack (last in, first out), queue (first in, first out) and priority_queue (largest first) are adaptors built on other containers. deque allows fast adds and removes at both ends.

Sets: unique values

A set stores each value at most once. Adding a value that is already there does nothing. Like maps, std::set is a sorted tree (O(log n)) and std::unordered_set is a hash table (O(1) on average). Sets answer "have I seen this before?" quickly.

cpp
#include <iostream>
#include <set>

int main() {
    std::set<int> pins = {411001, 560001, 411001, 110001};
    std::cout << pins.size() << '\n';              // 3: duplicates removed
    for (int p : pins) std::cout << p << ' ';      // 110001 411001 560001
    std::cout << '\n' << pins.count(560001) << '\n';   // 1
    auto it = pins.lower_bound(400000);            // first value >= 400000
    std::cout << *it << '\n';                      // 411001
}
lower_bound on a set finds the first element that is not less than a value, in O(log n).
Careful: Use the member function pins.lower_bound(x), not std::lower_bound(pins.begin(), pins.end(), x). The free algorithm cannot jump around a tree and takes O(n) on a set; the member function uses the tree and takes O(log n).

stack: last in, first out

cpp
#include <stack>
std::stack<std::string> history;
history.push("home");
history.push("product");
history.push("cart");
std::cout << history.top() << '\n';   // cart
history.pop();                        // back button
std::cout << history.top() << '\n';   // product
A stack is like a pile of plates: you add and remove at the top. Used for undo, the back button, matching brackets and depth-first search.

queue: first in, first out

cpp
#include <queue>
std::queue<std::string> counter;
counter.push("Asha");
counter.push("Ravi");
std::cout << counter.front() << '\n';   // Asha is served first
counter.pop();
std::cout << counter.front() << '\n';   // Ravi
A queue is like the line at a ticket counter. Used for tasks waiting their turn and breadth-first search.

priority_queue: the most important first

cpp
#include <queue>
#include <vector>

std::priority_queue<int> pq;               // max-heap: largest on top
for (int x : {5, 1, 8, 3}) pq.push(x);
std::cout << pq.top() << '\n';             // 8

std::priority_queue<int, std::vector<int>, std::greater<int>> minPq;   // smallest on top
for (int x : {5, 1, 8, 3}) minPq.push(x);
std::cout << minPq.top() << '\n';          // 1
push and pop are O(log n); top is O(1). std::greater<int> turns it into a min-heap, used in Dijkstra's shortest path.
Think of it like this: A priority_queue is like a hospital emergency room: patients are not seen in arrival order but by how serious their case is. The most serious (the "largest") is always treated next.

deque and list

std::deque (double-ended queue, said "deck") allows O(1) push and pop at both the front and the back, and still allows indexing with []. std::list is a doubly linked list: O(1) insert and erase anywhere if you already have an iterator there, but no indexing and poor cache use. In practice, vector beats list for most jobs, even with some middle inserts, because contiguous memory is so fast.

Choosing a container

You needUse
A list, mostly adding at the end and reading by indexstd::vector
Fast lookup by key, sorted order neededstd::map / std::set
Fast lookup by key, order not neededstd::unordered_map / std::unordered_set
Undo, back button, brackets, DFSstd::stack
Waiting line, BFSstd::queue
Always take the largest (or smallest) nextstd::priority_queue
Add and remove at both endsstd::deque

pair and tuple

cpp
std::pair<std::string, int> topper{"Meena", 98};
std::cout << topper.first << ' ' << topper.second << '\n';
auto t = std::make_tuple("Pune", 411001, 7.2);
std::cout << std::get<1>(t) << '\n';   // 411001
pair holds two values, tuple holds any number. Pairs compare by first, then second, which is handy for sorting and priority queues.
Tip: stack, queue and priority_queue have no iterators and no way to look at elements other than the top or front. If you need to inspect everything, use the underlying container (vector or deque) directly.

Need help?

Stuck on a word or an idea? Search this course, or every course, and jump straight to the explanation or a worked question.

Try:

Watch the lesson

set, stack, queue, deque and priority_queue · 1/6

More containers

Beyond vector and map, the STL has sets, stacks, queues and priority queues.

Prefer a video by a teacher? Find free videos on “c++ stl set stack queue priority_queue deque tutorial” on YouTube ↗

In real life: Hospital token system

A clinic gives each patient a token with a severity score from 1 to 10. The doctor always calls the most severe case next; among equal scores, the earlier token first. A priority_queue of pairs (severity, -token) does exactly this.

cpp
#include <iostream>
#include <queue>
#include <utility>

int main() {
    std::priority_queue<std::pair<int, int>> pq;   // (severity, -token)
    pq.push({3, -101});
    pq.push({9, -102});
    pq.push({3, -100});
    while (!pq.empty()) {
        auto [severity, negToken] = pq.top();
        pq.pop();
        std::cout << "Token " << -negToken << " (severity " << severity << ")\n";
    }
}
// Token 102 (severity 9)
// Token 100 (severity 3)
// Token 101 (severity 3)
Pairs compare by first then second; negating the token makes smaller tokens win ties.

Practice (0/4 done)

Task 1 · Question

std::set<int> s = {4, 2, 4, 9, 2}; What is s.size()?

Task 2 · Question

What prints? std::stack<int> st; st.push(1); st.push(2); st.push(3); st.pop(); std::cout << st.top();

Task 3 · Question

Which container gives the smallest element first in O(log n) per push/pop?

Task 4 · Practice

Write bool balanced(const std::string& s) that returns true if every bracket in s ((), [], {}) is closed in the right order, using std::stack<char>. Test "{[()]}" (true), "([)]" (false) and "((" (false).

Quick quiz

Question 1

1.Which order does std::queue follow?

Question 2

2.Why prefer s.lower_bound(x) over std::lower_bound(s.begin(), s.end(), x) on a std::set?

Question 3

3.Which container allows fast push and pop at BOTH ends and indexing with []?

Question 4

4.std::priority_queue<int> pq; after pushing 4, 9 and 2, what is pq.top()?

Read more (free)

Open a question to see the answer and why. The first ones are this topic's own quiz, so try the quiz above before you peek.

Which order does std::queue follow?

Answer: First in, first out

A queue serves elements in the order they arrived.

Why prefer s.lower_bound(x) over std::lower_bound(s.begin(), s.end(), x) on a std::set?

Answer: The member uses the tree and is O(log n); the free algorithm is O(n) on set iterators

Set iterators are bidirectional, so the generic algorithm cannot jump.

Which container allows fast push and pop at BOTH ends and indexing with []?

Answer: std::deque

deque is a double-ended queue with random access.

std::priority_queue<int> pq; after pushing 4, 9 and 2, what is pq.top()?

Answer: 9

By default priority_queue is a max-heap.

Which is the best tool for a large FIFO queue in Python?Related

Answer: collections.deque with append and popleft

deque adds and removes at both ends in O(1). list.pop(0) shifts every item, which is O(n).

From Stacks and queues

A circular queue has capacity 4, head = 3 and count = 2. Which slot does the next enqueue use?Related

Answer: 1

(3 + 2) % 4 = 1. The items sit in slots 3 and 0; the next one goes in slot 1.

From Queues and deques

Which removes and returns the head of a Queue, or null if it is empty?Related

Answer: poll()

poll returns null when empty; remove throws.

From Queues, stacks and priority queues

Which can you NOT do with std::unordered_map that you can with std::map?Related

Answer: Loop in sorted key order

unordered_map has no ordering, so no sorted iteration or lower_bound.

From std::map and std::unordered_map

Pass the quiz (60% or more) or mark this topic as done when you are ready.

Your progress is saved on this device only.

Next: Iterators: the glue between containers and algorithms →

Next steps

  1. 2 more topics in “The Standard Template Library (STL)” before its exam: Iterators: the glue between containers and algorithms, STL algorithms: sort, find, count, accumulate and binary search.
  2. Module 6 exam: The STL · 13 questions · 25 min, without help. 5 topics of this module still to finish first.
  3. Then the next module, Templates, smart pointers and move semantics. 42 topics left in the course before the final exam.

← Previous: std::map and std::unordered_map