Courses/C++/Data Structures

Lesson • Intermediate Track

Data Structures in C++

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.

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

Before you start: you should be comfortable with vectors and basic containers and with for loops. Everything here builds on a sequence of elements — we're just choosing how you're allowed to add and remove them.

💡 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?

Container	Rule	You touch	Reach for it when
stack	LIFO	top only	Undo, backtracking, reversing
queue	FIFO	front & back	Buffers, scheduling, BFS
priority_queue	heap	top (max)	"Biggest/smallest next"
deque	both ends	front & back + index	Sliding windows, double-ended
list	linked	anywhere (no index)	Lots of mid-sequence inserts
pair / tuple	fixed group	.first / get<N>	Returning 2+ values together

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.

Worked example: a stack of plates

Read every comment, run it, and check the output matches.

Try it Yourself »

C++

#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();     
...

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.

🎯 Your turn: reverse a word with a stack

Fill in the ____ method names, then check your output against the expected line.

Try it Yourself »

C++

#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()) {
  
...

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.

Worked example: a queue at the shop

See how front() and back() differ from a stack's top().

Try it Yourself »

C++

#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: 
...

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:

🎯 Your turn: a print queue

Read the front job, then pop it — repeat until the queue is empty.

Try it Yourself »

C++

#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
...

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.

Worked example: max-heap then min-heap

Watch the default max-heap, then flip it with greater<int>.

Try it Yourself »

C++

#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
        
...

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.

Worked example: deque and list

Push and pop at both ends; walk a linked list.

Try it Yourself »

C++

#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() <
...

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.

Worked example: pair, tuple & structured bindings

Group values, then unpack them with auto [a, b, c].

Try it Yourself »

C++

#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) << " @ £"
      
...

🔎 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.

Worked example: a singly linked list from scratch

Build a 10 -> 20 -> 30 chain by hand, then free it.

Try it Yourself »

C++

#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 
...

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

Goal	Code	Notes
Add to stack	s.push(x)	goes on top
Peek stack top	s.top()	does not remove
Remove stack top	s.pop()	returns void
Read queue front	q.front()	next to leave
Max-heap	priority_queue<int>	largest first (default)
Min-heap	priority_queue<int, vector<int>, greater<int>>	smallest first
Both ends	dq.push_front(x)	deque only
Group two values	pair<A,B>{a, b}	.first / .second

Frequently Asked Questions

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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).

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.

🎯 Mini-Challenge: are the brackets balanced?

Use a stack to validate (()()) and reject (().

Try it Yourself »

C++

#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. A
...

🎉 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
✅ Next lesson: High-Performance Code — make these structures fly

Data Structures in C++

What You'll Learn

💡 Real-World Analogy

📊 Which Container, When?

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

Worked example: a stack of plates

🎯 Your turn: reverse a word with a stack

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

Worked example: a queue at the shop

🎯 Your turn: a print queue

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

Worked example: max-heap then min-heap

4. std::deque and std::list

Worked example: deque and list

5. std::pair and std::tuple

Worked example: pair, tuple & structured bindings

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

Worked example: a singly linked list from scratch

Pro Tips

Common Errors (and the fix)

📋 Quick Reference

Frequently Asked Questions

Mini-Challenge: Balanced Brackets

🎯 Mini-Challenge: are the brackets balanced?

🎉 Lesson Complete

Cookie & Privacy Settings

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

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

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

4. `std::deque` and `std::list`

5. `std::pair` and `std::tuple`