Implementation of Circular Queue in Python

October 14, 2023

Implementation of Circular Queue

Learn how to implement a Circular Queue in Python. A Circular Queue is a data structure that extends the functionality of a traditional queue by allowing elements to wrap around, creating a circular buffer.

In this page, we delve into the intricacies of circular queues, unraveling their characteristics, applications, implementation, and advantages over their linear counterparts.

Note Whether you're a seasoned programmer or just starting, this guide will provide you with a clear understanding of circular queues and their implementation.

Understanding Circular Queues

Circular queues, often referred to as ring buffers, present a dynamic data structure that fosters efficient data handling in scenarios demanding a fixed-size buffer. The cyclic nature of circular queues eliminates the wastage of memory space and enables seamless data circulation. To visualize this, consider a circle where the end points are connected, forming a loop. This loop structure embodies the essence of circular queues.

Implementing Circular Queues: A Step-By-Step Guide

Initialization

To create a circular queue, allocate memory for the queue and initialize front and rear pointers to -1, indicating an empty queue.

Enqueue Operation

When adding elements to the circular queue, follow these steps:

Check for queue overflow by comparing (rear + 1) % capacity with the front pointer. If they are equal, the queue is full.
Increment the rear pointer using (rear + 1) % capacity.
Store the new element in the position pointed to by the rear.

Dequeue Operation

Removing elements from the circular queue involves the following steps:

Check for queue underflow by comparing the front and rear pointers. If they are equal, the queue is empty.
Increment the front pointer using (front + 1) % capacity.
The element at the position pointed to by the front is now dequeued.

Coding Example: Circular Queue in Python

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

    def enqueue(self, item):
        if (self.rear + 1) % self.size == self.front:
            print("Queue is full")
        elif self.front == -1:
            self.front = self.rear = 0
            self.queue[self.rear] = item
        else:
            self.rear = (self.rear + 1) % self.size
            self.queue[self.rear] = item

    def dequeue(self):
        if self.front == -1:
            print("Queue is empty")
        elif self.front == self.rear:
            temp = self.queue[self.front]
            self.front = self.rear = -1
            return temp
        else:
            temp = self.queue[self.front]
            self.front = (self.front + 1) % self.size
            return temp

Limitations of Queues

How to Implement a Circular Queue?

A circular queue can be implemented using two data structures :

Array
Linked List

Implementation of Circular Queue using Array

Initialize the circular queue with a given capacity and create an array to hold queue elements.
Initialize front and rear pointers to -1.
To enqueue an item:
Check if the queue is full by comparing (rear + 1) % capacity with front.
If the queue is not full, check if it’s empty. If it is, set front and rear to 0 and add the item to the queue.
Otherwise, update rear to the next position and add the item.
To dequeue an item:
Check if the queue is empty by checking if front is -1.
If there’s only one element, set front and rear to -1.
Otherwise, set the element at front to None and update front to the next position.
To display the elements in the queue:
Check if the queue is empty.
If rear is greater than or equal to front, loop through the elements from front to rear and print them.
If not, loop through the elements from front to the end of the array and then from the start of the array to rear.

class CircularQueue:
    def __init__(self, capacity):
        # Initialize the circular queue with a given capacity
        self.capacity = capacity
        self.queue = [None] * capacity  # Create an array to hold queue elements
        self.front = self.rear = -1  # Initialize front and rear pointers

    def enqueue(self, item):
        # Check if the queue is full
        if (self.rear + 1) % self.capacity == self.front:
            print("Queue is full")
        # Check if the queue is empty
        elif self.front == -1:
            self.front = self.rear = 0
            self.queue[self.rear] = item
        else:
            self.rear = (self.rear + 1) % self.capacity
            self.queue[self.rear] = item

    def dequeue(self):
        # Check if the queue is empty
        if self.front == -1:
            print("Queue is empty")
        # Check if there's only one element in the queue
        elif self.front == self.rear:
            self.queue[self.front] = None
            self.front = self.rear = -1
        else:
            self.queue[self.front] = None
            self.front = (self.front + 1) % self.capacity

    def display(self):
        # Check if the queue is empty
        if self.front == -1:
            print("Queue is empty")
        # Display the elements in the queue
        elif self.rear >= self.front:
            for i in range(self.front, self.rear + 1):
                print(self.queue[i], end=" ")
            print()
        else:
            for i in range(self.front, self.capacity):
                print(self.queue[i], end=" ")
            for i in range(0, self.rear + 1):
                print(self.queue[i], end=" ")
            print()

# Example usage
if __name__ == "__main__":
    cq = CircularQueue(5)
    cq.enqueue(1)
    cq.enqueue(2)
    cq.enqueue(3)
    cq.display()  
    cq.dequeue()
    cq.display()

Implementation of Circular Queue using Linked List :

Define a Node class with a data attribute and a next reference to the next node.
Initialize the CircularQueue class with front and rear pointers set to None.
To enqueue an item:
Create a new node with the given data.
If the queue is empty, set both front and rear to the new node, and make rear point to front.
Otherwise, make the current rear node point to the new node, update rear to the new node, and make rear point to front.
To dequeue an item:
If the queue is empty, print an error message.
If there’s only one element, set both front and rear to None.
Otherwise, move front to the next node and update rear to point to the new front node.
To display the elements in the queue:
Traverse through the circular linked list starting from front and print the data of each node until you reach the front node again.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class CircularQueue:
    def __init__(self):
        self.front = None
        self.rear = None

    def enqueue(self, item):
        new_node = Node(item)
        if self.front is None:
            self.front = self.rear = new_node
            self.rear.next = self.front
        else:
            self.rear.next = new_node
            self.rear = new_node
            self.rear.next = self.front

    def dequeue(self):
        if self.front is None:
            print("Queue is empty")
        elif self.front == self.rear:
            self.front = self.rear = None
        else:
            self.front = self.front.next
            self.rear.next = self.front

    def display(self):
        if self.front is None:
            print("Queue is empty")
        else:
            current = self.front
            while True:
                print(current.data, end=" ")
                current = current.next
                if current == self.front:
                    break
            print()

# Example usage
if __name__ == "__main__":
    cq = CircularQueue()
    cq.enqueue(1)
    cq.enqueue(2)
    cq.enqueue(3)
    cq.display() 
    cq.dequeue()
    cq.display()

Benefits of Circular Queues

Circular queues bring forth a plethora of benefits that underscore their significance in the world of data structures:

Optimized Memory Utilization: Unlike traditional linear queues, circular queues ensure optimal usage of memory. They prevent fragmentation and efficiently manage space allocation.
Efficient Data Handling: Circular queues excel in scenarios where data needs to be cycled and overwritten in a systematic manner. They find applications in print spooling, task scheduling, and more.
Constant Time Complexity: Enqueue and dequeue operations in circular queues boast constant time complexity, making them a favorable choice for real-time systems.

Conclusion

In the intricate tapestry of data structures, circular queues emerge as a thread that weaves efficiency, optimized memory utilization, and constant time complexity. Our endeavor to elucidate the nuances of circular queues equips you with an unmatched grasp over this fundamental concept.

As we part ways, remember that circular queues stand not only as a cornerstone of data structures but also as a testament to the power of organized data manipulation. May your journey through the world of circular queues be enlightening and transformative.

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Unlock this article for Free,
by logging in

Implementation of Circular Queue in Python