Implementing Circular Queue in Data Structures (2024)

Introduction to Circular Queue

Circular queues arealso 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:

Step 1: First, make sure the queue is empty (Front = -1 and Rear = -1).

Step 2: Underflow error if the queue is empty

Step 3: Set Element = Queue[Front] in step three.

Step 4: Set both Front and Rear to -1 (IF Front = Rear, set Front = Rear = -1) if a queue has only one element.

Step 5: Set Front = 0 if Front = Maxsize -1.

Step 6: In the event that is not, set Front = Front + 1.

Step 7: Exit.

Let's examine the Dequeue() function diagrammatically.

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 = Noneclass 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

In this, circular queues are utilized to guarantee that each process receives an equal amount of CPU time.

3. Spooling Systems for Printers

Print jobs are managed via circular queues, which hold them in a queue and process them in the order that they come in.

4. Networking Traffic Management

In network routers, packets are managed using circular queues to guarantee effective and systematic packet transport.

Conclusion

A Circular queue is a data structure that maximizes space utilization and offers queue functions. It can be used across areas such, as operating systems, networking, and scheduling systems.Therefore, refer to it repeatedly until you get thorough with implementation, and an overview of Circular queues in data structures.Enroll in our Best Data Structures And Algorithms Course to test your knowledge.