std::queue
std::queue
A queue is a data structure that replicates the properties of a real-life queue. They are ubiquitous in programming, with many use cases that we’ll cover soon.
The defining characteristic of a queue is that objects leave in the same order they were added.
Because of this, a queue is sometimes described as a first-in, first-out (FIFO)Â container.
We can visualize a queue as a sequential container, where objects are only added at the back of the queue, and only removed from the front. Adding an object to a queue is often referred to as pushing it, or enqueuing it. Removing an object from the front of a queue is referred to as popping it, or dequeuing it.
Queues are everywhere in programming. Their use cases broadly fall into three categories - simulation, asynchronous communication, and decoupling.
The most obvious use for a queue data structure is to simulate an actual, real-world queue. For example, if we’re making an online service, we may find ourselves having a surge of popularity that overloads our infrastructure. One way to prepare for this is to build a queue system, where users need to wait until we have enough capacity to let them in.
Sometimes, our systems communicating with each other through simple function calls can present issues. For example, imagine we’re running a popular video hosting site. Users can upload their videos, which we compress, and then release to the public.
Compressing videos can take a long time. We don’t want users waiting until that completes before we tell them their upload was successful. So, we can make these processes asynchronous, with the help of a queue. When users upload their video, rather than compressing it within the same call stack, we can simply add the video to a queue, and consider that part of the process complete. We can tell users their upload was successful.
Our compression system can run as a separate step, grabbing videos from the queue and compressing them without holding any other process back.
The third use of a queue is more concealed from users, as it’s a way to design our systems to make them more modular. When we’re building a complex project, like a large game, we will have dozens of systems.
All our systems need an organized way to communicate with each other. Having an event queue at the heart of our architecture, which our separate modules can write to and read from, is a common approach to take. Our course on making games using SDL relies heavily on this technique, and we have a dedicated lesson on the design pattern coming soon.
std::queue
The C++ standard library has an implementation of a queue ready for us to use. It’s available as part of the <queue>
header. It is a template class that requires us to specify the type of object our queue will contain. In this example, we create a queue of integers:
#include <queue>
int main() {
std::queue<int> Numbers;
}
The queue class does not have a constructor that lets us provide a list of initial values.
However, we can initialize a queue by passing an iterator pair denoting the start and end of a range of initial values. Note, this is a C++23 addition, so will not yet be supported by all compilers:
#include <queue>
#include <vector>
int main() {
std::vector<int> Source{1, 2, 3};
std::queue<int> Numbers{Source.begin(),
Source.end()};
}
We can also construct a queue by copying another queue:
#include <queue>
int main() {
std::queue<int> Numbers;
std::queue<int> Copy{Numbers};
}
When creating a queue from an iterator pair or from another queue, we can omit the template parameter. This will let the compiler infer it, using Class Template Argument Deduction (CTAD):
#include <queue>
int main() {
std::queue<int> Numbers;
std::queue Copy{Numbers};
}
We can also construct a queue directly from a specific type of container, which we cover later in this lesson.
Similar to most other sequential containers in the standard library, we have two ways to add objects to our queue.
emplace
The emplace
method will construct our object directly into the queue. If the object we want to add doesn’t already exist, this is the preferred method for performance reasons. Constructing an object in place tends to be faster than constructing it elsewhere, and then moving it into the container.
The emplace
method passes any arguments along to the constructor of the type stored in our queue:
#include <queue>
#include <string>
class Character {
public:
Character(std::string Name) : Name{Name} {}
std::string Name;
};
int main() {
std::queue<Character> Q;
Q.emplace("Legolas");
}
push
If our object already exists, we can use the queue’s push
method to copy or move it into our container:
#include <queue>
#include <string>
class Character {
public:
Character(std::string Name) : Name{Name} {}
std::string Name;
};
int main() {
Character Legolas{"Legolas"};
Character Gimli{"Gimli"};
std::queue<Character> Q;
// Copy
Q.push(Legolas);
// Move
Q.push(std::move(Gimli));
}
We cover copy semantics, move semantics, and std::move
in more detail here:
back
We can retrieve a reference to the object at the end of our queue using the back
 method:
