stack and queue in C++ STL

A stack is last-in, first-out (LIFO): like a pile of plates, you take the one you put down last. A queue is first-in, first-out (FIFO): like a line at a counter. The STL provides both as container adapters – thin wrappers around a deque that expose only the operations that make sense. They're the backbone of undo systems, expression parsing, BFS and many interview problems.

std::stack

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

int main() {
    std::stack<std::string> history;          // browser back button
    history.push("home");
    history.push("courses");
    history.push("cpp-stl");
    std::cout << "current: " << history.top() << ", depth " << history.size() << '\n';

    history.pop();                             // pop removes but returns nothing
    std::cout << "back to: " << history.top() << '\n';

    while (!history.empty()) {                 // always check empty() before top()/pop()
        std::cout << "leaving " << history.top() << '\n';
        history.pop();
    }
    return 0;
}

current: cpp-stl, depth 3
back to: courses
leaving courses
leaving home

Balanced brackets

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

bool balanced(const std::string& s) {
    std::stack<char> open;
    for (char c : s) {
        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();                       // nothing left unclosed
}

int main() {
    for (std::string s : {"{[()()]}", "([)]", "((a + b) * c", "v[i] = f(x);"}) {
        std::cout << s << " -> " << (balanced(s) ? "balanced" : "not balanced") << '\n';
    }
    return 0;
}

{[()()]} -> balanced
([)] -> not balanced
((a + b) * c -> not balanced
v[i] = f(x); -> balanced

Next greater element: the monotonic stack

For each element, find the next element to its right that's larger. Comparing every pair is O(n²); a stack that keeps "waiting" elements in decreasing order does it in O(n), because each element is pushed and popped at most once:

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

std::vector<int> next_greater(const std::vector<int>& a) {
    std::vector<int> result(a.size(), -1);
    std::stack<int> waiting;                          // indexes still waiting for a greater value
    for (int i = 0; i < static_cast<int>(a.size()); i++) {
        while (!waiting.empty() && a[waiting.top()] < a[i]) {
            result[waiting.top()] = a[i];             // a[i] is their next greater element
            waiting.pop();
        }
        waiting.push(i);
    }
    return result;
}

int main() {
    std::vector<int> prices{73, 74, 75, 71, 69, 72, 76, 73};
    auto ng = next_greater(prices);
    for (std::size_t i = 0; i < prices.size(); i++) std::cout << prices[i] << "->" << ng[i] << ' ';
    std::cout << '\n';
    return 0;
}

73->74 74->75 75->76 71->72 69->72 72->76 76->-1 73->-1 

std::queue

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

int main() {
    std::queue<std::string> printer;            // print jobs in arrival order
    printer.push("report.pdf");
    printer.push("photo.png");
    printer.push("notes.txt");
    std::cout << "next: " << printer.front() << ", last: " << printer.back() << '\n';

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

    std::queue<int> q;                           // simulate a round-robin scheduler
    for (int job : {1, 2, 3}) q.push(job);
    int remaining[4] = {0, 2, 1, 3};             // time slices each job needs
    while (!q.empty()) {
        int job = q.front();
        q.pop();
        std::cout << job << ' ';
        if (--remaining[job] > 0) q.push(job);   // not finished: back of the line
    }
    std::cout << '\n';
    return 0;
}

next: report.pdf, last: notes.txt
printing report.pdf
printing photo.png
printing notes.txt
1 2 3 1 3 3 

Queues model anything processed in arrival order – job schedulers, message queues, and breadth-first search, which explores a graph level by level (chapter 11).

Practice

Summary

Interview practice: stack and queue problems.