The next data structure we will consider is the queue. Queues are very similar to stacks in their simplicity, and support O(1) insertion, deletion and element access at one end. As you might expect they are structured exactly like a physical queue of people waiting in line. When somebody joins the queue, they join from the back, but when somebody leaves the queue, they leave from the front. Queues are therefore FIFO data structures; the First element In is the First element Out. This causes them to be similar to—but fundamentally different from—a stack. Both have single end push/pop operations, but in a stack all operations are performed on one end, whereas in a queue they are performed on a mixture of both.

These are then our requirements for a queue:

  • O(1) insertion at one end
  • O(1) deletion at the other end
  • O(1) element access at both ends
  • High space efficiency (ideally)

Can we use a singly-linked list for a queue? Well we can insert data in constant time at both the head and the tail, so point one is satisfied. We can remove data from the head very easily and we can—with some effort—do the same for the tail, so that satisfies point two. We can use the head as the front of the queue, and the tail as the back, and our singly-linked list implementation stored a tail pointer as well as a head pointer, so point three is satisfied too. For a pure singly-linked list with no tail pointer point three would not be satisfied, and instead we would have to use a doubly-linked list. We’ve got decent space efficiency using a singly-linked list, so we’re OK with point four. A linked list would certainly work then!

Could we use a vector this time? In fact we can’t, as vectors support O(1) insertion and deletion at one end, but not both. This means we’re stuck with either a doubly-linked list, or a singly-linked list with a tail pointer. The list implementation from a few tutorials back already supports a queue, so I won’t rewrite the code here. Instead just imagine that we have a queue class with push, pop, front, and back operations.

When exactly would you use a queue? Say we have an application that needs to perform a sequence of tasks, with new tasks added depending on certain conditions. What’s the best way to store the tasks? The logical solution would be to use a queue, as every time a new task is added we place it at the end of the queue, i.e. after the other tasks, and when the application is free to execute the next task it can look at the front of the queue and execute the task there. When that task is done, it can be popped off the front of the queue, and the next task can be run. These are the kinds of things queues are good for; when a sequence of data must be acted upon in the order it arrived.

STL provides a queue implementation, the queue class, which uses a list (or a deque) to store the queue. It’s usage is identical in format to every other STL container:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <queue>
#include <iostream>
#include <string>

int main(void)
{
    std::queue<std::string> people;
    people.push("Bob");
    people.push("James");
    people.push("Phoebe");
    people.push("Elizabeth");

    do
    {
        cout << "Next in line is " << people.front() << std::endl;
        people.pop();
    } while(!people.empty());

    return 0;
}