C++ Stack and Queue

A stack and a queue are two of the most fundamental data structures in computer science, and C++’s Standard Template Library provides ready-made, well-tested implementations of both: std::stack and std::queue. A stack gives you Last-In-First-Out (LIFO) access — the last item you added is the first one you take out — while a queue gives you First-In-First-Out (FIFO) access, just like a real line of people waiting to be served. Understanding these two container adapters is essential for writing algorithms like undo systems, expression parsers, breadth-first search, and task schedulers.

Overview: How Stack and Queue Work

Unlike std::vector or std::deque, std::stack and std::queue are not standalone containers with their own storage and algorithms. They are container adapters: thin wrapper classes that take an existing sequence container (by default std::deque) and restrict its public interface down to only the operations that make sense for LIFO or FIFO access. Internally, when you call push() on a std::stack, the adapter simply forwards the call to push_back() on the underlying container. When you call pop(), it forwards to pop_back(). There is no separate stack algorithm being invented — it is entirely a matter of which end(s) of the underlying container you are allowed to touch.

A stack only ever exposes one end. You can only add elements (push), remove elements (pop), and peek at (top) the most recently added element. A queue exposes both ends but in a fixed division of labor: elements are always added at the back (push) and always removed from the front (front to peek, pop to remove). This is why a queue also gives you a back() function — to peek at the most recently added element without removing anything.

Because both are adapters, neither supports iterators, indexing with [], or range-based for loops. You cannot “look inside” a stack or a queue except through its restricted interface — that is the entire point. This restriction is a feature: it prevents code elsewhere in a large program from accidentally reaching into the middle of what is supposed to be a strictly ordered structure, which keeps LIFO/FIFO invariants easy to reason about.

The default underlying container for both is std::deque (a double-ended queue), because a deque supports O(1) insertion and removal at both ends without invalidating existing elements the way a vector might when it reallocates. You can swap in std::vector (for stack only, since a plain vector can’t efficiently remove from the front) or std::list (for either), as long as the container you choose supports the operations the adapter needs.

Syntax

#include <stack>
#include <queue>

std::stack<int> s1;                        // underlying container: deque (default)
std::stack<int, std::vector<int>> s2;      // underlying container: vector

std::queue<int> q1;                        // underlying container: deque (default)
std::queue<int, std::list<int>> q2;        // underlying container: list

Both class templates take the element type as the first parameter and an optional container type as the second parameter. Their member functions are deliberately minimal:

Stack Member	Effect
push(val)	Adds val to the top
emplace(args...)	Constructs a new top element in place
pop()	Removes the top element (returns nothing)
top()	Returns a reference to the top element
empty()	Returns true if the stack has no elements
size()	Returns the number of elements

Queue Member	Effect
push(val)	Adds val to the back
emplace(args...)	Constructs a new back element in place
pop()	Removes the front element (returns nothing)
front()	Returns a reference to the front element
back()	Returns a reference to the back element
empty()	Returns true if the queue has no elements
size()	Returns the number of elements

Examples

Example 1: Checking Balanced Brackets with a Stack

A classic use of a stack is validating that brackets in an expression are balanced. Every time you see an opening bracket you push it; every time you see a closing bracket you check it against the top of the stack.

#include <iostream>
#include <stack>
#include <string>
using namespace std;

bool isBalanced(const string& expr) {
    stack<char> s;
    for (char c : expr) {
        if (c == '(' || c == '[' || c == '{') {
            s.push(c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (s.empty()) return false;
            char top = s.top();
            s.pop();
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) {
                return false;
            }
        }
    }
    return s.empty();
}

int main() {
    string expr1 = "{[a+(b*c)]-d}";
    string expr2 = "{[a+(b*c)]-d}]";

    cout << expr1 << " -> " << (isBalanced(expr1) ? "Balanced" : "Not Balanced") << endl;
    cout << expr2 << " -> " << (isBalanced(expr2) ? "Balanced" : "Not Balanced") << endl;

    return 0;
}

