Computer Science
Queues

queue image

A queue is a First In First Out (FIFO) data structure. New items are added to the end of the queue. Items are removed from the front of the queue. Pointers indicate the front and rear of the queue.

Linear Queue

Look carefully at the diagram of the queue above. If Job1 were to be removed from the queue and a new Job to be added, we would already have reached the maximum capacity for the queue shown above but still have a space left at the start. In a linear queue, all of the other jobs would have to shuffle one place to the left and then the space would be available at the end of the queue.

 '

 

This seems to be a rather fussy way of going about this. Moving the items takes a lot of processing time and would not be an efficient way of managing a busy queue.

Circular Queue

The circular queue operates in a similar way except it avoids the shuffling of items. When items are removed from the queue, all other items stay in the same location. Pointers are used to mark the front and rear of the queue. Try filling the queue and then removing a few items. Now add some more items to the queue and look carefully at the pointers.

 '

 

Circular Queue Algorithms

To Add To The Queue

If qlength>qmax Then
   Prompt User Queue Full
Else
   If qrear = 6 Then
      qrear = 1
   Else
      qrear = qrear + 1
   End If
   qitems[qrear] = item to add
   qlength = qlength + 1
End If

To Remove From The Queue

If qlength = 0 Then
   Prompt user Queue Empty
Else
   Take item from qitems[qfront]
   qlength = qlength - 1
   If qfront = 6 Then
      qfront =1
   Else
      qfront = qfront + 1
   End If
End If

Other Ways To Implement Queues

You can use a linked list, along with global variables to store start and end positions of the queue.

A priority queue stores the priority of each element. When we implement priority queues, it is the priority of the element, not when it is added that determines its position in the queue. A linked list can be used to represent this. The algorithms need to be tweaked to look at the priority of the item when adding or removing.