Implementing Circular Queue in Data Structures

Introduction to Circular Queue

Circular queues are also referred to as buffers or ring buffers. It is a type of data structure that forms a loop connecting the end of the queue, to the beginning. This design helps overcome the constraints of a queue by utilizing space, which proves beneficial, in situations where a fixed-size buffer is needed.

In this Data Structures Tutorial, We will go through an introduction toCircularQueues in Data Structures.

Explain Circular Queue

• The circular queue forms a circular link between the last node of a queue and its initial node,.
• It is essentially an expanded version of a linear queue that follows the First In First Out principle.
• As a result, it goes by the name Ring Buffer.
• The circular queue uses a circular link to overcome the memory-wasting issue, as seen in the below image.

Working of Circular Queue

While the Circular Queue and Linear Queue both follow the First In First Out (FIFO) rule, the Circular Queue is unique in that it replicates a circle by connecting the final position to the first position.

1. Front

• The Operation Front is where the circular queue's initial element is found.

2. Rear

• This is where the circular queue's final element is found.

3. Enqueue()

• To add a new value to the circular queue, use the enQueue(value) function.
• This process starts at the end of the line.

4.Dequeue()

• To remove a value from the circular queue, use the deQueue() function.
• This procedure is carried out at the front of the line.

Representation of Circular Queue

The representation of a Circular Queue can be done through Arrays and a Linked List

1. Array

In a queue based on arrays the front and rear pointers are increased using the modulo operation to loop to the beginning of the array;

• front = (front + 1) % size
• rear = (rear + 1) % size

2. Linked List

• When it comes to a circular queue using a linked list the nodes are linked in a way that the next pointer of the last node refers back, to the first node creating a circular structure.

Implementing Queue Operations

1. Enqueue(x)

To enter (enqueue) a data element into a circular queue, you should do the following:

• Step 1: First, determine whether the queue is full (Front + 1% Maxsize + Rear).
• Step 2: An Overflow error will appear if the queue is full.
• Step 3: Set Front and Rear to 0 and see if the line is empty.
• Step 4: If the rear pointer is at the end of the queue and the front is not at the 0th index, then set the rear = 0 if Rear = Maxsize - 1 & Front!= 0.
• Step 5: If not, set Rear to equal (Rear + 1)% Maxsize.
• Step 6: Place the element in the queue (Queue[Rear] = x) in step six.
• Step 7: Exit.

You will now investigate the Enqueue() function by examining several insertion scenarios in the circular queue:

2. Dequeue()

The actions listed below should be taken in order to remove data from a circular queue:

Implementing Circular Queue with an Array

class CircularQueue:
    def __init__(self, size):
        self.size = size
        self.queue = [None] * size
        self.front = self.rear = -1
    
    def is_full(self):
        return (self.rear + 1) % self.size == self.front
    
    def is_empty(self):
        return self.front == -1
    
    def enqueue(self, value):
        if self.is_full():
            print("Queue is full")
        else:
            if self.front == -1:
                self.front = 0
            self.rear = (self.rear + 1) % self.size
            self.queue[self.rear] = value
    
    def dequeue(self):
        if self.is_empty():
            print("Queue is empty")
        else:
            value = self.queue[self.front]
            if self.front == self.rear:
                self.front = self.rear = -1
            else:
                self.front = (self.front + 1) % self.size
            return value

Implementing a Circular Queue with a Linked List

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
class CircularQueue:
    def __init__(self):
        self.front = self.rear = None
    
    def is_empty(self):
        return self.front is None
    
    def enqueue(self, value):
        new_node = Node(value)
        if self.is_empty():
            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.is_empty():
            print("Queue is empty")
        else:
            value = self.front.data
            if self.front == self.rear:
                self.front = self.rear = None
            else:
                self.front = self.front.next
                self.rear.next = self.front
            return value

2. Algorithm of CPU Scheduling

3. Spooling Systems for Printers

4. Networking Traffic Management

Conclusion