Output:

{[a+(b*c)]-d} -> Balanced
{[a+(b*c)]-d}] -> Not Balanced

The stack tracks which opening bracket is “currently open.” When a closing bracket arrives, it must match whatever is on top of the stack, otherwise the brackets are mismatched. The second expression has an extra ] after the structure is already balanced, so when the stack is empty and a closing bracket still appears, the function immediately returns false.

Example 2: Simulating a Print Queue

A queue models real-world waiting lines well. Here, print jobs are processed in the exact order they were submitted.

#include <iostream>
#include <queue>
#include <string>
using namespace std;

int main() {
    queue<string> printQueue;

    printQueue.push("Report.pdf");
    printQueue.push("Invoice.docx");
    printQueue.push("Photo.png");

    cout << "Processing print jobs in order received:" << endl;
    while (!printQueue.empty()) {
        cout << "Printing: " << printQueue.front() << endl;
        printQueue.pop();
    }

    cout << "Queue size after processing: " << printQueue.size() << endl;

    return 0;
}

Output:

Processing print jobs in order received:
Printing: Report.pdf
Printing: Invoice.docx
Printing: Photo.png
Queue size after processing: 0

Each call to front() looks at the oldest job still waiting, and pop() removes it. Because jobs are always added at the back and removed from the front, they are always handled in the exact order they arrived — that is the FIFO guarantee.

Example 3: Breadth-First Search with a Queue

Queues are the backbone of breadth-first search (BFS), which explores a graph level by level. This mirrors how a real queue processes people: everyone at the current “distance” is served before anyone further away.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

void bfs(const vector<vector<int>>& graph, int start) {
    vector<bool> visited(graph.size(), false);
    queue<int> q;

    visited[start] = true;
    q.push(start);

    cout << "BFS order: ";
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << " ";

        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
    cout << endl;
}

int main() {
    vector<vector<int>> graph = {
        {1, 2},    // neighbors of 0
        {0, 3},    // neighbors of 1
        {0, 3},    // neighbors of 2
        {1, 2, 4}, // neighbors of 3
        {3}        // neighbors of 4
    };

    bfs(graph, 0);

    return 0;
}

Output:

BFS order: 0 1 2 3 4 

The queue holds nodes that have been discovered but not yet visited. Node 0 is processed first, discovering neighbors 1 and 2 and enqueuing them. Node 1 is processed next, discovering 3. By the time node 3 is processed, neighbor 4 is discovered. Because a queue is FIFO, nodes are always visited in the order they were discovered — which is exactly what gives BFS its level-by-level behavior. If a stack were used instead, you would get depth-first search instead, visiting deeply before broadly.

Under the Hood

Both adapters are template classes defined roughly like this in the standard library headers: they hold a single protected member, the underlying container instance, and every public member function is a small wrapper around that container’s own member functions.

• stack::push(x) calls underlying.push_back(x)
• stack::pop() calls underlying.pop_back()
• stack::top() returns underlying.back()
• queue::push(x) calls underlying.push_back(x)
• queue::pop() calls underlying.pop_front()
• queue::front() returns underlying.front(), queue::back() returns underlying.back()

With the default std::deque, all of these operations run in amortized O(1) time, because a deque is implemented as a sequence of fixed-size memory blocks with an index structure pointing to them, so it can grow at either end without shifting existing elements. This is why deque is the default choice over vector: a vector can push/pop at the back in O(1), but removing from the front would be O(n), which would make queue unacceptably slow.

Because the adapter only exposes a subset of the underlying container’s interface, the compiler enforces the LIFO/FIFO discipline at compile time — there is no begin()/end(), no operator[], and no way to iterate. If you truly need to inspect every element (for debugging, for example), you either redesign your algorithm to not need it, or you use the underlying container type directly instead of the adapter.

Common Mistakes

Mistake 1: Treating pop() as if it returns the removed value

