Data Structures

Reviewed & published by Brayan K

By the end of this lesson you'll reach for the right container without thinking: a stack for last-in-first-out, a queue for first-in-first-out, a priority_queue when the biggest (or smallest) item must come out next, plus deque, list, and pair/tuple for everything in between.

Part of the free C++ course at LearnCodingFast — hands-on lessons with worked examples and the output they print, plus practice exercises and a quick quiz.

What You'll Learn

• Use std::stack (LIFO) with push, top, and pop
• Use std::queue (FIFO) with push, front, and pop
• Pick a max- or min-heap with std::priority_queue
• Add and remove at both ends with std::deque
• Walk a std::list (doubly linked list) and a hand-built node chain
• Group values with std::pair and std::tuple

💡 Real-World Analogy

Think about a coffee shop. A stack is the pile of clean plates by the till — you take the top one, which was the last one washed (LIFO). The queue is the line of customers — whoever arrived first gets served first (FIFO). The priority queue is the barista's order screen: the most urgent drink jumps to the top no matter when it was ordered (a heap). Same coffee shop, three different rules for "who's next" — and choosing the right rule is what data structures are really about.

📊 Which Container, When?

stack, queue, and priority_queue are container adaptors — they wrap a deque or vector and only expose the operations the rule allows. That restriction is the point: it makes your intent obvious and prevents misuse.

1. std::stack — Last In, First Out

A stack only lets you work at one end, the top. You push a value on, you pop the top one off, and you top() to peek at it. The last thing you pushed is the first thing back out — that's LIFO. It's perfect for anything that unwinds in reverse: an undo history, the call stack, or matching brackets. Read this worked example and run it.

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

int main() {
    // A stack is LIFO: Last In, First Out — like a stack of plates.
    // You only ever touch the TOP.
    stack<int> s;

    s.push(10);   // stack (bottom->top): 10
    s.push(20);   // stack: 10, 20
    s.push(30);   // stack: 10, 20, 30

    // top() = look at the top WITHOUT removing it.
    cout << "Top is " << s.top() << endl;   // Top is 30

    // pop() REMOVES the top but returns nothing (void).
    s.pop();                                 // removes 30
    cout << "After pop, top is " << s.top() << endl; // Top is 20

    cout << "Size: " << s.size() << endl;    // Size: 2

    // Drain the stack — items come out in REVERSE insert order.
    cout << "Draining: ";
    while (!s.empty()) {     // ALWAYS guard pop/top with !empty()
        cout << s.top() << " ";   // 20  then  10
        s.pop();
    }
    cout << endl;            // Draining: 20 10
    return 0;
}

// ✅ Expected output:
//    Top is 30
//    After pop, top is 20
//    Size: 2
//    Draining: 20 10

Your turn. A stack is the natural way to reverse a sequence — push it all in, pop it all out. Fill in the two blanks marked ____ using the hints, then run it.

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

int main() {
    // 🎯 YOUR TURN — replace each ___ then press "Try it Yourself".
    // Goal: reverse the word "CODE" using a stack (LIFO).
    stack<char> s;

    // 1) Push every character of "CODE" onto the stack.
    for (char c : string("CODE")) {
        s.____(c);          // 👉 the method that adds to a stack is push
    }

    // 2) Pop them all off — they come out reversed.
    cout << "Reversed: ";
    while (!s.empty()) {
        cout << s.____();   // 👉 read the TOP character
        s.pop();            // then remove it
    }
    cout << endl;

    // ✅ Expected output:  Reversed: EDOC
    return 0;
}

2. std::queue — First In, First Out

A queue is the opposite discipline: you push to the back and remove from the front, so whoever arrived first leaves first — FIFO. You read the next item with front() (and can peek at the most recent with back()), then pop() removes the front. Use a queue whenever order of arrival must be respected: print jobs, message buffers, or a breadth-first search.

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

