4.5.2 Basic Queues

Queues

A queue is an advanced data structure in C++. It is part of the standard library but does need to be included to use it.

#include <queue>

A queue stores a list of values like a vector or stack, however unlike vectors, you only have limited access to the items in the list. Think of a queue as a line that you may stand in. Anyone who joins the line joins at the back. The next person in line is then taken from the front. A queue in C++ does just this. You add new items to the back and take items off the front. This makes queues first-in, first-out.

Creating a Queue

Queues can be declared as an empty queue with a variable type, similar to how a new vector or stack is declared. Once declared, they are empty but ready to be added to.

queue<double> doubleQueue; // creates a new double queue
queue<string> strQueue; // creates a new string queue

Lick stacks, queues can also be declared and initialized with an existing data structure such as a vector.

vector<int> numVector {1,2,3,4};
queue<int> numQueue (numVector);

Basic Queue Operations

As mentioned above, queues store values but only give you limited access to items. Typically, you only access the front of the queue, but in C++, you can also access the back of the queue (although you can only remove the front).

Here is a list of commands available with queues.

Function	Operation
push	Inserts new element at the back of the queue.
front	Accesses the element at the front of the queue, but does not remove it.
pop	Removes the element at the front of the queue, but does not return it.
back	Accesses the element at the back of the queue, but does not remove it.
size	Returns the number of items in the queue.
empty	Returns a bool as true if the queue is empty.

Similar to stacks, you should notice that the front and pop commands are both needed to access and remove an element from the queue. Front will return the value and then you use pop to remove it.

Unlike stacks, queues do give you access to the last item in the list using the back command, however there is no way to remove that item.

Just like stacks, you will notice that there is a size and an empty function. While it is possible to use size == 0, this can be streamlined with the empty function.

Iterating through a Queue

As was the case with stacks, queues are not a data structure to use if you want to iterate through the entire list. Values in a queue cannot be accessed via an index value and you do not have access to any value in the middle of the queue.

Try This Example