Back

Queues

How a queue works
Consider a supermarket. The first person to arrive at a checkout is first in the queue! Then a second person arrives and they are second in the queue. Then a third person arrives and they are third in the queue and so on. Of course, people are also leaving the queue as well. When someone leaves, they leave from the front of the queue. The first person into the queue is the first person out of the queue. This kind of data structure is known as a FIFO, or First In First Out structure.

If the first person in the queue leaves, then the front of the queue is now at the second person! You can find out where the front of the queue is by using a pointer to the front of the queue. You can also keep track of where the back of the queue is by using a pointer there, too.

An example of a queue
We will set up an array with 6 elements. Within this array, we will set up our queue. We will have a pointer called FRONT to point to the memory location where the front of the queue can be found, and a pointer called END, to point to the END of the queue. These will in fact simply be variables called FRONT and END. Note that the queue itself is a dynamic data structure because it grows and shrinks in size, but it is confined within an array - a static data structure, a fixed size! This may seem a contradiction because you are losing all the benefits of a dynamic structure by placing it within a static structure. However, it is the processing of the data itself in a queue that is most important so we will conveniently 'overlook' this anomaly for now! We will visualise the queue with the front of the queue at the bottom of the following diagrams. There is of course nothing stopping us having 1 row and 6 columns to show the queue. Different books will show a queue in different ways. We will see an example of this second method of visualising a queue in the section on stacks shortly. 

Step 1: The queue is empty. FRONT=0, END=0

Step 2: John joins the queue, then Zubair comes along and joins the queue. Finally, Mandy joins the queue. FRONT=1, END=3

Step 3: Sam joins the queue (at END+1 memory location) and John leaves the queue. FRONT=2, END=4

Step 4: Larry joins the queue and Zubair then Mandy leave the queue. FRONT=4, END=5

Step 5: Fred joins the queue. FRONT=4, END=6

When the END pointer points to the very end of the array, there appears to be a problem - how can we add another piece of data, Emma? There is free space in the array, just not at the end! Actually, it presents no problem! When the END pointer points to the end of the array AND the FRONT pointer isn't at the front of the array, it means there is space. We put the new data in to the front of the array, and adjust the END pointer accordingly. It doesn't matter that the END is in front of the FRONT pointer!

Step 6: Emma joins the queue. FRONT=4, END=1

Step 7: Sam leaves the queue and Ali joins the queue. FRONT=5, END=2

This kind of queue is known as a ‘circular queue’ because the FRONT and END pointers go around in circles! It ensures that free space made available at the front of the queue when a data item is removed can be re-used.

A classic application of a queue structure
A classic application of a queue structure is in the management of print jobs on a network. If 6 people on a network all send their work to be printed, their print jobs are intercepted in the order they are sent by a special program called a ‘spooler’. This program's function is to store each of the data in each print job in a queue. It then sends each job to the printer in a ‘First In First Out’ manner. (Using a spooler program ensures that a user can use their computer quickly after they have sent a file to be printed because the spooler is in charge of printing rather than the individual's computer).

Back