Library

since C++98

Basic

std::stack, std::queue, and std::priority_queue

C++ container adaptors — stack (LIFO), queue (FIFO), and priority_queue (heap-based) with underlying container selection, complexity, and practical patterns.

Container Adaptorssince C++98

std::stack, std::queue, and std::priority_queue are interface-restricting wrappers over sequence containers that enforce LIFO, FIFO, and heap-ordered access disciplines without exposing iteration.

Overview

Container adaptors are not data structures — they are interface restrictions over existing sequence containers. Each adaptor owns an underlying container (accessible as the protected member c) and forwards only the operations semantically appropriate for its discipline. Because they expose no iterators, range-based for, STL algorithms, and structured iteration cannot operate on them directly. This is intentional: the restricted surface enforces correct usage patterns.

Adaptor	Discipline	Default container	Access points
`std::stack`	LIFO	`std::deque`	`top()`
`std::queue`	FIFO	`std::deque`	`front()`, `back()`
`std::priority_queue`	Max-heap	`std::vector`	`top()`

Underlying container requirements differ and constrain substitution:

stack — needs back(), push_back(), pop_back(). Satisfied by deque, vector, list.
queue — needs front(), back(), push_back(), pop_front(). Satisfied by deque, list — not vector (no pop_front()).
priority_queue — needs random-access iterators plus front(), push_back(), pop_back(). Satisfied by vector, deque.

Syntax

cpp

// C++98
template<class T, class Container = std::deque<T>>
class stack;

// C++98
template<class T, class Container = std::deque<T>>
class queue;

// C++98
template<class T,
         class Container = std::vector<T>,
         class Compare = std::less<typename Container::value_type>>
class priority_queue;

All three headers: <stack> for stack, <queue> for queue and priority_queue.

Examples

std::stack

cpp

#include <stack>

std::stack<int> s;          // std::deque<int> underneath
s.push(1);
s.push(2);
s.emplace(3);               // construct in-place; C++11
s.top();                    // 3 — reference, UB if empty
s.pop();                    // void — does NOT return the element
s.size();                   // 2

// Vector-backed stack: contiguous memory, better cache behavior
// than deque's segmented layout — preferred for hot inner loops
std::stack<int, std::vector<int>> vs;

// C++23: push_range — batch-insert from any range
// s.push_range(std::views::iota(0, 5));

pop() intentionally returns void. Returning by value would require a copy that could throw, making it impossible to provide a strong exception guarantee. Always read top() before pop().

RPN expression evaluator — stack's canonical pattern:

cpp

int eval_rpn(const std::vector<std::string>& tokens) {
    std::stack<int> stk;
    for (const auto& tok : tokens) {
        if (tok == "+" || tok == "-" || tok == "*" || tok == "/") {
            int b = stk.top(); stk.pop();
            int a = stk.top(); stk.pop();
            if      (tok == "+") stk.push(a + b);
            else if (tok == "-") stk.push(a - b);
            else if (tok == "*") stk.push(a * b);
            else                 stk.push(a / b);
        } else {
            stk.push(std::stoi(tok));
        }
    }
    return stk.top();
}
// eval_rpn({"3", "4", "+", "2", "*"}) == 14

std::queue

cpp

#include <queue>

std::queue<std::string> q;  // std::deque<string> underneath
q.push("a");                // enqueue at back
q.emplace("b");             // construct in-place at back; C++11
q.front();                  // "a" — next to dequeue (UB if empty)
q.back();                   // "b" — most recently enqueued
q.pop();                    // removes front element; void
q.size();                   // 1

// List-backed queue: O(1) pop_front without block reallocation
// Useful when insertion rate far exceeds removal rate
std::queue<int, std::list<int>> lq;

BFS with level tracking:

cpp

void bfs_levels(Node* root) {
    std::queue<Node*> q;
    q.push(root);
    int depth = 0;
    while (!q.empty()) {
        for (int n = static_cast<int>(q.size()); n-- > 0;) {
            Node* node = q.front();
            q.pop();
            visit(node, depth);
            for (Node* child : node->children)
                q.push(child);
        }
        ++depth;
    }
}

