← Back to Data Structures and Algorithms in Python

1. Introduction

A Circular Queue (also known as a Ring Buffer) is a linear data structure that follows the First In First Out (FIFO) principle. The difference between a standard queue and a circular queue is that in a circular queue, the last position is connected back to the first position to form a circle. This feature allows us to utilize memory more efficiently when the queue becomes full, and then some elements are dequeued.

2. Implementation Steps

1. Initialize an array of a fixed size and two pointers: front and rear.

2. Both pointers start at -1, indicating the queue is empty.

3. When adding an element (enqueue):

- Check if the queue is full.

- Update the rear pointer and add the element.

4. When removing an element (dequeue):

- Check if the queue is empty.

- Update the front pointer.

5. The queue is full when front is at 0 and rear is at the last index or when rear is one position behind the front.

6. The queue is empty when both front and rear are at -1.

3. Implementation in Python

class CircularQueue:
    def __init__(self, size):
        self.size = size
        self.queue = [None] * size
        self.front = self.rear = -1
    def enqueue(self, item):
        # Check if queue is full
        if ((self.rear + 1) % self.size == self.front):
            print("Queue is full!")
            return
        # Check if queue is empty
        elif self.front == -1:
            self.front = 0
            self.rear = 0
            self.queue[self.rear] = item
        else:
            self.rear = (self.rear + 1) % self.size
            self.queue[self.rear] = item
    def dequeue(self):
        # Check if queue is empty
        if self.front == -1:
            print("Queue is empty!")
            return
        # Check if queue has only one element
        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.size
            return temp
    def display(self):
        if self.front == -1:
            print("Queue is empty!")
            return
        i = self.front
        while True:
            print(self.queue[i], end=" ")
            if i == self.rear:
                break
            i = (i + 1) % self.size
        print()
# Example Usage
cq = CircularQueue(5)
cq.enqueue(1)
cq.enqueue(2)
cq.enqueue(3)
cq.enqueue(4)
cq.enqueue(5)
cq.display()
cq.enqueue(6)  # This should display "Queue is full!"
cq.dequeue()
cq.enqueue(6)
cq.display()

Output:

1 2 3 4 5
Queue is full!
2 3 4 5 6

Explanation:

1. A Circular Queue is initialized with a fixed size and two pointers, front and rear, both set to -1 to signify that the queue is empty.

2. When performing an enqueue operation, it checks if the queue is full by calculating the next position of rear and comparing it with front.

3. If the queue is not full, the rear pointer is updated (with wrapping) and the item is added.

4. When performing a dequeue operation, it checks if the queue is empty. If not, the item at the front is removed and the front pointer is updated.

5. The display method prints all the elements in the queue from front to rear.

6. In the example usage, elements from 1 to 5 are enqueued. Attempting to enqueue the 6th element shows "Queue is full!" because our circular queue's size is set to 5. After dequeuing an element, there's space to enqueue again, and then the queue is displayed.

The circular nature of this queue ensures that memory is efficiently used by overwriting previously dequeued positions, allowing for a more efficient utilization of a fixed-size buffer.