#include <iostream>
#include <queue>
#include <string>
class Character {
public:
Character(std::string Name) : Name{Name} {}
std::string Name;
};
int main() {
std::queue<Character> Q;
Q.emplace("Legolas");
std::cout
<< "The last character in the queue is "
<< Q.back().Name;
}
The last character in the queue is Legolas
The two methods we use for working with the front of our queues are front
and pop
.
front
The queue’s front
method returns a reference to the object at the front of our queue. By definition of a queue, the object at the front is the object that has been in the queue the longest.
#include <iostream>
#include <queue>
#include <string>
class Character {
public:
Character(std::string Name) : Name{Name} {}
std::string Name;
};
int main() {
std::queue<Character> Q;
Q.emplace("Legolas");
Q.emplace("Gimli");
Q.emplace("Gandalf");
std::cout << Q.front().Name
<< " is at the front of the queue";
}
Legolas is at the front of the queue
pop
Accessing the first object in the queue with front
doesn’t automatically remove it from the queue. To remove the object from the front of the queue, we need to call pop
:
#include <iostream>
#include <queue>
#include <string>
class Character {
public:
Character(std::string Name) : Name{Name} {}
std::string Name;
};
int main() {
std::queue<Character> Q;
Q.emplace("Legolas");
Q.emplace("Gimli");
Q.emplace("Gandalf");
std::cout
<< Q.front().Name
<< " is at the front of the queue\n";
Q.pop();
std::cout << Q.front().Name
<< " is now at the front";
}
Legolas is at the front of the queue
Gimli is now at the front
The queue
class has two more useful methods:
size
The size method returns a size_type
integer, telling us how many objects are in the queue:
#include <iostream>
#include <queue>
#include <string>
class Character {
public:
Character(std::string Name) : Name{Name} {}
std::string Name;
};
int main() {
std::queue<Character> Q;
Q.emplace("Legolas");
Q.emplace("Gimli");
Q.emplace("Gandalf");
std::cout << Q.size()
<< " objects are in the queue\n";
Q.pop();
std::cout << Q.size()
<< " objects are now in the queue";
}
empty
Where we want to compare the size()
of the queue to 0
, we can use the more explicit empty
 method:
#include <iostream>
#include <queue>
#include <string>
class Character {
public:
Character(std::string Name) : Name{Name} {}
std::string Name;
};
int main() {
std::queue<Character> Q;
Q.emplace("Legolas");
if (!Q.empty()) {
std::cout << "The queue is not empty\n";
}
Q.pop();
if (Q.empty()) {
std::cout << "Now it is";
}
}
The queue is not empty
Now it is
The typical approach for consuming a queue uses a while
loop that continues whilst Queue.empty()
is false. Within the body of the loop, we access the front()
object, do what we need to do with it, and then pop()
it off.
It looks something like this:
#include <iostream>
#include <queue>
#include <string>
class Character {
public:
Character(std::string Name) : Name{Name} {}
std::string Name;
};
int main() {
std::queue<Character> Q;
Q.emplace("Legolas");
Q.emplace("Gimli");
Q.emplace("Gandalf");
while (!Q.empty()) {
std::cout << Q.front().Name
<< " has entered the game\n";
Q.pop();
}
std::cout << "The queue is empty!";
}
Legolas has entered the game
Gimli has entered the game
Gandalf has entered the game
The queue is empty!
std::queue
(Container Adaptors)The C++ std::queue is an example of a container adaptor. It does not implement the storage mechanism for our objects - rather, it defers that to some other container, and provides us with an abstraction that acts like a queue.
By default, the container underlying std::queue
is a std::deque
. We cover deques (double-ended queues) in a later lesson.
We can change the underlying container by passing it to the second argument when constructing our queue.
The default std::deque
is appropriate here, but we can use a different container class, including our own if preferred. In the following example, we use a doubly-linked list, std::list
 instead:
#include <iostream>
#include <list>
#include <queue>
#include <string>
class Character {
public:
Character(std::string Name) : Name{Name} {}
std::string Name;
};
int main() {
std::queue<Character, std::list<Character>> Q;
Q.emplace("Legolas");
std::cout << Q.front().Name
<< " is at the front of the queue";
}
For the std::queue
adaptor to be compatible with a container, the container needs to have the following methods:
push_back()
- adds an object to the back of the queueback()
- returns a reference to the object at the back of the queue (i.e., the most recently pushed object)front()
- returns a reference to the object at the front of the queue (i.e., the object that has been in the queue the longest)pop_front()
- removes the object at the front of the queueWhilst not enforced by the compiler, our container should naturally be performant at running those methods if we want our queue to be performant. Additionally, the underlying container should perhaps not consume an excessive amount of resources that are not required when the container is only being used in the context of a queue.
We can initialize a queue using a collection of the queue’s underlying type, such as std::list
:
#include <iostream>
#include <list>
#include <queue>
#include <string>
class Character {
public:
Character(const char* Name) : Name{Name} {}
std::string Name;
};
int main() {
std::list<Character> Characters{
"Legolas", "Gandalf", "Gimli"};
std::queue<Character, std::list<Character>> Q{
Characters};
std::cout << Q.front().Name
<< " is at the front of the queue";
}
When initializing a queue from a container, we can use Class Template Argument Deduction (CTAD) to omit the template parameters. This is because the compiler can examine the type of argument we’re passing to the constructor.
In this case, we’re passing a std::List<Character>
, so the compiler can infer our std::queue
will be containing Character
objects, and the underlying container type will be a std::list<Character>
:
int main() {
std::list<Character> Characters{};
std::queue Q{Characters};
}
Comprehensive course covering advanced concepts, and how to use them on large-scale projects.