Introduction to Circular Queues

A circular queue is a linear data structure that follows the First In First Out (FIFO) principle but, unlike a regular queue, it connects the end of the queue back to the front, forming a circle. This allows for efficient utilization of space and avoids the problem of unused space in a regular queue.

Key Concepts

Circular Nature: The last position is connected back to the first position to make a circle.
Front and Rear Pointers: Two pointers are used to indicate the start and end of the queue.
Full and Empty Conditions: Special conditions to check if the queue is full or empty.

Circular Queue Operations

Basic Operations

Enqueue (Insertion): Add an element to the rear of the queue.
Dequeue (Deletion): Remove an element from the front of the queue.
Front: Get the front item from the queue.
Rear: Get the last item from the queue.
isEmpty: Check if the queue is empty.
isFull: Check if the queue is full.

Circular Queue Implementation

Below is a Python implementation of a circular queue using a list:

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

    def isFull(self):
        return (self.rear + 1) % self.size == self.front

    def isEmpty(self):
        return self.front == -1

    def enqueue(self, item):
        if self.isFull():
            print("Queue is full")
            return
        if self.front == -1:
            self.front = 0
        self.rear = (self.rear + 1) % self.size
        self.queue[self.rear] = item
        print(f"Enqueued {item}")

    def dequeue(self):
        if self.isEmpty():
            print("Queue is empty")
            return
        item = self.queue[self.front]
        if self.front == self.rear:
            self.front = self.rear = -1
        else:
            self.front = (self.front + 1) % self.size
        print(f"Dequeued {item}")
        return item

    def display(self):
        if self.isEmpty():
            print("Queue is empty")
            return
        if self.rear >= self.front:
            print("Queue:", end=" ")
            for i in range(self.front, self.rear + 1):
                print(self.queue[i], end=" ")
        else:
            print("Queue:", end=" ")
            for i in range(self.front, self.size):
                print(self.queue[i], end=" ")
            for i in range(0, self.rear + 1):
                print(self.queue[i], end=" ")
        print()

# Example usage
cq = CircularQueue(5)
cq.enqueue(10)
cq.enqueue(20)
cq.enqueue(30)
cq.enqueue(40)
cq.enqueue(50)
cq.display()
cq.dequeue()
cq.display()
cq.enqueue(60)
cq.display()

Explanation of Code

Initialization: The __init__ method initializes the queue with a given size and sets the front and rear pointers to -1.
isFull: Checks if the queue is full by comparing the next position of rear with the front.
isEmpty: Checks if the queue is empty by checking if the front is -1.
enqueue: Adds an item to the queue. If the queue is full, it prints a message. Otherwise, it updates the rear pointer and inserts the item.
dequeue: Removes an item from the queue. If the queue is empty, it prints a message. Otherwise, it updates the front pointer and returns the item.
display: Prints the elements of the queue in order.

Practical Exercises

Exercise 1: Implement Circular Queue

Task: Implement a circular queue with a size of 7 and perform the following operations:

Enqueue 5 elements.
Dequeue 2 elements.
Enqueue 3 more elements.
Display the queue.

Solution:

cq = CircularQueue(7)
cq.enqueue(1)
cq.enqueue(2)
cq.enqueue(3)
cq.enqueue(4)
cq.enqueue(5)
cq.display()
cq.dequeue()
cq.dequeue()
cq.display()
cq.enqueue(6)
cq.enqueue(7)
cq.enqueue(8)
cq.display()

Exercise 2: Check Full and Empty Conditions

Task: Write a function to check if the circular queue is full or empty after performing a series of enqueue and dequeue operations.

Solution:

def check_conditions():
    cq = CircularQueue(3)
    print("Is queue empty?", cq.isEmpty())  # True
    cq.enqueue(10)
    cq.enqueue(20)
    cq.enqueue(30)
    print("Is queue full?", cq.isFull())  # True
    cq.dequeue()
    print("Is queue full?", cq.isFull())  # False
    cq.enqueue(40)
    print("Is queue full?", cq.isFull())  # True
    cq.display()

check_conditions()

Common Mistakes and Tips

Overflow and Underflow: Always check for full and empty conditions before performing enqueue and dequeue operations to avoid overflow and underflow errors.
Pointer Updates: Ensure that the front and rear pointers are updated correctly to maintain the circular nature of the queue.
Initialization: Properly initialize the queue and pointers to avoid unexpected behavior.

Conclusion

In this section, we learned about circular queues, their operations, and how to implement them in Python. Circular queues are an efficient way to utilize space and are particularly useful in scenarios where the queue needs to be reused. The exercises provided practical experience in implementing and working with circular queues. In the next module, we will explore priority queues and their applications.

Circular Queues

Introduction to Circular Queues

Key Concepts

Circular Queue Operations

Basic Operations

Circular Queue Implementation

Explanation of Code

Practical Exercises

Exercise 1: Implement Circular Queue

Exercise 2: Check Full and Empty Conditions

Common Mistakes and Tips

Conclusion

Data Structures Course

Module 1: Introduction to Data Structures

Module 2: Lists

Module 3: Stacks

Module 4: Queues

Module 5: Trees

Module 6: Graphs

Module 7: Conclusions and Additional Resources