Data Structures

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.

Learn Python, JavaScript, Java and more with free interactive lessons, real projects and AI-powered help. Beginner-friendly.

Part of the free C++ course at LearnCodingFast — hands-on lessons with examples you run in your browser, plus practice exercises and a quick quiz.

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.

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.

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.

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.

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:

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.

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.

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.

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.

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 .

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.

Practice quiz

Which discipline does a std::stack follow?

  • FIFO (First In, First Out)
  • Sorted order
  • LIFO (Last In, First Out)
  • Random access

Answer: LIFO (Last In, First Out). A stack is LIFO: the last item pushed is the first one popped, like a stack of plates.

Which methods does a std::queue use to read elements?

  • front() and back()
  • top() only
  • peek() and poll()
  • begin() and end()

Answer: front() and back(). A queue is FIFO: you read the next item with front() and the most recent with back(); a stack uses top().

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

  • It is a historical bug in the STL
  • pop() actually does return the value
  • Because the container is always empty after pop()
  • Returning-and-removing in one step could lose data if the copy threw, so reading and removing are separate

Answer: Returning-and-removing in one step could lose data if the copy threw, so reading and removing are separate. You read with top()/front() first, then call pop() (which returns void) to remove it.

By default, std::priority_queue<int> is a:

  • min-heap (smallest on top)
  • max-heap (largest on top)
  • FIFO queue
  • sorted vector

Answer: max-heap (largest on top). The default priority_queue is a max-heap, so top() always gives the largest element.

How do you make a min-heap with std::priority_queue?

  • priority_queue<int, vector<int>, greater<int>>
  • priority_queue<int, less<int>>
  • min_priority_queue<int>
  • priority_queue<int>(MIN)

Answer: priority_queue<int, vector<int>, greater<int>>. Supplying greater<int> as the comparator flips the default max-heap into a min-heap.

Which container lets you push and pop efficiently at BOTH ends AND index by position?

  • std::stack
  • std::queue
  • std::deque
  • std::list

Answer: std::deque. A deque (double-ended queue) supports push/pop at both ends and random access like dq[3].

Why can't you write list[3] on a std::list?

  • list indices start at 1, not 0
  • A list is a doubly linked list with no random access; you must walk it

Answer: A list is a doubly linked list with no random access; you must walk it. std::list stores nodes linked by pointers, so there is no index access; you walk it with an iterator or range-for.

What is the correct way to call top()/front()/pop() safely?

  • Wrap each access only in a try/catch
  • Always call pop() twice to be safe
  • Check size() == -1 before each call
  • Guard with !empty() first, because accessing an empty container is undefined behaviour

Answer: Guard with !empty() first, because accessing an empty container is undefined behaviour. Calling top/front/pop on an empty container is undefined behaviour, so always guard with !empty().

How do you read a value from std::tuple<string,int,double> record;?

  • record.second
  • get<1>(record)

Answer: get<1>(record). A tuple is read with get<index>(), e.g. get<1>(record); .first/.second is for pair.

In the hand-built linked list, how do you know you have reached the end of the chain?

  • The node's value is 0
  • The list throws an exception
  • The node's next pointer is nullptr
  • size() returns -1

Answer: The node's next pointer is nullptr. Each Node points to the next; the last node's next is nullptr, which marks the end.