Chapter 37 of 48

stack, queue & priority_queue

Stacks, queues and priority queues are three of the most used data structures in computer science. A stack checks balanced brackets and powers undo; a queue drives breadth-first search and task scheduling; a priority queue is the heart of Dijkstra's algorithm, CPU schedulers and "top K" problems.

In C++ you do not have to write any of them yourself. The STL provides std::stack, std::queue and std::priority_queue. Interestingly, these are not new containers. They are container adaptors: thin wrappers that take a container you already know (deque, vector or list from the previous chapters) and expose only a restricted interface.


What Is a Container Adaptor?

A container adaptor is a class template that stores an underlying sequence container and offers a limited, purpose-specific interface on top of it. It hides every operation that would break the data structure's rules.

For example, a stack must only let you touch the top. A deque lets you do anything, so std::stack wraps a deque and only exposes push, pop and top.

Adaptor

Header

Rule

Default underlying container

Other allowed containers

std::stack<T>

<stack>

LIFO (last in, first out)

deque<T>

vector, list

std::queue<T>

<queue>

FIFO (first in, first out)

deque<T>

list (not vector: it has no pop_front)

std::priority_queue<T>

<queue>

Highest priority first

vector<T>

deque (needs random access)

Two important consequences of being adaptors:

  • They have no iterators. You cannot write a range-based for over a std::stack. If you need to look at all elements, you probably want the underlying container itself.

  • They do not check for emptiness. Calling top(), front() or pop() on an empty adaptor is undefined behavior, not an exception.


std::stack – Last In, First Out

Think of a stack of plates: you put a plate on top, and you take the top plate off. The last plate placed is the first one removed.

push(10)  push(20)  push(30)   pop()

                      ┌────┐
            ┌────┐    │ 30 │ ← top
  ┌────┐    │ 20 │    │ 20 │    ┌────┐
  │ 10 │    │ 10 │    │ 10 │    │ 20 │ ← top
  └────┘    └────┘    └────┘    │ 10 │
                                └────┘

Member

Meaning

Cost (default deque)

push(x) / emplace(args...)

Put an element on top

O(1)

pop()

Remove the top element (returns nothing)

O(1)

top()

Reference to the top element

O(1)

empty(), size()

Is it empty? How many elements?

O(1)

#include <iostream>
#include <stack>

int main() {
    std::stack<int> st;
    st.push(10);
    st.push(20);
    st.push(30);

    std::cout << "Top: " << st.top() << ", size: " << st.size() << '\n';

    st.top() = 35;                 // top() returns a reference
    while (!st.empty()) {
        std::cout << "Popping " << st.top() << '\n';
        st.pop();                  // pop() returns void
    }
    std::cout << "Empty now? " << std::boolalpha << st.empty() << '\n';
}

Output:

Top: 30, size: 3
Popping 35
Popping 20
Popping 10
Empty now? true

Because top() returns a reference, st.top() = 35; modified the element in place.

Why Does pop() Return void?

Students coming from Java or Python often expect int x = st.pop();. In C++ that does not compile, and the reason is exception safety. If pop() removed the element and then returned it by value, the copy into x could throw (imagine a large std::string and memory running out). The element would already be removed from the stack, but never delivered to you: it would be lost forever. Splitting the job into top() (read) and pop() (remove) makes each step safe. It also avoids an unnecessary copy when you only want to discard the element.

Example: Balanced Brackets

This is a classic interview problem. Every opening bracket is pushed; every closing bracket must match the most recent unmatched opening bracket, which is exactly the top of the stack.

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

bool isBalanced(const std::string& s) {
    std::stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (st.empty()) return false;            // closing with nothing open
            char open = st.top();
            st.pop();
            if ((c == ')' && open != '(') ||
                (c == ']' && open != '[') ||
                (c == '}' && open != '{'))
                return false;                        // wrong kind of bracket
        }
    }
    return st.empty();                               // something left open?
}

int main() {
    for (std::string s : {"{[()()]}", "([)]", "((", "a*(b+c)"}) {
        std::cout << s << " -> " << (isBalanced(s) ? "balanced" : "not balanced") << '\n';
    }
}

Output:

