How would you implement a circular queue?

A Circular Queue (also known as a Ring Buffer) is a linear data structure that follows the First In First Out (FIFO) principle. In a typical queue data structure, we cannot reuse the spaces once an element is removed. However, the circular queue modulates the end of the queue to the beginning, allowing continuous reusability of the queue.

Here’s a simple implementation of a circular queue in Python. Our queue consists of an array ’queue’ and two integers, ’front’ and ’rear’. The array holds the items in the queue, while ’front’ and ’rear’ represent indices of the starting and end points in the queue.

class CircularQueue:
    def __init__(self, k):
        self.k = k
        self.queue = [None] * k
        self.front = self.rear = -1

    # Insert an element at the rear
    def enQueue(self, data):
        if ((self.rear + 1) % self.k == self.front): 
            print("Circular Queue is fulln") 

        elif (self.front == -1):
            self.front = 0
            self.rear = 0
            self.queue[self.rear] = data
        else:
            self.rear = (self.rear + 1) % self.k 
            self.queue[self.rear] = data

    # Remove element from the front
    def deQueue(self):
        if (self.front == -1): 
            print("Circular Queue is emptyn")

        elif (self.front == self.rear):
            temp=self.queue[self.front]
            self.front = -1
            self.rear = -1
            return temp
        else:
            temp = self.queue[self.front]
            self.front = (self.front + 1) % self.k
            return temp

    # Display the queue
    def display(self):
        if(self.front == -1):
            print("No element in the Circular Queue")

        elif (self.rear >= self.front):
            for i in range(self.front, self.rear + 1):
                print(self.queue[i], end = " ")
        else:
            for i in range(self.front, self.k):
                print(self.queue[i], end = " ")
            for i in range(0, self.rear + 1):
                print(self.queue[i], end = " ")

In the ‘enQueue‘ operation, we check:

- If the queue is full ‘(self.rear + 1)

- If it’s empty, then the front and rear are at the same location.

- Otherwise, we move the rear to the next position ‘(self.rear + 1)

In the ‘deQueue‘ operation, we check:

- If the queue is empty ‘(self.front == -1)‘.

- If the front and rear are at the same location, then we make the queue empty after the ‘deQueue‘ operation.

- Otherwise, we move the front to the next position ‘(self.front + 1)

In the ‘display‘ operation, we handle the case when the rear has wrapped to an index before front. We display elements from front to the end of array and then from start to rear.