Python: Circular Queue Implementation

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 unique aspect of a circular queue is that the last position is connected to the first position, forming a circle. This characteristic ensures efficient use of memory as it can reuse freed positions.

2. Program Overview

In this Python program, we will:

1. Define a CircularQueue class with functions to enqueue, and dequeue, check if the queue is full or empty, and display the queue.

2. Implement overflow and underflow checks for our queue operations.

3. Code Program

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

        # If queue is empty
        if self.front == -1:
            self.front = 0

        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

        # If this is the last element
        if self.front == self.rear:
            temp = self.queue[self.front]
            self.front = -1
            self.rear = -1
            return temp

        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()

# Sample Usage
cq = CircularQueue(5)
cq.enqueue(10)
cq.enqueue(20)
cq.enqueue(30)
cq.enqueue(40)
cq.enqueue(50)
print("Queue after enqueues:")
cq.display()
cq.dequeue()
cq.dequeue()
print("Queue after dequeues:")
cq.display()
cq.enqueue(60)
cq.enqueue(70)
print("Queue after more enqueues:")
cq.display()

Output:

Queue after enqueues:
10 20 30 40 50
Queue after dequeues:
30 40 50
Queue after more enqueues:
30 40 50 60 70

4. Step By Step Explanation

1. The CircularQueue class initializes an empty queue with a given size.

2. The enqueue method adds an item to the rear of the queue, with checks for overflow.

3. The dequeue method removes an item from the front of the queue, with checks for underflow.

4. The display method prints the items of the queue from front to rear.

5. In the sample usage, we initialize a queue of size 5. We then enqueue five elements, display the queue, dequeue two elements, display the queue again, and finally enqueue two more elements and display the queue one last time. The output showcases the circular nature of the queue, where after reaching the end, the queue starts utilizing the space at the beginning.