Queues

A queue is a linear list with a first-in first-out structure.There are three different types of queue circular queues, linear queues and priority queues.

Types of Queue

Linear

A linear queue is where items are removed from the front of queue and items are added to the rear of the queue. As items are removed from the front of the queue the front of the queue will move further and further back.

If we simply add to the rear of the queue and remove from the front in a linear fashion we would eventually reach the maximum limit of the queue and have no more space to add items. Also, there will be wasted empty space at the front of the queue.

It is also impractical to move all the items up a place when an item is removed (as would happen in a shop queue). This would require each item in the queue to be moved every time an item was removed from the queue. This would require too much processing especially for large queue sizes.

Circular

Rather than move the data items, we move the front and rear pointers as data is added or removed. We still need to know when the queue is full or empty. The easiest method is to simply count the number of items in the queue.

Pointers are required to point to the front and rear of the queue. The rear pointer always points to the last item in the queue and the front pointer points to the next item to be removed from the front of the queue. Initially rear pointer would be set to 0 and front pointer to 1.

We have a limit to the size of the queue (ie queuemax). To make the queue circular when either pointer reaches queuemax it will next move to position 1.

The queue is full when Number of items = queuemax and the queue is empty when Number of items = 0. We can only add an item if the queue is not full and we can only remove an item if the queue is not empty.