C++ PROGRAMMING · 13 MIN STUDY

Stacks, queues, deques, and lists

Choose standard sequence containers and container adaptors for different access patterns.

Learning objectives

Choose a container based on required operations.
Use stack and queue container adaptors.
Understand deque and list at a high level.
Compare common operation costs.

Prerequisites: understand arrays, std::vector, loops, and basic template syntax. Review Arrays, Vectors, and Loops first.

Container choice follows the problem

The standard library provides several containers. They are not interchangeable: each has different access patterns, memory behavior, and operation costs. Prefer the simplest container that supports the operations your program needs.

Stack: last in, first out

#include <stack>\nstd::stack<int> history;
history.push(10);
history.push(20);
int latest = history.top(); // 20
history.pop();              // removes 20

A stack is a container adaptor with push, top, and pop. It follows LIFO: last in, first out. pop() removes the top element but does not return it.

Queue: first in, first out

#include <queue>\n#include <string>\nstd::queue<std::string> tasks;
tasks.push("compile");
tasks.push("test");
auto next = tasks.front(); // compile
tasks.pop();

A queue follows FIFO: first in, first out. It is useful for processing work in arrival order.

Deque and list

std::deque supports efficient insertion and removal at both ends and random-access indexing. std::list is a doubly linked list: insertion and removal at a known iterator are constant time, but finding an element by position requires traversal. A list usually uses more memory per element and has poorer cache locality than vector.

Priority queue

std::priority_queue exposes the highest-priority element according to its comparison rule. By default, it behaves like a max-heap, so top() gives the largest element. It is useful for scheduling and graph algorithms.

Complexity overview

Container	Strength	Trade-off
vector	Fast random access and cache locality	Insert/erase in middle shifts elements
deque	Efficient operations at both ends	Different storage layout from vector
list	Insert/erase at known iterator	No random access; extra link storage
stack	LIFO interface	Only top access
queue	FIFO interface	Only front/back access
priority_queue	Access highest-priority item	No arbitrary indexed access

Common mistakes

Calling top() or front() on an empty adaptor.
Expecting pop() to return the removed element.
Choosing list because insertion is described as O(1), without accounting for the cost of finding the insertion position.
Assuming priority_queue returns the smallest value by default.

Practice

Use a stack to reverse a short sequence.
Use a queue to simulate people waiting in a line.
Use a priority_queue to repeatedly process the largest number.
Explain why vector is often a better default than list.

Practice solutions

Show worked solutions

Push the sequence onto a std::stack, then repeatedly print top() and call pop(). A stack reverses the order because the last pushed element is removed first.
Push each person's name into a std::queue. Repeatedly read front() and call pop(); the first person added is served first.
Push all numbers into std::priority_queue<int>. Repeatedly read top() and call pop(); the largest remaining number is returned first.
vector is usually a better default because it stores elements contiguously, supports fast indexing, and is efficient to traverse. A list is useful when its iterator stability or splice operations are specifically needed; finding an insertion position in a list still takes time.

Check your understanding

What does stack::pop return?

Answer: Nothing. Read the value with top() before calling pop().

Summary

Choose containers based on access patterns: vector for general sequences, stack for LIFO, queue for FIFO, priority_queue for highest-priority access, deque for both-end operations, and list only when its iterator-based insertion/removal strengths matter.