std::priority_queue

A max-heap by default: top() always returns the element for which the comparator ranks all others below it. With std::less<T> (the default), the maximum element wins.

cpp

#include <queue>

std::priority_queue<int> pq;         // max-heap, std::less<int>
pq.push(3); pq.push(1); pq.push(5); pq.push(4);
pq.top();  // 5
pq.pop();  // O(log n), removes 5
pq.top();  // 4

// Min-heap: flip to std::greater
std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
min_pq.push(3); min_pq.push(1); min_pq.push(4);
min_pq.top();  // 1

Comparator semantics: Cmp(a, b) == true means a ranks lower than b — a would be evicted before b. This mirrors std::sort convention. With a custom type, write the comparator as a strict less-than over priority:

cpp

struct Job { int pri; int seq; std::string name; };

// Higher pri = more urgent; among equals, lower seq = older = more urgent
auto cmp = [](const Job& a, const Job& b) {
    return a.pri != b.pri ? a.pri < b.pri : a.seq > b.seq;
};
std::priority_queue<Job, std::vector<Job>, decltype(cmp)> scheduler{cmp};
scheduler.push({3, 1, "urgent"});
scheduler.push({3, 2, "also-urgent"});
scheduler.push({1, 3, "low"});
scheduler.top().name;  // "urgent" — pri 3, seq 1 wins tie-break

O(n) construction from a range:

cpp

std::vector<int> data{5, 3, 1, 4, 2};

// Heapify constructor: O(n) via std::make_heap internally
std::priority_queue<int> pq1(data.begin(), data.end());

// Move the underlying container in — avoids a copy (C++11)
std::priority_queue<int, std::vector<int>, std::less<int>> pq2(
    std::less<int>{},
    std::move(data)
);

Inserting n elements individually via push() costs O(n log n). Prefer the range constructor when initialising from existing data.

Dijkstra's algorithm:

cpp

using Edge  = std::pair<int, int>;   // (weight, destination)
using State = std::pair<int, int>;   // (distance, node)

