circular queue

Circular Queue using Array (Wrapping Around)

To understand the concept of Circular Queue (Front and Rear arrows wrap around), consider the Queue Implementation Example and make the following changes.

First comment out the following lines in MyQueue class, Basically what you are doing is commenting out the logic for handling wrap around.

And modify your QueueExample class like the following

Circular Queue using Array

Whenever you insert a new item in the queue, the Front arrow moves upward towards the higher index of the array and whenever you remove an item from the queue, the Rear arrow also moves upward as shown in the following figure.

circular queue
QueueExample class is modified inline with the above operations. Try these operations with Queue Implementation example by commenting wrap around logic as mentioned above. The final code should look like the following

The problem with this code or approach is that the rear arrow of the queue has reached the end of the array (maximum index) at step iv. as shown in the figure above.

And when you try to insert another item in step v., even if there are empty cells at the beginning of the array you would see the following error

Wrap Around

To solve the above problem of not being able to insert an item even if the queue is not full, the front and rear arrows of the queue wrap around to the beginning of the array as shown in figure. This is called circular queue or ring buffer.

circular queue wrap around

Note that after the rear arrow is wrapped around, it is now below the front arrow i.e., the reverse of the original arrangement.

With wrap around logic when you run the above program you should be able to insert more items and see the following output

Recommended Posts

References

Leave a Reply

avatar
  Subscribe  
Notify of