int main() {
    // A queue is FIFO: First In, First Out — like a line at a shop.
    // You add at the BACK and remove from the FRONT.
    queue<string> line;

    line.push("Alice");   // front -> Alice
    line.push("Bob");     // front -> Alice, Bob
    line.push("Carol");   // front -> Alice, Bob, Carol

    cout << "Next up: " << line.front() << endl;  // Next up: Alice
    cout << "Last in: " << line.back()  << endl;  // Last in: Carol

    // Serve everyone in arrival order.
    cout << "Serving order: ";
    while (!line.empty()) {
        cout << line.front() << " ";  // Alice  Bob  Carol
        line.pop();                   // pop() removes the FRONT here
    }
    cout << endl;         // Serving order: Alice Bob Carol
    return 0;
}

// ✅ Expected output:
//    Next up: Alice
//    Last in: Carol
//    Serving order: Alice Bob Carol

Now you try. A printer serves jobs in the order they were sent. Fill in the two blanks so each job is read from the front and then removed:

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

int main() {
    // 🎯 YOUR TURN — a printer serves jobs First In, First Out.
    queue<string> jobs;
    jobs.push("report.pdf");
    jobs.push("photo.png");
    jobs.push("invoice.pdf");

    cout << "Printing order: ";
    while (!jobs.empty()) {
        // 1) Print the job at the FRONT of the queue.
        cout << jobs.____() << " ";   // 👉 read the FRONT element

        // 2) Remove that job so the next one moves up.
        jobs.____();                  // 👉 remove the front (pop)
    }
    cout << endl;

    // ✅ Expected output:  Printing order: report.pdf photo.png invoice.pdf
    return 0;
}

3. std::priority_queue — Biggest First (a Heap)

A priority queue ignores arrival order entirely. It's backed by a heap, so top() always hands you the highest-priority element, and pop() removes it. By default it's a max-heap — the largest value comes out first. Want the smallest first? Declare it with greater<int> to make a min-heap. Heaps power task schedulers, Dijkstra's shortest path, and "find the top K" problems.

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

int main() {
    // A priority_queue is a HEAP: top() is always the largest item.
    // By DEFAULT it is a MAX-heap (biggest comes out first).
    priority_queue<int> pq;

    for (int v : {42, 17, 93, 5, 68}) pq.push(v);

    cout << "Top (largest): " << pq.top() << endl;  // Top (largest): 93

    cout << "Pop order (high->low): ";
    while (!pq.empty()) {
        cout << pq.top() << " ";   // 93 68 42 17 5
        pq.pop();
    }
    cout << endl;

    // Want SMALLEST first? Flip it to a MIN-heap with greater<int>.
    priority_queue<int, vector<int>, greater<int>> minHeap;
    for (int v : {42, 17, 93, 5, 68}) minHeap.push(v);

    cout << "Min-heap top: " << minHeap.top() << endl;  // Min-heap top: 5
    return 0;
}

// ✅ Expected output:
//    Top (largest): 93
//    Pop order (high->low): 93 68 42 17 5
//    Min-heap top: 5

4. std::deque and std::list

A deque (say "deck", short for double-ended queue) lets you push_front/push_back and pop_front/pop_back — fast at both ends — and you can still index it like a vector. A list is a doubly linked list: each element knows its neighbours, so inserting or erasing in the middle is cheap, but there's no list[3] — you have to walk it. Reach for deque by default; pick list only when you do a lot of middle-of-the-sequence editing.

#include <iostream>
#include <deque>
#include <list>
using namespace std;

