Skip to content

Stack, Queue, Priority Queue — Container Adaptors and Underlying Containers

DodaTech Updated 2026-06-28 7 min read

In this tutorial, you will learn about Stack, Queue, Priority Queue. We cover key concepts, practical examples, and best practices to help you master this topic.

C++ stack, queue, and priority_queue are container adaptors that wrap sequence containers (vector, deque, list) with restricted interfaces for LIFO, FIFO, and priority-based element access.

What You'll Learn

You will use std::stack for LIFO (last-in-first-out) operations, use std::queue for FIFO (first-in-first-out) operations, use std::priority_queue for heap-based priority ordering, customize the underlying container for each adaptor, provide custom comparison for priority ordering, and implement a monotonic stack for algorithmic problem solving.

Why It Matters

Container adaptors simplify code by providing exactly the interface you need. They prevent accidental misuse of the full container API. priority_queue is the go-to data structure for scheduling, pathfinding, and any algorithm that needs to repeatedly extract the maximum or minimum element.

Learning Path

graph LR
    A["33: Map & Multimap"] --> B["34: Stack, Queue, Priority Queue"]
    B --> C["35: String & Span"]
    C --> D["36: Algorithms Overview"]
    style A fill:#4a90d9,stroke:#2c5f8a,color:#fff
    style B fill:#4a90d9,stroke:#2c5f8a,color:#fff
    style C fill:#4a90d9,stroke:#2c5f8a,color:#fff
    style D fill:#4a90d9,stroke:#2c5f8a,color:#fff

std::stack

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

int main() {
    std::stack<int> s;  // default: deque
    
    s.push(10);
    s.push(20);
    s.push(30);
    
    std::cout << "Top: " << s.top() << "\n";  // 30
    
    s.pop();  // removes 30
    
    std::cout << "Size: " << s.size() << "\n";
    std::cout << "Top: " << s.top() << "\n";  // 20
    
    // Custom underlying container
    std::stack<int, std::vector<int>> vecStack;
    vecStack.push(1);
    vecStack.push(2);
    
    // Iterate (destructive)
    while (!s.empty()) {
        std::cout << s.top() << " ";
        s.pop();
    }
    std::cout << "\n";
}

Stack operations: push(), pop(), top(), empty(), size().

std::queue

#include <iostream>
#include <queue>
#include <list>

int main() {
    std::queue<int> q;  // default: deque
    
    q.push(10);
    q.push(20);
    q.push(30);
    
    std::cout << "Front: " << q.front() << "\n";  // 10
    std::cout << "Back: " << q.back() << "\n";    // 30
    
    q.pop();  // removes 10
    
    std::cout << "Front: " << q.front() << "\n";  // 20
    
    // Custom underlying container
    std::queue<int, std::list<int>> listQueue;
    listQueue.push(1);
    listQueue.push(2);
    
    // Iterate (destructive)
    while (!q.empty()) {
        std::cout << q.front() << " ";
        q.pop();
    }
    std::cout << "\n";
}

Queue operations: push(), pop(), front(), back(), empty(), size().

std::priority_queue

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

int main() {
    // Max heap (default)
    std::priority_queue<int> pq;
    
    pq.push(30);
    pq.push(10);
    pq.push(50);
    pq.push(20);
    pq.push(40);
    
    std::cout << "Top: " << pq.top() << "\n";  // 50
    
    pq.pop();  // removes 50
    
    std::cout << "Top: " << pq.top() << "\n";  // 40
    
    // Min heap
    std::priority_queue<int, std::vector<int>, std::greater<int>> minPq;
    minPq.push(30);
    minPq.push(10);
    minPq.push(50);
    std::cout << "Min top: " << minPq.top() << "\n";  // 10
    
    // Custom comparator
    struct CustomCompare {
        bool operator()(int a, int b) const {
            return (a % 10) > (b % 10);  // sort by last digit
        }
    };
    std::priority_queue<int, std::vector<int>, CustomCompare> customPq;
    customPq.push(23);
    customPq.push(45);
    customPq.push(12);
    customPq.push(38);
    
    while (!customPq.empty()) {
        std::cout << customPq.top() << " ";  // smallest last digit first
        customPq.pop();
    }
    std::cout << "\n";
}

Container Adaptor Characteristics

Adaptor Underlying Default Allowed Containers Key Operations
stack deque deque, vector, list push, pop, top
queue deque deque, list push, pop, front, back
priority_queue vector vector, deque push, pop, top

Customizing priority_queue

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

struct Task {
    int priority;
    std::string description;
};

struct TaskCompare {
    bool operator()(const Task& a, const Task& b) const {
        return a.priority < b.priority;  // higher priority first (max heap)
    }
};

int main() {
    std::priority_queue<Task, std::vector<Task>, TaskCompare> taskQueue;
    
    taskQueue.push({3, "Low priority"});
    taskQueue.push({5, "High priority"});
    taskQueue.push({4, "Medium priority"});
    taskQueue.push({1, "Lowest priority"});
    
    while (!taskQueue.empty()) {
        const auto& task = taskQueue.top();
        std::cout << task.priority << ": " << task.description << "\n";
        taskQueue.pop();
    }
}

Monotonic Stack Example

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

