C++ Queues using 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.

Simulating a Real Queue

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.

Asynchronous Communication between Systems

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.

Decoupling Modules

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:

1#include <queue>
2
3int main() {
4  std::queue<int> Numbers;
5}
6

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:

1#include <queue>
2#include <vector>
3
4int main() {
5  std::vector<int> Source{1, 2, 3};
6  std::queue<int> Numbers{Source.begin(),
7                          Source.end()};
8}
9

We can also construct a queue by copying another queue:

1#include <queue>
2
3int main() {
4  std::queue<int> Numbers;
5  std::queue<int> Copy{Numbers};
6}
7

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

1#include <queue>
2
3int main() {
4  std::queue<int> Numbers;
5  std::queue Copy{Numbers};
6}
7

We can also construct a queue directly from a specific type of container, which we cover later in this lesson.

Adding Objects to the Back of the Queue

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:

1#include <queue>
2#include <string>
3
4class Character {
5 public:
6  Character(std::string Name) : Name{Name} {}
7  std::string Name;
8};
9
10int main() {
11  std::queue<Character> Q;
12  Q.emplace("Legolas");
13}
14

push

If our object already exists, we can use the queue’s push method to copy or move it into our container:

1#include <queue>
2#include <string>
3
4class Character {
5 public:
6  Character(std::string Name) : Name{Name} {}
7  std::string Name;
8};
9
10int main() {
11  Character Legolas{"Legolas"};
12  Character Gimli{"Gimli"};
13
14  std::queue<Character> Q;
15
16  // Copy
17  Q.push(Legolas);
18
19  // Move
20  Q.push(std::move(Gimli));
21}
22

We cover copy semantics, move semantics, and std::move in more detail here:

Copy Semantics, Elision, and RVO

Learn how to implement copy semantics in C++, and take advantage of copy elision and return value optimization (RVO)

Move Semantics, std::move and rvalues

Learn how to implement move semantics in C++, the difference between lvalues and rvalues, and what std::move really does.

back

We can retrieve a reference to the object at the end of our queue using the back method:

1#include <iostream>
2#include <queue>
3#include <string>
4
5class Character {
6 public:
7  Character(std::string Name) : Name{Name} {}
8  std::string Name;
9};
10
11int main() {
12  std::queue<Character> Q;
13  Q.emplace("Legolas");
14
15  std::cout
16      << "The last character in the queue is "
17      << Q.back().Name;
18} 
19

1The last character in the queue is Legolas
2

Removing Objects from the Front of the Queue

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.

1#include <iostream>
2#include <queue>
3#include <string>
4
5class Character {
6 public:
7  Character(std::string Name) : Name{Name} {}
8  std::string Name;
9};
10
11int main() {
12  std::queue<Character> Q;
13  Q.emplace("Legolas");
14  Q.emplace("Gimli");
15  Q.emplace("Gandalf");
16
17  std::cout << Q.front().Name
18            << " is at the front of the queue";
19}
20

1Legolas is at the front of the queue
2

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:

1#include <iostream>
2#include <queue>
3#include <string>
4
5class Character {
6 public:
7  Character(std::string Name) : Name{Name} {}
8  std::string Name;
9};
10
11int main() {
12  std::queue<Character> Q;
13  Q.emplace("Legolas");
14  Q.emplace("Gimli");
15  Q.emplace("Gandalf");
16
17  std::cout
18      << Q.front().Name
19      << " is at the front of the queue\n";
20
21  Q.pop();
22
23  std::cout << Q.front().Name
24            << " is now at the front";
25}
26

1Legolas is at the front of the queue
2Gimli is now at the front
3

Checking the Queue Size

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:

1#include <iostream>
2#include <queue>
3#include <string>
4
5class Character {
6 public:
7  Character(std::string Name) : Name{Name} {}
8  std::string Name;
9};
10
11int main() {
12  std::queue<Character> Q;
13  Q.emplace("Legolas");
14  Q.emplace("Gimli");
15  Q.emplace("Gandalf");
16
17  std::cout << Q.size()
18            << " objects are in the queue\n";
19
20  Q.pop();
21
22  std::cout << Q.size()
23            << " objects are now in the queue";
24}
25

empty

Where we want to compare the size() of the queue to 0, we can use the more explicit empty method:

1#include <iostream>
2#include <queue>
3#include <string>
4
5class Character {
6 public:
7  Character(std::string Name) : Name{Name} {}
8  std::string Name;
9};
10
11int main() {
12  std::queue<Character> Q;
13  Q.emplace("Legolas");
14
15  if (!Q.empty()) {
16    std::cout << "The queue is not empty\n";
17  }
18
19  Q.pop();
20
21  if (Q.empty()) {
22    std::cout << "Now it is";
23  }
24}
25

1The queue is not empty
2Now it is
3

Typical Queue Usage

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:

1#include <iostream>
2#include <queue>
3#include <string>
4
5class Character {
6 public:
7  Character(std::string Name) : Name{Name} {}
8  std::string Name;
9};
10
11int main() {
12  std::queue<Character> Q;
13  Q.emplace("Legolas");
14  Q.emplace("Gimli");
15  Q.emplace("Gandalf");
16
17  while (!Q.empty()) {
18    std::cout << Q.front().Name
19              << " has entered the game\n";
20    Q.pop();
21  }
22
23  std::cout << "The queue is empty!";
24}
25

1Legolas has entered the game
2Gimli has entered the game
3Gandalf has entered the game
4The queue is empty!
5

Using a different container with 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:

1#include <iostream>
2#include <list>
3#include <queue>
4#include <string>
5
6class Character {
7 public:
8  Character(std::string Name) : Name{Name} {}
9  std::string Name;
10};
11
12int main() {
13  std::queue<Character, std::list<Character>> Q;
14  Q.emplace("Legolas");
15  std::cout << Q.front().Name
16            << " is at the front of the queue";
17}
18

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 queue
• back() - 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 queue

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

Initializing a Queue from a Container

We can initialize a queue using a collection of the queue’s underlying type, such as std::list:

1#include <iostream>
2#include <list>
3#include <queue>
4#include <string>
5
6class Character {
7 public:
8  Character(const char* Name) : Name{Name} {}
9  std::string Name;
10};
11
12int main() {
13  std::list<Character> Characters{
14      "Legolas", "Gandalf", "Gimli"};
15
16  std::queue<Character, std::list<Character>> Q{
17      Characters};
18
19  std::cout << Q.front().Name
20            << " is at the front of the queue";
21}
22

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

1int main() {
2  std::list<Character> Characters{};
3  std::queue Q{Characters};
4}
5