A [[std::vector]] is the right answer most of the time, but a [[std::stack]], [[std::queue]] or [[std::deque]] beats it when your access pattern is not "index from the front". The stack and the queue are *adaptors*: they are not containers of their own, but wrappers around a container that restrict what you can do with it. That restriction is the feature — it makes the intended use impossible to misuse.
stack is last in, first out
A std::stack is the adaptor for a LIFO structure. You push onto the top and pop from the top. Nothing else is allowed.
#include
#include
#include
int main() {
std::stack parcels;
parcels.push("p-001");
parcels.push("p-002");
parcels.push("p-003");
std::cout << "top: " << parcels.top() << '\n';
while (!parcels.empty()) {
std::cout << "processing " << parcels.top() << '\n';
parcels.pop();
}
return 0;
}The output shows the last parcel pushed coming out first:
top: p-003
processing p-003
processing p-002
processing p-001Notice what the adaptor does *not* let you do. There is no .operator[], no .begin() and no .erase(). You cannot reach into the middle of a stack, and that is the point.
queue is first in, first out
A std::queue is the adaptor for a FIFO structure. You push at the back and pop from the front.
#include
#include
#include
int main() {
std::queue parcels;
parcels.push("p-001");
parcels.push("p-002");
parcels.push("p-003");
while (!parcels.empty()) {
std::cout << "processing " << parcels.front() << '\n';
parcels.pop();
}
return 0;
}The output shows the first parcel pushed coming out first:
processing p-001
processing p-002
processing p-003A queue is the natural structure for work that must be handled in the order it arrived: print jobs, incoming requests, a breadth-first search.
deque is a double-ended queue
A std::deque is a real container rather than an adaptor, and it allows insertion and removal at both ends as well as random access in the middle.
#include
#include
#include
int main() {
std::deque parcels;
parcels.push_back("p-003");
parcels.push_front("p-001");
parcels.push_back("p-004");
parcels.push_front("p-000");
for (const std::string& parcel : parcels) {
std::cout << parcel << ' ';
}
std::cout << '\n';
std::cout << "front: " << parcels.front() << '\n';
std::cout << "back: " << parcels.back() << '\n';
return 0;
}The output shows the ends being used independently:
p-000 p-001 p-003 p-004
front: p-000
back: p-004A deque is the structure behind a sliding window, a work-stealing queue and a scheduler that may add work at either end.
Comparing the four
The table below is the practical summary.
| Operation | std::vector | std::deque | std::stack | std::queue | |---|---|---|---|---| | Push at the back | push_back | push_back | push | push | | Push at the front | slow | push_front | not available | not available | | Remove from the back | pop_back | pop_back | pop | not available | | Remove from the front | slow | pop_front | not available | pop | | Read the front | front | front | top | front | | Read the back | back | back | top | back | | Index with [i] | yes | yes | no | no |
When a vector is still the right choice
A vector is faster than a deque for most workloads, because its elements are contiguous in memory while a deque's are in blocks. If you do not actually need to add or remove at the front, use a vector.
The same applies to a stack and a queue. If your code only ever pushes and pops at one end, a std::vector with .back() and .pop_back() is simpler and faster. The adaptors earn their place when the discipline matters: when a reviewer wants to see that the code cannot reach into the middle of the collection.
The adaptors are built on other containers
A std::stack is a template over an underlying container, and by default that container is a std::deque. You can choose a different one.
#include
#include
#include
#include
int main() {
std::stack> parcels;
parcels.push(1);
parcels.push(2);
parcels.push(3);
std::cout << "top: " << parcels.top() << '\n';
std::cout << "size: " << parcels.size() << '\n';
// The underlying container is still reachable through the adaptor.
std::stack> copy = parcels;
std::cout << "copy size: " << copy.size() << '\n';
return 0;
}The output shows the stack working the same way with a vector underneath:
top: 3
size: 3
copy size: 3A worked example: a work queue
Here is a queue used for something real — processing parcel records in order while collecting the results.
#include
#include
#include
struct Parcel {
std::string id;
int weight;
};
int main() {
std::queue incoming;
incoming.push({"p-001", 4});
incoming.push({"p-002", 30});
incoming.push({"p-003", 12});
int total = 0;
int heaviest = 0;
while (!incoming.empty()) {
Parcel parcel = incoming.front();
incoming.pop();
std::cout << "processing " << parcel.id << '\n';
total += parcel.weight;
if (parcel.weight > heaviest) {
heaviest = parcel.weight;
}
}
std::cout << "total weight: " << total << '\n';
std::cout << "heaviest: " << heaviest << '\n';
return 0;
}The output shows the parcels being processed in the order they arrived:
processing p-001
processing p-002
processing p-003
total weight: 46
heaviest: 30Quick reference
std::stackis LIFO:push,top,pop.std::queueis FIFO:push,front,pop.std::dequeallows insertion and removal at both ends and random access.- The stack and the queue are adaptors that restrict the interface of an underlying container.
- A vector is faster than a deque for everything except front insertion and removal.
- Use a queue for work that must be handled in arrival order.
Try it yourself: push ten parcel records into a [[std::queue]] and process them, printing them as they come out. Then convert the queue to a [[std::stack]] and repeat, checking that the order reverses. Next, use a [[std::deque]] to add records at both ends and remove from the front, and compare the behaviour with the vector.