// Find the next greater element for each element in the array
std::vector<int> nextGreaterElement(const std::vector<int>& arr) {
    std::vector<int> result(arr.size(), -1);
    std::stack<size_t> s;  // stack of indices
    
    for (size_t i = 0; i < arr.size(); ++i) {
        while (!s.empty() && arr[s.top()] < arr[i]) {
            result[s.top()] = arr[i];
            s.pop();
        }
        s.push(i);
    }
    
    return result;
}

int main() {
    std::vector<int> arr = {13, 7, 6, 12};
    auto result = nextGreaterElement(arr);
    
    for (size_t i = 0; i < arr.size(); ++i) {
        std::cout << arr[i] << " -> " << result[i] << "\n";
    }
}

Expected output:

13 -> -1
7 -> 12
6 -> 12
12 -> -1

Common Mistakes

Mistake 1: Accessing top() or front() on Empty Adaptor

std::stack<int> s;
// s.top();  // undefined behavior if empty

Always check !empty() first.

Mistake 2: Forgetting pop() Does Not Return Value

int val = s.pop();  // Error: pop returns void
int val = s.top(); s.pop();  // correct

Mistake 3: Using Wrong Comparator for priority_queue

std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;  // min heap
std::priority_queue<int> maxHeap;  // max heap (default)

std::greater creates a min heap because priority_queue uses the comparator as "less than" for ordering.

Mistake 4: Modifying Elements After Push

auto& top = pq.top();
top = 999;  // may break the heap property!

Push a modified copy instead.

Mistake 5: Using stack When vector Would Suffice

If you only need to access the most recently added element, stack adds safety by restricting the interface. But if you later need iteration, vector is more flexible.

Mistake 6: Expecting priority_queue Iteration in Order

priority_queue does not support iteration. To get elements in order, you must repeatedly pop().

Practice Questions

  1. What is a container adaptor and why would you use one instead of the underlying container?
  2. How would you implement a min-heap using priority_queue?
  3. Write a function that checks if a string of parentheses is balanced using a stack.
  4. What underlying containers can a queue use? Why not vector?
  5. Implement a simple task scheduler using priority_queue.

Challenge

Use a priority queue to implement the "merge k sorted lists" algorithm. Given k sorted vectors, merge them into a single sorted vector using a min-heap of iterators.

FAQ

Why is there no `std::array` adaptor for stack?

std::array has a fixed size and cannot grow. Container adaptors need push/pop which require dynamic size changes.

Can I iterate over a stack without modifying it?

No, the stack interface intentionally prevents non-destructive iteration. If you need iteration, use the underlying container directly.

What is the time complexity of priority_queue operations?

push(): O(log n), pop(): O(log n), top(): O(1). These are guaranteed by the heap property.

Is `std::stack` LIFO always?

Yes. The stack adaptor enforces strict LIFO (last-in-first-out) order regardless of the underlying container.

What is 'heap' in the context of priority_queue?

A binary heap is a complete binary tree where each parent is greater (max heap) or smaller (min heap) than its children. It is stored compactly in a vector.

Can I use `std::list` as the underlying container for `priority_queue`?

No. priority_queue requires random access iterators for heap operations. std::list provides only bidirectional iterators.

Mini Project

Build a simple expression evaluator using a stack:

#include <iostream>
#include <stack>
#include <string>
#include <sstream>
#include <cctype>

int evaluate(const std::string& expression) {
    std::stack<int> values;
    std::stack<char> ops;
    
    auto applyOp = [](int a, int b, char op) {
        switch (op) {
            case '+': return a + b;
            case '-': return a - b;
            case '*': return a * b;
            case '/': return b != 0 ? a / b : 0;
            default: return 0;
        }
    };
    
    auto precedence = [](char op) {
        return (op == '+' || op == '-') ? 1 : 2;
    };
    
    std::istringstream stream(expression);
    char token;
    
    while (stream >> token) {
        if (std::isdigit(token)) {
            stream.putback(token);
            int value;
            stream >> value;
            values.push(value);
        } else if (token == '(') {
            ops.push(token);
        } else if (token == ')') {
            while (!ops.empty() && ops.top() != '(') {
                int b = values.top(); values.pop();
                int a = values.top(); values.pop();
                values.push(applyOp(a, b, ops.top()));
                ops.pop();
            }
            if (!ops.empty()) ops.pop();  // remove '('
        } else if (token == '+' || token == '-' || token == '*' || token == '/') {
            while (!ops.empty() && precedence(ops.top()) >= precedence(token)) {
                int b = values.top(); values.pop();
                int a = values.top(); values.pop();
                values.push(applyOp(a, b, ops.top()));
                ops.pop();
            }
            ops.push(token);
        }
    }
    
    while (!ops.empty()) {
        int b = values.top(); values.pop();
        int a = values.top(); values.pop();
        values.push(applyOp(a, b, ops.top()));
        ops.pop();
    }
    
    return values.top();
}

int main() {
    std::cout << evaluate("3 + 4 * 2") << "\n";        // 11
    std::cout << evaluate("( 3 + 4 ) * 2") << "\n";    // 14
    std::cout << evaluate("10 / 2 + 3 * 4") << "\n";   // 17
}

What's Next

Container adaptors simplify common data structure patterns. The next lesson covers string_view and span: non-owning views into character and contiguous data sequences.

← Previous Map and Multimap — Ordered and Unordered Maps, emplace, try_emplace Next → String and Span — std::string_view, std::span, String Operations

Built by the developers of DodaTech

Doda Browser, DodaZIP & Durga Antivirus Pro

Home Browse Cpp