Unlike some other languages’ stack APIs, C++’s pop() returns void. It only removes the element; it does not hand it back to you.

stack<int> s;
s.push(10);
s.push(20);
int x = s.pop(); // ERROR: pop() returns void, this will not compile
cout << x;

The fix is to read the value with top() before removing it with pop():

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> s;
    s.push(10);
    s.push(20);

    int x = s.top(); // read the value first
    s.pop();          // then remove it

    cout << "Popped value: " << x << endl;
    cout << "New top: " << s.top() << endl;

    return 0;
}

Output:

Popped value: 20
New top: 10

Mistake 2: Trying to index into a stack or queue

Because stack and queue deliberately hide the underlying container’s iterators and indexing, code like this will not compile:

queue<int> q;
q.push(1);
q.push(2);
q.push(3);
cout << q[0]; // ERROR: queue has no operator[]

If you need random access, use front()/back() for the ends, or reach for an actual container like vector or deque if you genuinely need to inspect the middle:

#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);

    cout << "Front: " << q.front() << endl;
    cout << "Back: " << q.back() << endl;

    return 0;
}

Output:

Front: 1
Back: 3

Mistake 3: Calling top()/front() without checking empty() first

Calling top() or front() on an empty stack or queue is undefined behavior — it will not throw an exception, it may silently return garbage or crash:

stack<int> s;
cout << s.top(); // UB: the stack is empty, this has no valid element to return

Always guard with empty() before peeking:

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> s;

    if (!s.empty()) {
        cout << s.top() << endl;
    } else {
        cout << "Stack is empty, nothing to show." << endl;
    }

    return 0;
}

Output:

Stack is empty, nothing to show.

Best Practices

• Use stack for LIFO problems: undo/redo history, expression parsing, backtracking, and depth-first search implemented iteratively.
• Use queue for FIFO problems: task scheduling, breadth-first search, buffering/streaming data, and print/job queues.
• Always check empty() before calling top(), front(), or back() — none of them are safe to call on an empty adapter.
• Remember that pop() only removes; retrieve the value first with top()/front() if you still need it.
• Pick the underlying container deliberately: keep the default deque unless you have a specific reason, use vector for a stack when you know you’ll never need front access, and use list when you need guaranteed O(1) operations with stable references to existing elements.
• Prefer emplace() over push() for non-trivial element types to construct in place instead of copying or moving a temporary.
• If you need to inspect, iterate, or search the middle of a collection, do not fight the adapter — use the underlying container type (e.g. vector or deque) directly instead.
• When processing needs to depend on priority rather than arrival order, use std::priority_queue instead of manually sorting a queue.

Practice Exercises

• Write a function reverseString(string s) that reverses a string using only a stack<char> (push every character, then pop them all off into a new string).
• Simulate a customer service line: push a series of customer names into a queue<string>, then pop and print “Serving: name” for each one in order, finally printing the total number of customers served.
• Classic interview problem: implement a queue’s push/pop behavior using two stack<int> objects internally. Hint: keep pushing onto the first stack; when the second stack is empty, dump everything from the first stack into the second (reversing the order) before popping from the second.

Summary

• std::stack and std::queue are container adapters, not standalone data structures — they wrap another sequence container (deque by default) and restrict its interface.
• stack is LIFO: push(), pop(), and top() all operate on one end.
• queue is FIFO: elements are added with push() at the back and removed with pop() from the front; front() and back() peek at either end.
• Neither supports iteration, indexing, or random access — that restriction is intentional and enforces the LIFO/FIFO discipline at compile time.
• pop() returns nothing; read the value with top()/front() before removing it.
• Always check empty() before peeking — calling top()/front() on an empty adapter is undefined behavior.
• Choose the underlying container based on your performance needs; deque is the sensible default for both.
• Use stack for undo/backtracking/DFS-style problems and queue for scheduling/BFS-style problems; reach for priority_queue when order should depend on priority.