C++ Stack and Queue

std::stack and std::queue are STL container adaptors that limit how you access stored values. A stack uses last-in, first-out order, while a queue uses first-in, first-out order.

They are called adaptors because they usually use another container internally, such as std::deque. As a beginner, you can focus on their simple public functions: add, inspect, remove, and check size.

Using a Stack

A stack works like a pile of plates. The last value you push onto the stack is the first value you can take off. To use one, include the <stack> header.

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

int main(void) {
    std::stack<std::string> history;

    history.push("Home");
    history.push("Products");
    history.push("Checkout");

    std::cout << "Current page: " << history.top() << std::endl;

    history.pop();

    std::cout << "After back: " << history.top() << std::endl;
    std::cout << "Pages stored: " << history.size() << std::endl;

    return 0;
}

Output:

Current page: Checkout
After back: Products
Pages stored: 2

The stack stores Home, then Products, then Checkout. The top() function reads the most recently added value. The pop() function removes that value, so the new top becomes Products.

Important Stack Functions

Function	What it does
push(value)	Adds a value to the top
pop()	Removes the top value
top()	Returns the top value
size()	Returns the number of values
empty()	Returns whether the stack has no values

Call top() or pop() only when the stack is not empty. A common pattern is to check empty() before reading or removing a value.

Using a Queue

A queue works like a line of people waiting for service. The first value added is the first value removed. To use one, include the <queue> header.

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

int main(void) {
    std::queue<std::string> orders;

    orders.push("Order 1001");
    orders.push("Order 1002");
    orders.push("Order 1003");

    std::cout << "Next: " << orders.front() << std::endl;
    std::cout << "Newest: " << orders.back() << std::endl;

    orders.pop();

    std::cout << "After serving one:" << std::endl;
    while (!orders.empty()) {
        std::cout << orders.front() << std::endl;
        orders.pop();
    }

    return 0;
}

Output:

Next: Order 1001
Newest: Order 1003
After serving one:
Order 1002
Order 1003

The queue keeps the oldest order at the front and the newest order at the back. After pop() removes Order 1001, the loop processes the remaining orders in the same order they were added.

Important Queue Functions

Function	What it does
push(value)	Adds a value to the back
pop()	Removes the front value
front()	Returns the next value to be removed
back()	Returns the most recently added value
size()	Returns the number of values
empty()	Returns whether the queue has no values

Stack vs Queue

Container	Order	Common use
std::stack	Last in, first out	Undo steps, browser history, nested parsing
std::queue	First in, first out	Task lists, waiting lines, processing messages

Use a stack when the most recent item should be handled first. Use a queue when the oldest waiting item should be handled first.

Takeaway: std::stack gives you LIFO access, and std::queue gives you FIFO access.