int main() {
    // ---- std::deque: a double-ended queue. Push/pop at BOTH ends. ----
    deque<int> dq;
    dq.push_back(2);    // dq: 2
    dq.push_front(1);   // dq: 1, 2
    dq.push_back(3);    // dq: 1, 2, 3
    cout << "deque front=" << dq.front()
         << " back=" << dq.back() << endl;   // front=1 back=3
    dq.pop_front();     // dq: 2, 3   (removed the 1)
    cout << "after pop_front, front=" << dq.front() << endl; // front=2

    // ---- std::list: a doubly linked list. Fast insert ANYWHERE. ----
    list<string> tasks{"wake", "code"};
    tasks.push_back("sleep");        // wake, code, sleep
    tasks.push_front("coffee");      // coffee, wake, code, sleep
    cout << "Task order: ";
    for (const string& t : tasks)    // you walk a list, you can't index it
        cout << t << " ";
    cout << endl;   // Task order: coffee wake code sleep
    return 0;
}

// ✅ Expected output:
//    deque front=1 back=3
//    after pop_front, front=2
//    Task order: coffee wake code sleep

5. std::pair and std::tuple

Sometimes you just need to glue a few values together — a name and a score, a product with its quantity and price. A pair holds exactly two values you reach with .first and .second. A tuple holds two, three, or more, read with get<0>(), get<1>(), and so on. Since C++17, structured bindings let you unpack them straight into named variables — much easier to read.

#include <iostream>
#include <utility>   // pair
#include <tuple>     // tuple
using namespace std;

int main() {
    // pair groups exactly TWO values of any types.
    pair<string, int> player = {"Zoe", 99};
    cout << player.first << " scored " << player.second << endl; // Zoe scored 99

    // tuple groups 2, 3, 4... values. Read them with get<index>().
    tuple<string, int, double> record = {"Widget", 5, 2.50};
    cout << get<0>(record) << ": "
         << get<1>(record) << " @ £"
         << get<2>(record) << endl;          // Widget: 5 @ £2.5

    // structured bindings (C++17) unpack a tuple into named variables:
    auto [name, qty, price] = record;
    cout << name << " total = £" << qty * price << endl; // Widget total = £12.5
    return 0;
}

// ✅ Expected output:
//    Zoe scored 99
//    Widget: 5 @ £2.5
//    Widget total = £12.5

🔎 Deep Dive: Under the Hood — a Hand-Built Linked List

So how does a linked list actually work? Each element is a Node that stores a value and a pointer (next) to the following node. The last node points to nullptr, which is how you know you've reached the end. There's no array behind it — the nodes can sit anywhere in memory, linked only by those pointers. That's exactly why you can't write list[3]: to reach the fourth node you must hop from node to node.

You'd rarely build this yourself — std::list does it for you and manages memory safely. But writing it once makes the idea click.

#include <iostream>
using namespace std;

// A hand-rolled singly linked list to SHOW the concept behind std::list.
// Each Node holds a value and a pointer to the NEXT node (or nullptr at the end).
struct Node {
    int value;
    Node* next;
    Node(int v) : value(v), next(nullptr) {}
};

int main() {
    // Build:  10 -> 20 -> 30 -> nullptr
    Node* head = new Node(10);
    head->next = new Node(20);
    head->next->next = new Node(30);

    // Walk the chain by following 'next' until it's nullptr.
    cout << "List: ";
    for (Node* cur = head; cur != nullptr; cur = cur->next)
        cout << cur->value << " -> ";   // 10 -> 20 -> 30 ->
    cout << "nullptr" << endl;

    // Clean up — every 'new' needs a matching 'delete'.
    while (head) {
        Node* tmp = head;
        head = head->next;
        delete tmp;
    }
    return 0;
}

// ✅ Expected output:
//    List: 10 -> 20 -> 30 -> nullptr

Note the cleanup loop: every new needs a matching delete. In real code you'd use a std::unique_ptr<Node> for next so the chain frees itself — or just use std::list.

Pro Tips

• 💡 Always guard with !empty() before top()/front()/pop(). Calling them on an empty container is undefined behaviour, not an error.
• 💡 pop() returns nothing. Read the value first with top() (stack/priority_queue) or front() (queue), then pop().
• 💡 Need the smallest out first? A priority_queue is a max-heap by default — add greater<int> for a min-heap.
• 💡 Default to deque over list — it's faster for almost everything unless you're constantly inserting in the middle.

