Home  Back Topics CD Orders  INDEX 
Queues

A queue is a FIFO (First In First Out) data structure. The first item to be added is the first one to be removed. (Think of a queue at a supermarket checkout!)

The implementation of a queue involves two pointers:

  • Front - which points to the front of the queue (the item which has been in the queue longest).
  • Back - which points to the back of the queue (the item most recently added) The diagram shows a queue after two names have been added :
8  

Front Pointer = 1

Back Pointer = 2

 
7  
6  
5  
4  
3  
2 Harry
1 William

If 'Jonathan' and 'Hayley' are then added to the queue:

8  

Front Pointer = 1

Back Pointer = 4

 
7  
6  
5  
4 Hayley
3 Jonathan
2 Harry
1 William

Then a name is removed and 'Paul' is added....

8  

Front Pointer = 2

Back Pointer = 5

 
7  
6  
5 Paul
4 Hayley
3 Jonathan
2 Harry
1  

An example of a queue in a computer system would be the printer queue ie spooled documents waiting for output to a printer. The documents would be printed in the order in which they were spooled.

Another example : In a multi-access system jobs waiting for processing are placed in a queue.

 
 

Algorithms

If we have an array Queue[FP..BP] of records then...the algorithm for adding a new record NewRecord to the Queue is...

AddNew(NewRecord)

if BP < MaxRecords then
    increment BP
    Queue[BP] = NewRecord
else
    output('Queue is full')
endif.
    

 MaxRecords is the maximum size of the queue.

BP is the Back Pointer. A new record is placed at the back of the queue.

The algorithm for removing a record from the Queue is..

Remove;

If Queue is not empty then
    increment FP
else
    output('Queue is empty')
endif.

 FP is the Front Pointer. A record is always removed from the Front of the queue.

NB : There is no need to 'delete' a record when it is removed.

 

 

Circular Queues

Consider the following sequence...

8  

Front Pointer = 2

Back Pointer = 7

 
7 Jennifer
6 Chloe
5 Paul
4 Hayley
3 Jonathan
2 Harry
1  

'Mary' is added and one name is removed....

8 Mary

Front Pointer = 3

Back Pointer = 8

 
7 Jennifer
6 Chloe
5 Paul
4 Hayley
3 Jonathan
2  
1  

.....and the array is filled to the top.....

If 'Keith' is now added to the queue, the position becomes.....

8 Mary

Front Pointer = 3

Back Pointer = 1

 
7 Jennifer
6 Chloe
5 Paul
4 Hayley
3 Jonathan
2  
1 Keith

The queue uses a circular structure and always uses any empty cells.

If one more name is then added, the queue becomes 'full' and no more data can be added to it.