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.