Computer Science
Queues
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.