{[()()]} -> balanced
([)] -> not balanced
(( -> not balanced
a*(b+c) -> balanced

Trace for ([)]: push (, push [, then ) arrives but the top is [, a mismatch, so the function returns false. Each character is processed once, so the algorithm runs in O(n) time and O(n) extra space.


std::queue – First In, First Out

A queue works like a ticket counter: people join at the back and are served from the front.

         front                     back
pop() ◄── [ Asha ][ Ravi ][ Meena ] ◄── push()

Member

Meaning

Cost (default deque)

push(x) / emplace(args...)

Add at the back

O(1)

pop()

Remove from the front (returns nothing)

O(1)

front() / back()

References to the first / last element

O(1)

empty(), size()

As usual

O(1)

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

int main() {
    std::queue<std::string> counter;
    counter.push("Asha");
    counter.push("Ravi");
    counter.push("Meena");

    std::cout << "Front: " << counter.front() << ", Back: " << counter.back() << '\n';

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

Output:

Front: Asha, Back: Meena
Serving Asha
Serving Ravi
Serving Meena

Why is the default container deque and not vector? A queue removes from the front. vector has no pop_front because it would be O(n), while deque::pop_front is O(1) (see list, deque & array).

BFS explores a graph level by level. A queue guarantees that all vertices at distance d are processed before any vertex at distance d + 1, which is why BFS finds shortest paths in unweighted graphs.

    0 ─── 1
    │     │
    2 ─── 3 ─── 5
    │
    4
#include <iostream>
#include <queue>
#include <vector>

int main() {
    // Undirected graph with 6 vertices as an adjacency list
    std::vector<std::vector<int>> adj = {
        {1, 2},     // 0
        {0, 3},     // 1
        {0, 3, 4},  // 2
        {1, 2, 5},  // 3
        {2},        // 4
        {3}         // 5
    };

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

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {          // not visited yet
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }

    for (std::size_t i = 0; i < dist.size(); ++i)
        std::cout << "dist[" << i << "] = " << dist[i] << '\n';
}

Output:

dist[0] = 0
dist[1] = 1
dist[2] = 1
dist[3] = 2
dist[4] = 2
dist[5] = 3

Each vertex enters the queue at most once and each edge is examined at most twice (once from each end), so BFS takes O(V + E) time.


std::priority_queue – Highest Priority First

A priority queue is a collection where every removal takes out the element with the highest priority, regardless of insertion order. std::priority_queue implements it as a binary heap stored inside a vector.

By default, "highest priority" means "largest according to operator<", so std::priority_queue<int> is a max-heap.

How the Heap Works

A binary max-heap is a complete binary tree where every parent is ≥ its children. It is stored level by level in an array: the children of index i are at 2i + 1 and 2i + 2.

            50                index: 0   1   2   3   4
          /    \              value: 50  40  30  10  20
        40      30
       /  \
     10    20
  • top() is simply element 0: O(1).

  • push(x) appends x at the end and "sifts it up", swapping with its parent while it is larger. The tree height is log2 n, so this is O(log n).

  • pop() moves the last element to the root and "sifts it down", swapping with the larger child: O(log n).

  • Building from n elements at once (the iterator-range constructor) uses the bottom-up heap construction, which is O(n), better than n separate pushes (O(n log n)).

Member

Meaning

Cost

push(x) / emplace(args...)

Insert an element

O(log n)

pop()

Remove the top element

O(log n)

top()

const reference to the highest-priority element

O(1)

constructor from a range

Build a heap from existing data

O(n)

Notice that top() returns a const reference. If you could change the top element, you would break the heap ordering.

Max-Heap and Min-Heap

#include <functional>   // std::greater
#include <iostream>
#include <queue>
#include <vector>

int main() {
    std::vector<int> nums = {40, 10, 50, 30, 20};

    std::priority_queue<int> maxHeap;                  // default: largest on top
    for (int x : nums) maxHeap.push(x);

    std::cout << "Max-heap order: ";
    while (!maxHeap.empty()) {
        std::cout << maxHeap.top() << ' ';
        maxHeap.pop();
    }
    std::cout << '\n';

    std::priority_queue<int, std::vector<int>, std::greater<int>>
        minHeap(nums.begin(), nums.end());             // build in O(n)

    std::cout << "Min-heap order: ";
    while (!minHeap.empty()) {
        std::cout << minHeap.top() << ' ';
        minHeap.pop();
    }
    std::cout << '\n';
}

Output:

Max-heap order: 50 40 30 20 10 
Min-heap order: 10 20 30 40 50 

The full template is std::priority_queue<T, Container, Compare>. To get a min-heap we pass std::greater<int> as the comparator, but because the comparator is the third parameter we must also spell out the second one, std::vector<int>.

The comparator logic feels backwards at first, so remember this rule:

The comparator comp(a, b) answers "does a have lower priority than b?" The element that is "greatest" by this comparison ends up on top. With std::less (the default) the largest value is on top; with std::greater the smallest value is on top.

A quick alternative trick for a min-heap of numbers is to push -x into a max-heap and negate again when reading, but the std::greater version is clearer (and does not overflow for INT_MIN).

Custom Priorities with a Struct

Let's model a hospital emergency room: more severe patients first; for equal severity, whoever arrived first.

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

struct Patient {
    std::string name;
    int severity;      // higher = more urgent
    int arrival;       // lower = came earlier
};

// Comparator returns true if a has LOWER priority than b
struct LessUrgent {
    bool operator()(const Patient& a, const Patient& b) const {
        if (a.severity != b.severity) return a.severity < b.severity;
        return a.arrival > b.arrival;                  // tie: earlier arrival first
    }
};

int main() {
    std::priority_queue<Patient, std::vector<Patient>, LessUrgent> er;
    er.push({"Kiran", 2, 1});
    er.push({"Divya", 5, 2});
    er.push({"Arjun", 3, 3});
    er.push({"Sana",  5, 4});

    while (!er.empty()) {
        const Patient& p = er.top();
        std::cout << p.name << " (severity " << p.severity << ")\n";
        er.pop();
    }
}

Output:

Divya (severity 5)
Sana (severity 5)
Arjun (severity 3)
Kiran (severity 2)

Divya and Sana both have severity 5. The comparator says the one with the larger arrival number has lower priority, so Divya (arrival 2) comes before Sana (arrival 4). A priority queue is not stable: without that tie-breaking rule, elements of equal priority could come out in any order.

The comparator here is a function object: a struct with an overloaded operator(), which we saw in the Operator Overloading chapter. It must be a strict weak ordering: in particular, comp(a, a) must be false. Using <= instead of < breaks this rule and gives undefined behavior.

Example: Top K Elements in O(n log k)

To find the 3 highest scores, keep a min-heap of size k. Its top is the smallest of the best k seen so far; whenever the heap grows beyond k, throw that smallest away.

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

// k largest elements using a min-heap of size k: O(n log k)
std::vector<int> topK(const std::vector<int>& v, std::size_t k) {
    std::priority_queue<int, std::vector<int>, std::greater<int>> heap;
    for (int x : v) {
        heap.push(x);
        if (heap.size() > k) heap.pop();     // throw away the smallest
    }
    std::vector<int> result;
    while (!heap.empty()) {
        result.push_back(heap.top());
        heap.pop();
    }
    return result;                           // in increasing order
}

int main() {
    std::vector<int> scores = {67, 92, 45, 88, 99, 73, 81};
    for (int s : topK(scores, 3)) std::cout << s << ' ';
    std::cout << '\n';
}

Output:

88 92 99 

Each push/pop costs O(log k) because the heap never holds more than k + 1 elements, giving O(n log k) overall. That is better than sorting everything (O(n log n)) when k is small.


Choosing the Underlying Container

You can pass the container as the second template argument. For example, a stack on a vector avoids the deque's block allocations and is a common choice:

#include <iostream>
#include <stack>
#include <vector>

int main() {
    std::stack<int, std::vector<int>> st;   // stack on top of a vector
    st.push(1);
    st.push(2);

    std::stack<int> empty;
    // empty.top();   // undefined behavior: no check, no exception!
    // empty.pop();   // undefined behavior too
    if (!empty.empty()) std::cout << empty.top() << '\n';
    else std::cout << "Stack is empty, nothing to read\n";

    std::cout << "st.top() = " << st.top() << '\n';
}

Output:

Stack is empty, nothing to read
st.top() = 2

The container must provide the operations the adaptor uses:

  • stack: back(), push_back(), pop_back()

  • queue: front(), back(), push_back(), pop_front()

  • priority_queue: random-access iterators, front(), push_back(), pop_back()

C++23 Additions

C++23 made the adaptors easier to fill from existing data. stack and queue gained constructors that take an iterator pair (priority_queue always had one), and all three gained push_range and constructors taking std::from_range:

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

int main() {
    std::vector<int> v = {1, 2, 3, 4};

    std::stack<int> st(v.begin(), v.end());      // C++23: iterator-pair constructor
    std::queue<int> q;
    q.push_range(v);                             // C++23: push_range

    std::cout << "stack top = " << st.top() << ", queue front = " << q.front() << '\n';
}

Output (compiled with -std=c++23, GCC 15):

stack top = 4, queue front = 1

The last element pushed (4) is on top of the stack, while the first (1) is at the front of the queue, exactly as LIFO and FIFO say.


Comparison

stack

queue

priority_queue

Removal order

Newest first (LIFO)

Oldest first (FIFO)

Highest priority first

Read the next element

top()

front()

top() (const)

Insert / remove cost

O(1) / O(1)

O(1) / O(1)

O(log n) / O(log n)

Default container

deque

deque

vector

Typical uses

Undo, brackets, expression evaluation, DFS, recursion simulation

BFS, task scheduling, buffering

Dijkstra, Prim, Huffman coding, scheduling, top-K, merging k sorted lists


Common Mistakes

  1. Calling top()/front()/pop() on an empty adaptor. There is no check and no exception: it is undefined behavior. Always test empty() first.

  2. Writing int x = st.pop();. pop() returns void. Read with top()/front(), then pop().

  3. Using a reference after popping. const auto& p = pq.top(); pq.pop(); use(p); is a bug. p refers to slot 0 of the underlying vector; after pop() that slot holds a different element (the new top), or, if the queue had only one element, an object that has been destroyed (undefined behavior). Use the reference before pop(), or make a copy: auto p = pq.top();.

  4. Expecting priority_queue<int> to give the smallest first. The default is a max-heap; use std::greater<int> for a min-heap.

  5. Writing the comparator the "natural" way round. For a min-heap of structs you return a.key > b.key, not <.

  6. Trying to iterate over an adaptor with a range-based for. Adaptors have no begin()/end().

  7. Using std::queue<int, std::vector<int>>. It compiles until you call pop(), which needs pop_front(), and then fails.


Interview / GATE-Style Questions

Q1. Why does std::stack::pop() return void instead of the removed element?

For exception safety. If pop() removed the element and then returned it by value, an exception thrown while copying the return value would lose the element permanently. Separating top() and pop() means the element is only removed after you have safely read it. It also avoids a copy when you just want to discard the element.

Q2. What are the time complexities of push, pop and top for std::priority_queue? How long does it take to build one from n elements?

push and pop are O(log n); top is O(1). Building from n elements with the range constructor is O(n) (bottom-up heapify). Pushing n elements one by one is O(n log n).

Q3. What does this print? std::priority_queue<int, std::vector<int>, std::greater<int>> pq; push 5, 1, 8, 3; pop once; print top.

It is a min-heap, so the top is 1. After one pop, 1 is removed and the new top is 3.

Q4. A sequence 1, 2, 3, 4, 5 is pushed onto a stack in that order; pops may be interleaved with pushes. Is 4, 5, 3, 2, 1 a valid output? Is 4, 3, 5, 1, 2?

4 5 3 2 1 is valid: push 1–4, pop 4, push 5, pop 5, then pop 3, 2, 1. 4 3 5 1 2 is not valid: after popping 4, 3 and 5, the stack holds 2 on top of 1, so 1 cannot be popped before 2.

Q5. How can you implement a queue using two stacks, and what is the cost per operation?

Use an in stack for pushes and an out stack for pops. To pop, if out is empty, move every element from in to out (this reverses their order, putting the oldest on top), then pop from out. Each element is moved at most once, so every operation is O(1) amortized, although a single pop can take O(n).


Summary

  • stack, queue and priority_queue are container adaptors: they wrap a sequence container and expose a restricted interface. They have no iterators.

  • stack is LIFO (push/pop/top), queue is FIFO (push/pop/front/back); both default to deque and are O(1).

  • priority_queue is a binary heap on a vector: max-heap by default, min-heap with std::greater; push/pop O(log n), top O(1).

  • pop() returns void, and accessing an empty adaptor is undefined behavior.

  • C++23 adds iterator-pair constructors for stack/queue and push_range for all three.

Next, in set & map, we move to containers that keep their elements sorted automatically and let us search by key in O(log n).