C Queues Explained - JohnHau/mis GitHub Wiki

Imagine you’re in line at a lemonade stand on a hot summer day, waiting to reach the front so you can enjoy a refreshing drink. Without having to think about it, you know that the first person to join the line will be the first person to leave it, and the last person to join will be the last to receive a drink.

The same concept exists in programming—in C++, this built-in data structure is called a queue. In this article, we’ll touch on what queues are and how to use them, and we’ll discuss some circumstances in which you might use and avoid queues.

Photo of administrator responsible for cyber security of large corporation searching for safety gaps debugging existant operating system to reduce hacker attacks success probability What is a queue in C++? A queue is a data structure that is optimized for a specific access pattern: the “first in, first out” (FIFO) pattern that describes lines as we know them in everyday life.

In addition to a garden-variety queue, C++ also has the concept of a priority queue, which you can think of as a structured or organized queue. The top element (largest, greatest, etc.) is always moved to the front of the queue, the bottom element is moved to the back, and each element in between has a priority in relation to all other elements. C++ has built-in queue and priority_queue data structures.

How to use a C++ queue The basic operations available to you when working with queues include creating a new queue, adding elements to it and retrieving elements. Let’s look at how this works with both a FIFO queue and a priority queue.

FIFO Queues First, let’s create a queue:

#include // std::cout #include // std::queue using namespace std;

int main () { queue my_queue; } This creates an empty queue, which we have illustratively named my_queue. Now, how can we add an element to this queue? Since we initialized our queue to contain integers, let’s add one using the push member function. Keep in mind that we need to do this using the same scope in which we declared our queue:

my_queue.push(7); Since our queue is empty, the integer 7 will be the only element. But say we push another element—where will it stand in the queue? The answer is that adding an element assigns it the last index, as the newest member of the queue.

As far as retrieving elements goes, the front and back functions will return references to those respective elements in the queue. Let’s push another integer into our queue so that the front and back functions will return different integers.

my_queue.push(3); my_queue.front(); // returns 7 my_queue.back(); // returns 3 It’s important to note that while we have operations that retrieve elements from the front and back, we don’t have a way to get an element from the middle of a queue. If we push another integer—say, 4—to our queue, we have no way of accessing 3, now in the middle of our queue.

Priority Queues Now that you’ve grasped the foundations of C++ queues, let’s look at the same operations in priority queues. Creating a priority queue (and then populating it with a for-loop) looks like this:

#include // std::cout #include // std::queue using namespace std;

int main () { priority_queue my_priority_queue;

for (int i = 5; i > 0; --i) my_priority_queue.push(i); // adds 5, 4, 3, 2, 1 } Priority queues have most of the same operations as queues have, with a few additions like top(). The top member function replaces the front member function used for FIFO queues. Note that there is no priority-queue equivalent to the back function.

Say we add this line right after our for-loop:

cout << my_priority_queue.top() << endl; What do you think this will print out? If you said 5, you are correct. What if we changed the order in which elements were pushed into the priority queue, so that the smallest elements are added first?

#include // std::cout #include // std::queue

int main () { priority_queue my_priority_queue;

for (int i = 0; i < 5; ++i) my_priority_queue.push(i + 1); // adds 1, 2, 3, 4, 5

cout << my_priority_queue.top() << endl; } If this were a FIFO queue, we would expect 1 to be the first item, since it was pushed first. However, the code prints out 5 when we call top(). As expected, our priority queue has ordered the elements for us.

To check if this is really how priority queues work, let’s now call pop(), a function (also available in FIFO queues) that removes the topmost element and returns its value. With a priority queue, we should see that the numbers returned by pop are ordered, so let’s try it and see:

priority_queue.pop(); // returns 5 priority_queue.pop(); // returns 4 priority_queue.pop(); // returns 3 priority_queue.pop(); // returns 2 priority_queue.pop(); // returns 1 And so we see that this priority queue really is ordered. Now that we have an understanding of both types of queues, let’s move on to some use cases for these data structures.

When to use queues in C++ Queues are great at keeping track of tasks to process and are the right choice if you need to track the order in which items need to be processed. If, for example, a movie studio has a number of scenes to render on its server farm, a queue will effectively keep track of which task came in first and handles it first. Perhaps you don’t need to keep track of the order elements are inserted, but you do need to order tasks according to a certain metric. In this case queues can still be a great fit—priority queues, that is. Back in our movie studio example, some projects will have a higher priority, and a priority queue will help those get taken care of first.

When to avoid using queues in C++ As previously noted, we can’t reference queue elements outside of the first and last ones, so if you’re looking for access to, say, the sixth element of a 12-element list, a queue is not the right data structure for you. You might find an array better suited to this purpose.

Underlying containers in C++ So far we have only touched on the first argument used in FIFO queues and priority queues. As you know, this first argument specifies the type of elements in the queue, but you can also specify an optional second argument. A priority queue is a container adapter, which changes the functionality of a given container type by imposing limitations on it. The optional second argument specifies the underlying container that actually stores the elements.
Let’s look at our previous example and add in a second argument:

priority_queue<int, vector > my_priority_queue Here, a vector is the underlying container—that is, the priority queue uses a vector container to store its values. It is worthwhile to note that the elements in the underlying container are accessed by the member functions of the container adapter (the priority queue), and not by those of the container (the vector) itself. Remember, the second argument is optional. If none is provided, a FIFO queue defaults to a deque as its container adapter, and a priority queue defaults to a vector. Other underlying container options include a list (for a FIFO queue) and a deque (for a priority queue).

Further reading and resources This is a comprehensive overview of member functions available to FIFO queues and priority queues. Here is a great overview of FIFO queues and another for priority queues.

Conclusion In this article, we covered what C++ FIFO queues and priority queues are, and we walked through the code for instantiating, adding to and retrieving from these data structures. We went over some ideal circumstances for using queues and talked about when other data structures might be more appropriate.