How do you implement a circular queue using an array?

A circular queue can be implemented using an array by maintaining two pointers, front and rear, to track queue elements.

A circular queue, also known as a ring buffer, is a linear data structure that follows the First-In-First-Out (FIFO) principle. It is called a circular queue because the last element points to the first element making a circular link. To implement a circular queue using an array, you need to initialise an array of a certain size and two pointers, front and rear, both set to -1 initially.

The front pointer is used to remove elements from the queue, while the rear pointer is used to add elements to the queue. When an element is enqueued, the rear pointer is incremented and the element is placed in the array at the rear index. When an element is dequeued, the front pointer is incremented, and the element at the front index is removed.

However, the circular nature of the queue needs to be maintained. This is done by using the modulus operator. When incrementing the rear or front pointer, you take the modulus of the incremented value with the size of the array. This ensures that when the end of the array is reached, the pointer wraps around to the beginning of the array.

For example, if the size of the array is 5, and the rear pointer is at index 4 (the last index), when an element is enqueued, the rear pointer is incremented to 5, and then the modulus operation (5 mod 5) sets the rear pointer back to 0.

It's important to handle the case when the queue is full or empty. The queue is empty when front and rear are both -1. The queue is full when the next increment of rear, modulus the size of the array, equals front. In this case, no more elements can be added until some are removed.

In summary, implementing a circular queue using an array involves careful management of the front and rear pointers to maintain the circular nature of the queue, and handling the cases when the queue is full or empty.