Introduction to Queues and 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.

Use Cases

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 the "uploading" 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, and having an event queue is a common approach to take. We have a dedicated lesson on event queues, and how to implement them later in the course.

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}

Copying and Moving Queues

We can also construct a queue with initial values by copying or moving another queue:

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

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

Copy Semantics and Return Value Optimization

Learn how to control exactly how our objects get copied, and take advantage of copy elision and return value optimization (RVO)

Move Semantics

Learn how we can improve the performance of our types using move constructors, move assignment operators and std::move()

When initializing a std::queue with values, we can, we can omit the template parameter. This will let the compiler infer it, using Class Template Argument Deduction (CTAD). Below, the compiler will deduce both Copy and Move should have a type of std::queue<int>:

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

Constructing Queues from Other Containers

We can also construct a queue directly from certain types of containers, such as a std::list:

1#include <queue>
2#include <list>
3
4int main() {
5  std::list Nums{1, 2, 3};
6  std::queue NumsQueue{Nums};
7}

There is a little more nuance here on what type of containers we can use, and the implications on our queue. We cover this later in the lesson, in the section on container adapters.

Constructing Queues from Iterators

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.

We introduced iterators in a dedicated lesson earlier in the course:

Iterators

This lesson provides an in-depth look at iterators in C++, covering different types like forward, bidirectional, and random access iterators, and their practical uses.

Note, the iterator-based constructor for std::queue 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{
7    Source.begin(), Source.end()};
8}

Again, we can use class template argument deduction:

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

Adding (Pushing) Objects

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}

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
Character Class|Show
4class Character {/*...*/}
10
11int main() {
12  Character Legolas{"Legolas"};
13  Character Gimli{"Gimli"};
14
15  std::queue<Character> Q;
16
17  // Copy
18  Q.push(Legolas);
19
20  // Move
21  Q.push(std::move(Gimli));
22}

Accessing Queue Elements

Queues only provide easy access to two of their objects - the object at the front of the queue, and the object at the back.

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
Character Class|Show
5class Character {/*...*/}
11
12int main() {
13  std::queue<Character> Q;
14  Q.emplace("Legolas");
15  Q.emplace("Gimli");
16  Q.emplace("Gandalf");
17
18  std::cout << Q.front().Name
19            << " is at the front of the queue";
20}

1Legolas is at the front of the queue

back()

We can retrieve a reference to the object at the end of our queue using the back method. By definition of a queue, the back of the queue is the object that was most recently added:

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

1The last character in the queue is Legolas

We can’t access other arbitrary elements of the queue. By design, queues are more restrictive than more general containers like std::vector.

Removing (Popping) Objects

To preserve the first-in-first-out rule of queues, we can only remove objects from the front of the queue. We do this using the pop() method:

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

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

Checking the Queue Size

The queue class has two methods to determine how many elements it contains:

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
Character Class|Show
5class Character {/*...*/}
11
12int main() {
13  std::queue<Character> Q;
14  Q.emplace("Legolas");
15  Q.emplace("Gimli");
16  Q.emplace("Gandalf");
17
18  std::cout << Q.size()
19            << " objects are in the queue\n";
20
21  Q.pop();
22
23  std::cout << Q.size()
24            << " objects are now in the queue";
25}

13 objects are in the queue
22 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:

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

1The queue is not empty
2Now it is

Practical Queue Example

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
Character Class|Show
5class Character {/*...*/}
11
12int main() {
13  std::queue<Character> Q;
14  Q.emplace("Legolas");
15  Q.emplace("Gimli");
16  Q.emplace("Gandalf");
17
18  while (!Q.empty()) {
19    std::cout << Q.front().Name
20              << " has entered the game\n";
21    Q.pop();
22  }
23
24  std::cout << "The queue is empty!";
25}

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

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
Character Class|Show
6class Character {/*...*/}
12
13int main() {
14  std::queue<Character, std::list<Character>> Q;
15  Q.emplace("Legolas");
16  std::cout << Q.front().Name
17            << " is at the front of the queue";
18}

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

• front() - returns a reference to the object at the start of the container
• back() - returns a reference to the object at the end of the container
• push_back() - adds an object to the end of the container. Called by the push() method of std::queue.
• emplace_back() - constructs an object in the end of the container. Called by the emplace() method of std::queue
• pop_front() - removes the object at the start of the container. Called by the pop() method of std::queue

Whilst not enforced by the compiler, our container should naturally be efficient at running those methods if we want our queue to be performant.

Additionally, the underlying container should 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. For example, if our queue is using a std::list as the underlying container, we can initialize our queue by copying that std::list:

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

Class Template Argument Deduction

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, so we’ll construct a std::queue<Character, std::list>:

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

Moving the Container

If we don’t need to copy our original container to create the queue, we can instead move it using std::move:

1#include <iostream>
2#include <list>
3#include <queue>
4
5int main() {
6  std::list Nums{1, 2, 3};
7
8  std::queue Q{std::move(Nums)};
9
10  std::cout << Q.front()
11            << " is at the front of the queue";
12}

Summary

In this lesson, we covered the queue data structure, and specifically the standard library’s implementation: std::queue. The key takeaways are:

• Queues are FIFO data structures with various applications in programming.
• The std::queue class template provides a convenient way to create and use queues in C++.
• Objects are added to the back of the queue using emplace() or push() and removed from the front using pop().
• The front() and back() methods allow accessing the elements at the front and back of the queue.
• std::queue is a container adaptor that can use different underlying containers, such as std::deque or std::list.

Next Lesson

Priority Queues using std::priority_queue

Master priority queues with a complete guide, starting from the basics, using the standard library’s priority_queue.

ContinueView Course