Common Errors (and the fix)

• Popping an empty container: s.pop(); when s is empty is undefined behaviour — it may crash, corrupt memory, or silently "work". Always wrap it: if (!s.empty()) s.pop();
• "error: void value not ignored as it ought to be": you wrote int x = s.pop();. pop() returns void. Read with top() first: int x = s.top(); s.pop();
• Smallest came out last: you expected a min-heap but priority_queue<int> is a max-heap. Use priority_queue<int, vector<int>, greater<int>>.
• "no member named 'front' in 'std::stack'": a stack only has top(); only a queue has front()/back(). Use the method that matches the container.
• "no match for 'operator[]'" on a list: std::list has no index access. Walk it with a range-based for loop or an iterator instead.

📋 Quick Reference

Mini-Challenge: Balanced Brackets

No blanks this time — just a brief and an outline. This is the classic stack problem: a string of brackets is balanced when every ) closes an earlier (. Push on open, pop on close, and check the stack is empty at the end. Build it, run it, and check it against the expected results in the comments.

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

int main() {
    // 🎯 MINI-CHALLENGE: Balanced brackets
    // Check whether a string of brackets is balanced, e.g. "(()())".
    //
    // 1. Make a stack<char>.
    // 2. Walk through each character of the expression:
    //      - if it's '(' , push it onto the stack.
    //      - if it's ')' , the stack must NOT be empty (guard first!),
    //        then pop one '(' off.  If it IS empty -> unbalanced.
    // 3. After the loop, it's balanced ONLY if the stack is empty.
    //
    // ✅ Expected: "(()())" -> Balanced ,  "(()" -> Not balanced

    string expr = "(()())";
    stack<char> s;

    // your code here

    return 0;
}

🎉 Lesson Complete

• ✅ stack is LIFO — push, top, pop; great for reversing and backtracking
• ✅ queue is FIFO — push to back, front, pop from front
• ✅ priority_queue is a heap — max-heap by default, greater<int> for min-heap
• ✅ deque adds/removes at both ends; list is a linked list you walk
• ✅ pair and tuple bundle values; unpack with structured bindings
• ✅ Always guard top/front/pop with !empty() — empty access is undefined behaviour

Practice quiz

Continue this course

• Previous: Writing High-Performance Code: Cache Lines, Branch Prediction, SIMD
• Next: Best Practices for Header Files, Forward Declarations & Dependencies — Manage includes, avoid cyclic dependencies, and keep compile times fast
• Quick reference: C++ cheat sheet

Frequently asked questions

When should I use a stack vs a queue?

Use a stack (LIFO) when the most recent item should be handled first — undo history, function calls, backtracking, reversing. Use a queue (FIFO) when items should be handled in arrival order — print jobs, task buffers, breadth-first search.

Why does pop() not return the value it removes?

In C++, top()/front() read the value and pop() removes it as two separate calls. This is a deliberate design: returning-and-removing in one step could lose data if the copy threw an exception. So you read with top() (stack) or front() (queue) first, then call pop() to discard it.

Is std::priority_queue a min-heap or a max-heap?

By default it is a MAX-heap — top() gives the largest element. To get the smallest first, declare it as priority_queue<int, vector<int>, greater<int>>, which turns it into a min-heap.

What's the difference between std::deque and std::list?

A deque (double-ended queue) supports fast push/pop at both ends and random access by index (dq[3]). A list is a doubly linked list: fast insert/erase anywhere you already have an iterator, but no index access — you must walk it. Reach for deque first; use list only when you insert/remove in the middle a lot.

Should I ever write my own linked list?

Almost never in production — std::list, std::deque, and std::vector cover real needs and manage memory for you. Hand-rolling a Node with raw pointers is worth doing once to understand how nodes link together, but in real code prefer the standard containers (and smart pointers if you do build one).

Related lessons

• vectors and basic containers