# Computer ScienceQueues

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.