Implementing Circular Queue in Data Structures

Implementing Circular Queue in Data Structures

02 Jul 2024
Beginner
113 Views
10 min read
Learn via Video Course & by Doing Hands-on Labs

Data Structures & Algorithms Free Course

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.

What is Circular Queue

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:

When you want to add an element x to the queue

Implementing Queue Operations

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.

Dequeue()

Dequeue()

Implementing Circular Queue with an Array

Let's elaborate on circular queues with arrays inthe Python Compiler.

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

Circular Queues Applications

1. Operating Systems' Memory Management

In order to handle fixed-size data buffers efficiently, circular queues are utilized to manage memory in a circular buffer.

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 systemsTherefore, 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.

Similar Articles on Data Structures
Queue in Data Structures
Priority Queue in Data Structures
AVL Tree in Data Structures
Trees in Data Structures
Interview Preparation
DSA Interview Questions and Answers (Freshers to Experienced)

FAQs

Q1. What is circular stack in data structure?

A circular stack is a variation of the stack data structure in which the last element points to the first one, forming a loop or a 'circle.

Q2. What are the advantages of circular queues?

  • It provides a quick way to store FIFO data with a maximum size.
  • Efficient utilization of the memory.
  • Doesn't use dynamic memory.
  • Simple implementation.
  • All operations occur in O(1) constant time.

Q3. What is circular list in data structure?

The circular linked list is a linked list where all nodes are connected to form a circle. 
Share Article

Live Classes Schedule

Our learn-by-building-project method enables you to build practical/coding experience that sticks. 95% of our learners say they have confidence and remember more when they learn by building real world projects.
ASP.NET Core Project Jul 16 TUE, THU
Filling Fast
07:00AM to 08:30AM (IST)
Get Details
Azure Master Class Jul 20 SAT, SUN
Filling Fast
03:00PM to 05:00PM (IST)
Get Details
ASP.NET Core Certification Training Jul 28 SAT, SUN
Filling Fast
07:00AM to 09:00AM (IST)
Get Details
Software Architecture and Design Training Jul 28 SAT, SUN
Filling Fast
05:30PM to 07:30PM (IST)
Get Details
.NET Solution Architect Certification Training Jul 28 SAT, SUN
Filling Fast
05:30PM to 07:30PM (IST)
Get Details
Azure Developer Certification Training Jul 28 SAT, SUN
Filling Fast
10:00AM to 12:00PM (IST)
Get Details
Advanced Full-Stack .NET Developer Certification Training Jul 28 SAT, SUN
Filling Fast
07:00AM to 09:00AM (IST)
Get Details
Data Structures and Algorithms Training with C# Jul 28 SAT, SUN
Filling Fast
08:30PM to 10:30PM (IST)
Get Details
Angular Certification Course Aug 11 SAT, SUN
Filling Fast
09:30AM to 11:30AM (IST)
Get Details
ASP.NET Core Project Aug 24 SAT, SUN
Filling Fast
07:00AM to 09:00AM (IST)
Get Details

Can't find convenient schedule? Let us know

About Author
Shailendra Chauhan (Microsoft MVP, Founder & CEO at Scholarhat by DotNetTricks)

Shailendra Chauhan is the Founder and CEO at ScholarHat by DotNetTricks which is a brand when it comes to e-Learning. He provides training and consultation over an array of technologies like Cloud, .NET, Angular, React, Node, Microservices, Containers and Mobile Apps development. He has been awarded Microsoft MVP 8th time in a row (2016-2023). He has changed many lives with his writings and unique training programs. He has a number of most sought-after books to his name which has helped job aspirants in cracking tough interviews with ease.
Accept cookies & close this