std::vector<int> dijkstra(int src, int n,
                           const std::vector<std::vector<Edge>>& adj) {
    std::vector<int> dist(n, INT_MAX);
    std::priority_queue<State, std::vector<State>,
                        std::greater<State>> pq;  // min-heap on distance
    dist[src] = 0;
    pq.push({0, src});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();  // C++17 structured bindings
        if (d > dist[u]) continue;          // stale entry — discard
        for (auto [w, v] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

K-largest elements with a bounded min-heap:

cpp

std::vector<int> k_largest(const std::vector<int>& data, std::size_t k) {
    std::priority_queue<int, std::vector<int>, std::greater<int>> heap;
    for (int x : data) {
        heap.push(x);
        if (heap.size() > k) heap.pop();  // evict current minimum
    }
    std::vector<int> result;
    result.reserve(k);
    while (!heap.empty()) { result.push_back(heap.top()); heap.pop(); }
    std::ranges::sort(result, std::greater<>{});  // C++20
    return result;
}

Complexity summary

Operation	`stack`	`queue`	`priority_queue`
`push` / `emplace`	O(1) amortized	O(1) amortized	O(log n)
`pop`	O(1)	O(1)	O(log n)
`top` / `front` / `back`	O(1)	O(1)	O(1)
`size` / `empty`	O(1)	O(1)	O(1)
Construction from range	O(n)	O(n)	O(n) heapify

Best Practices

Match the underlying container to the access pattern. For stack, std::vector gives better cache locality than deque's segmented memory; benchmark before assuming the default is optimal. For queue, deque is almost always correct — list avoids reallocation at the cost of per-node heap allocations that can dominate at high throughput.

Use the range constructor for priority_queue when possible. O(n) heapify versus O(n log n) for n individual push() calls is a meaningful difference at scale.

Prefer emplace() over push() for non-trivial types (C++11). emplace() forwards arguments directly to the element constructor, eliminating a temporary.

Encode a sequence number for stable priority ordering. The heap does not preserve insertion order for elements that compare equal. If FIFO behaviour among equal-priority items is required, add a monotonically increasing counter to the element type and include it in the comparator.

Common Pitfalls

Accessing an empty adaptor is undefined behaviour, not an exception. None of the three adaptors provide a bounds-checked accessor equivalent to vector::at(). Always guard with empty() before top(), front(), or back().

pop() returns void. The pattern int x = s.pop(); is a compile error. Read the element first, then pop: int x = s.top(); s.pop();.

vector cannot back a queue. std::vector has no pop_front(), so std::queue<T, std::vector<T>> fails to compile. Only deque and list satisfy queue's container requirements.

No iterators means no standard traversal. There is no way to iterate a priority_queue without destroying it. If you need non-destructive inspection, drain into a vector, inspect, then rebuild — or reconsider whether you need a full sorted container instead.

push_range() is C++23 only. Gate usage behind #if __cpp_lib_adaptor_iterator_pair_constructor >= 202106L or restrict to C++23 translation units.

Comparator polarity is a persistent source of bugs. The comparator defines "less than" for priority rank. std::less makes the maximum win. Swapping to std::greater makes the minimum win. When writing a custom lambda, always verify which element appears at top() with a small test before integrating into production code.

Custom container backends

The adaptor template's second parameter lets you swap the underlying store without changing call sites. Any container satisfying the required concept works — including hand-rolled or third-party types.

cpp

// C++11
#include <stack>
#include <vector>

// Swap deque for vector to get contiguous memory and
// avoid the segmented-block indirection deque introduces.
std::stack<int, std::vector<int>> fast_stack;
fast_stack.push(42);
fast_stack.top();   // 42 — same interface, better cache behavior

// A list-backed stack has O(1) worst-case push (no realloc) at
// the cost of per-node heap allocations. Worth it only when
// push latency must be predictable, not average-case optimal.
std::stack<int, std::list<int>> latency_stable_stack;

Accessing the underlying container is possible through the protected member c via a derived class. This is a legitimate (if rarely needed) extension point:

cpp

// C++11
template<class T, class Container = std::deque<T>>
class drainable_stack : public std::stack<T, Container> {
public:
    // Expose the protected member to allow non-destructive inspection.
    Container& data()       { return this->c; }
    const Container& data() const { return this->c; }
};

drainable_stack<int> ds;
ds.push(1); ds.push(2); ds.push(3);
for (int x : ds.data()) { /* iterate without popping */ }

Do not expose c in production APIs; it breaks the adaptor's encapsulation contract and re-admits all the misuse patterns the restricted interface was designed to prevent.

Min-heap vs max-heap

The comparator argument to priority_queue determines which element sits at top(), not which is "smallest." Cmp(a, b) == true means a is lower priority and will be evicted before b. The default std::less<T> therefore promotes the largest element to the top — a max-heap.

cpp

// C++11
#include <queue>
#include <functional>

// Max-heap (default): top() == maximum element
std::priority_queue<int> max_heap;
max_heap.push(3); max_heap.push(1); max_heap.push(4); max_heap.push(1);
max_heap.top();  // 4

// Min-heap: pass std::greater — top() == minimum element
std::priority_queue<int,
    std::vector<int>,
    std::greater<int>> min_heap;
min_heap.push(3); min_heap.push(1); min_heap.push(4); min_heap.push(1);
min_heap.top();  // 1

// Negate values to simulate a min-heap without changing the comparator —
// a common competitive-programming trick, but avoid in production code
// because it silently overflows for INT_MIN.
std::priority_queue<int> negated_min;
negated_min.push(-3); negated_min.push(-1); negated_min.push(-4);
int actual_min = -negated_min.top();  // 1 — fragile, avoid

For custom types, write the comparator as a strict weak ordering on the priority dimension. Returning true when a should lose means writing it like a < that encodes "a is less important than b":

cpp

// C++11
struct Task { int priority; std::string name; };

// Task with HIGHER numeric priority wins (reaches top()).
auto task_cmp = [](const Task& a, const Task& b) {
    return a.priority < b.priority;  // lower number = lower priority = evicted first
};
std::priority_queue<Task, std::vector<Task>, decltype(task_cmp)> pq{task_cmp};

Priority queue with mutable priorities

std::priority_queue does not support decrease-key or increase-key operations — once an element is inside the heap its position cannot be updated. The standard workaround is the lazy deletion pattern used in Dijkstra: push a new entry and skip stale ones when they surface.

cpp

// C++17
#include <queue>
#include <vector>
#include <unordered_map>

// Lazy-deletion priority queue: elements can be "updated" by
// pushing a new entry with a higher priority and marking the old one invalid.
struct Entry { int priority; int id; };

struct LazyPQ {
    std::priority_queue<Entry,
        std::vector<Entry>,
        decltype([](const Entry& a, const Entry& b){
            return a.priority < b.priority; // max-heap on priority
        })> heap;
    std::unordered_map<int, int> best;  // id -> best known priority

    void push(int id, int pri) {
        best[id] = pri;
        heap.push({pri, id});
    }

    // Returns the entry with the highest priority that has not been superseded.
    std::optional<Entry> pop() {
        while (!heap.empty()) {
            auto top = heap.top(); heap.pop();
            if (best.count(top.id) && best[top.id] == top.priority)
                return top;
            // else: stale entry — discard and continue
        }
        return std::nullopt;
    }

    void update(int id, int new_pri) {
        best[id] = new_pri;           // invalidates any existing entry
        heap.push({new_pri, id});     // push fresh entry
    }
};

The heap may accumulate O(n) stale entries. If memory is constrained, use a std::set or std::multiset instead — they support erase + re-insert in O(log n), providing true mutable priorities at the cost of worse constant factors than a binary heap.

Thread-safe queue with condition_variable

std::queue is not thread-safe; concurrent push/pop without synchronisation is undefined behaviour. The standard pattern wraps the queue in a mutex-plus-condition-variable to build a blocking concurrent queue:

cpp

// C++11
#include <queue>
#include <mutex>
#include <condition_variable>
#include <optional>

template<class T>
class blocking_queue {
public:
    void push(T value) {
        {
            std::lock_guard<std::mutex> lk(mtx_);
            q_.push(std::move(value));
        }
        cv_.notify_one();   // wake one waiting consumer
    }

    // Blocks until an item is available.
    T pop() {
        std::unique_lock<std::mutex> lk(mtx_);
        cv_.wait(lk, [this]{ return !q_.empty(); });
        T value = std::move(q_.front());
        q_.pop();
        return value;
    }

    // Non-blocking: returns nullopt immediately if empty.
    std::optional<T> try_pop() {
        std::lock_guard<std::mutex> lk(mtx_);
        if (q_.empty()) return std::nullopt;
        T value = std::move(q_.front());
        q_.pop();
        return value;
    }

    bool empty() const {
        std::lock_guard<std::mutex> lk(mtx_);
        return q_.empty();
    }

private:
    mutable std::mutex mtx_;
    std::condition_variable cv_;
    std::queue<T> q_;
};

Use notify_all() instead of notify_one() only when all consumers must wake — for example, when the queue also signals shutdown. notify_one() is sufficient and cheaper for normal producer-consumer pipelines. For higher throughput, consider std::atomic ring buffers (lock-free SPSC/MPSC queues) from a library such as folly::MPMCQueue.

Stack-based DFS and queue-based BFS

The duality between DFS and BFS is purely a data structure choice: swap std::stack for std::queue (or vice versa) and the traversal order flips. Both iterative versions avoid recursion-depth limits and have identical structure.

cpp

// C++17
#include <stack>
#include <queue>
#include <vector>
#include <unordered_set>

// Iterative DFS using std::stack
void dfs(int start, const std::vector<std::vector<int>>& adj) {
    std::unordered_set<int> visited;
    std::stack<int> frontier;
    frontier.push(start);
    while (!frontier.empty()) {
        int node = frontier.top(); frontier.pop();
        if (visited.count(node)) continue;
        visited.insert(node);
        process(node);
        for (int nbr : adj[node])
            if (!visited.count(nbr)) frontier.push(nbr);
    }
}

// Iterative BFS using std::queue — only the container type differs
void bfs(int start, const std::vector<std::vector<int>>& adj) {
    std::unordered_set<int> visited;
    std::queue<int> frontier;      // <-- the only structural difference
    frontier.push(start);
    visited.insert(start);
    while (!frontier.empty()) {
        int node = frontier.front(); frontier.pop();
        process(node);
        for (int nbr : adj[node])
            if (visited.insert(nbr).second)
                frontier.push(nbr);
    }
}

Note that the DFS version shown uses visited check at pop-time, which may push duplicates. Mark nodes at push-time to avoid this and reduce frontier size:

cpp

// C++17 — push-time marking avoids redundant frontier entries
void dfs_clean(int start, const std::vector<std::vector<int>>& adj) {
    std::unordered_set<int> visited;
    std::stack<int> frontier;
    frontier.push(start);
    visited.insert(start);
    while (!frontier.empty()) {
        int node = frontier.top(); frontier.pop();
        process(node);
        for (int nbr : adj[node])
            if (visited.insert(nbr).second)   // insert returns {it, bool}
                frontier.push(nbr);
    }
}

Monotonic stack/deque patterns

A monotonic stack maintains elements in strictly increasing or decreasing order and solves "next greater/smaller element" problems in O(n) time. Elements are popped whenever they would violate the monotonic invariant, guaranteeing each element is pushed and popped at most once.

cpp

// C++17 — Next Greater Element (monotonic decreasing stack)
#include <stack>
#include <vector>

std::vector<int> next_greater(const std::vector<int>& nums) {
    int n = static_cast<int>(nums.size());
    std::vector<int> result(n, -1);
    std::stack<int> indices;   // stack of indices, values decrease top->bottom

    for (int i = 0; i < n; ++i) {
        // Pop indices whose value is smaller than current — current is their answer.
        while (!indices.empty() && nums[indices.top()] < nums[i]) {
            result[indices.top()] = nums[i];
            indices.pop();
        }
        indices.push(i);
    }
    return result;
    // next_greater({2,1,2,4,3}) == {4,2,4,-1,-1}
}

Largest rectangle in histogram is the classic two-pointer monotonic stack problem:

cpp

// C++17
int largest_rectangle(const std::vector<int>& heights) {
    std::stack<int> stk;   // monotonic increasing stack of indices
    int max_area = 0;
    int n = static_cast<int>(heights.size());

    for (int i = 0; i <= n; ++i) {
        int h = (i == n) ? 0 : heights[i];
        while (!stk.empty() && heights[stk.top()] > h) {
            int height = heights[stk.top()]; stk.pop();
            int width  = stk.empty() ? i : i - stk.top() - 1;
            max_area = std::max(max_area, height * width);
        }
        stk.push(i);
    }
    return max_area;
}

A monotonic deque extends the pattern to sliding-window extrema — the deque front always holds the index of the window's maximum (or minimum), and stale indices outside the window are discarded from the front:

cpp

// C++17 — Sliding window maximum in O(n)
#include <deque>

std::vector<int> sliding_window_max(const std::vector<int>& nums, int k) {
    std::deque<int> dq;   // indices; values at front are always the window max
    std::vector<int> result;
    int n = static_cast<int>(nums.size());

    for (int i = 0; i < n; ++i) {
        // Remove indices that are out of the current window.
        while (!dq.empty() && dq.front() < i - k + 1)
            dq.pop_front();
        // Remove indices whose value is less than current — they can never be max.
        while (!dq.empty() && nums[dq.back()] < nums[i])
            dq.pop_back();
        dq.push_back(i);
        if (i >= k - 1)
            result.push_back(nums[dq.front()]);
    }
    return result;
    // sliding_window_max({1,3,-1,-3,5,3,6,7}, 3) == {3,3,5,5,6,7}
}

Note that std::deque is used directly here, not std::queue, because both ends must be accessible. The monotonic deque pattern is the foundation for more advanced algorithms including the optimal-BST problem and certain DP optimisations.

See Also

std::deque — default underlying container for stack and queue
std::vector — default underlying container for priority_queue
std::make_heap, std::push_heap, std::pop_heap — raw heap algorithms that priority_queue wraps
std::flat_map, std::flat_set — C++23 sorted container adaptors over contiguous storage