IntermediatePractice in the editor

C++ Stack and Queue

std::stack, std::queue and std::priority_queue are container adapters: they wrap another container and allow only the operations their idea needs. That makes the code say exactly how the data is used.

stack: last in, first out

A stack works like a pile of plates: you add on top (push), look at the top (top) and remove from the top (pop). The last element added is the first one out.

ExampleTry it in the editor

#include <iostream>
#include <stack>

int main() {
    std::stack<int> s;
    s.push(1);
    s.push(2);
    s.push(3);
    while (!s.empty()) {
        std::cout << s.top() << " ";
        s.pop();
    }
    std::cout << "\n";
    return 0;
}

Output

3 2 1

pop removes the element but does not return it; read it with top first. Calling top or pop on an empty stack is a bug, so check empty().

A classic use is checking that brackets are balanced:

ExampleTry it in the editor

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

bool balanced(const std::string& 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 t : {"(a[b]{c})", "(a[b)]", "((x)"}) {
        std::cout << t << ": " << (balanced(t) ? "balanced" : "not balanced") << "\n";
    }
    return 0;
}

Output

(a[b]{c}): balanced
(a[b)]: not balanced
((x): not balanced

queue: first in, first out

A queue works like a line at a counter: elements join at the back (push) and leave from the front (front, pop).

ExampleTry it in the editor

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

int main() {
    std::queue<std::string> line;
    line.push("Asha");
    line.push("Ravi");
    line.push("Kiran");
    while (!line.empty()) {
        std::cout << "Serving " << line.front() << "\n";
        line.pop();
    }
    return 0;
}

Output

Serving Asha
Serving Ravi
Serving Kiran

priority_queue: the most important first

A priority_queue always gives the largest element first, whatever the order they were added in. With std::greater it gives the smallest first instead.

ExampleTry it in the editor

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

int main() {
    std::priority_queue<int> high;
    for (int x : {5, 1, 8, 3}) high.push(x);
    std::priority_queue<int, std::vector<int>, std::greater<int>> low;
    for (int x : {5, 1, 8, 3}) low.push(x);
    std::cout << "largest first: ";
    while (!high.empty()) { std::cout << high.top() << " "; high.pop(); }
    std::cout << "\nsmallest first: ";
    while (!low.empty()) { std::cout << low.top() << " "; low.pop(); }
    std::cout << "\n";
    return 0;
}

Output

largest first: 8 5 3 1 
smallest first: 1 3 5 8

Priority queues schedule tasks by urgency and are the heart of path-finding algorithms such as Dijkstra's.

Which one to choose

These three are container adaptors: they wrap a deque or vector and allow only the operations that fit their rule. Use a stack for undo histories, matching brackets and depth-first search; a queue for jobs handled in arrival order and breadth-first search; a priority_queue for scheduling by importance and for algorithms such as Dijkstra's shortest path. Calling top(), front() or pop() on an empty one is undefined behaviour, so always check empty() first.

Practice exercises

Reverse a word using a stack<char>.
Simulate a printer queue: add five documents and print them in order.
Keep the three highest scores from a list using a priority_queue.