Skip to main content

Circular Queues

The above implementation of a queue has one significant disadvantage, in that it will become very slow if there are a large number of items in the queue. This is because every time the head of the queue is removed, all of the other data items in the queue will have to be moved down one. This can be solved by changing the way the queue is implemented. Instead of sliding all of the values along by one we can use a circular buffer to implement the queue. As a circular queue is a queue, just like the queue implemented above, the operations should be identical, so we do not need to consider that stage of the development process. Instead we can move straight to the implementation. Again we can help our visualisation with a diagram.

Initially both head and tail point to index 0. As we add a sequence of numbers to the queue, tail is incremented to reflect this. This is exactly the same as we have already seen. In this example we will add the four numbers 23, 87, 24 and 37 to the queue. This will result in a scenario like this:

Queue with 4 entries

Next: Removing Items from a Circular Queue