Linear Queue

The simple linear queue can be implemented in code as a dynamic array that uses 2 pointers. One to mark the front of the queue (the head) and another to mark the next free slot.

When a data item leaves the queue (dequeue), the front pointer is simply redefined. The data is not actually removed from the queue.

When data is added to the queue (enqueue), it is placed at the end and the next free pointer is redefined.  These enqueue and dequeue operations can be summarised as follows:

Enqueue

• Add data item to position given by Next Free pointer
• Redefine NextFree pointer to end of queue

Dequeue

• Copy item from front of queue
• Redefine Front pointer to next item in queue

A Linear queue is easy to implement but it is constantly working its way through memory, it does not re-use memory. As a consequence if a large number of items are being added and removed from the queue, this means the queue will grow very large without ‘containing’ much data.

This is not a very efficient solution because it may use up large amounts of memory, it may even overwrite important data in memory.

Linear Queue Alternative

A linear queue can also be implemented in code using a static array. As before pointer variables are used to indicate the front and rear of the queue, plus an additional variable to indicate the number of items in the queue.

In this example, you can see what the queue looks like when two data items are dequeued then three more are enqueued. Of course the queue has no more space at the end now, so data items would have to be shuffled along to allow for more data. This means testing to see if the queue is full before new data is added, and testing to see if the rear of the queue is occupied before shuffling. The problem with a linear queue like this is that a lot of shuffling would be required for a busy queue.

Circular Queue

To get around the problem of having to shuffle the items in a queue along to make more space, it can be implemented as a circular queue.

When the last element of the array is occupied, simply add new data to the start of the array and define this as the rear of the queue.

It is worth noting that when items are removed from the queue, we simply need to redefine the front. The data need not actually removed from the array. It will be overwritten when the space it needed.