Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Operations on Circular Queue
3.
Illustration of Circular Queue Operations
4.
How to Implement a Circular Queue
4.1.
Enqueue (Add Element)
4.2.
Dequeue (Remove Element)
4.3.
Example Code
4.4.
Python
5.
Implement Circular Queue Using Array
5.1.
Steps to Implement Circular Queue Using Array
5.1.1.
Initialization
5.1.2.
Enqueue Operation (Add Element)
5.1.3.
Dequeue Operation (Remove Element)
5.1.4.
Peek Operation
5.2.
Example : 
5.3.
Python
5.4.
C++
5.5.
Java
5.6.
C
6.
Complexity Analysis of Circular Queue Operations
6.1.
Time Complexity
6.2.
Space Complexity
7.
Applications of Circular Queue
7.1.
Computer Systems
7.2.
Networking
7.3.
Application Level
7.4.
Consumer Devices
8.
Frequently Asked Questions
8.1.
What makes a circular queue different from a normal queue?
8.2.
Can a circular queue become full if there is an empty space at the beginning?
8.3.
How do you check if a circular queue is empty or full?
9.
Conclusion
Last Updated: May 4, 2024
Easy

What is a Circular Queue

Author Sinki Kumari
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

A circular queue is a linear data structure that follows a particular order in which operations are performed. Unlike standard queues, where the first element inserted is the first to be removed (FIFO—first in, first out), a circular queue connects the end of the queue back to its starting point, forming a circle. This setup is especially useful in situations where repetitive tasks need managing, as it allows for continuous data management without needing to reset storage pointers. 

What is a Circular Queue

In this article, we'll learn everything about circular queues, their operations, and applications and we will learn how they optimize various computer science processes.

Operations on Circular Queue

A circular queue lets you perform several basic actions that help manage data efficiently. These actions are:

  1. Enqueue: This is the term used for adding an item to the queue. In a circular queue, if there is space, the item is placed at the position marked by the 'rear' pointer. After adding the item, the rear pointer moves to the next position, circling back to the beginning if it reaches the queue's end.
     
  2. Dequeue: This operation involves removing an item from the front of the queue. The item where the 'front' pointer is located gets removed. Then, the front pointer shifts to the next item in line, also circling back if it reaches the queue’s end.
     
  3. Peek: This operation allows you to look at the first item in the queue without removing it. It's useful when you just want to check what's at the front of the line.
     
  4. IsEmpty: This checks if the queue is empty. If the front and rear pointers are at the same position and no enqueue operation has occurred, it means the queue is empty.
     
  5. IsFull: This checks if the queue is full. In a circular queue, this happens if the next position of the rear pointer is the front pointer, indicating there is no more space to add items.


Each of these operations helps in managing the data in a way that is efficient, especially when the data needs to be accessed or removed in a specific order. The ability to loop back to the beginning automatically after reaching the end of the queue makes circular queues particularly useful for repeated task cycles, like managing processes in a computer's CPU or distributing resources in networking.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Illustration of Circular Queue Operations

To better understand how a circular queue works, let's visualize its operations through a simple example. Imagine a circular queue that can hold up to five elements.

Initial State: Assume the queue is empty. The front and rear pointers are at position -1, indicating an empty state.

 

Enqueue 5, 3, and 9:

Enqueue 5, 3, and 9:
  • Add 5: Rear moves to 0, Front is at 0, Queue now is [5].
     
  • Add 3: Rear moves to 1, Queue now is [5, 3].
     
  • Add 9: Rear moves to 2, Queue now is [5, 3, 9].

Dequeue:

  • Remove 5: Front moves to 1, leaving Queue as [3, 9]. The position where 5 was gets cleared.

Enqueue 7 and 2:

  • Add 7: Rear moves to 3, Queue becomes [3, 9, 7].
     
  • Add 2: Rear moves to 4, Queue becomes [3, 9, 7, 2].

Circular Behavior:

  • If we add another element, say 4, and the queue is full, the rear will need to wrap around to the start if there is a space due to prior dequeues.

Dequeue Twice:

  • Remove 3: Front moves to 2, Queue shows [9, 7, 2].
     
  • Remove 9: Front moves to 3, Queue shows [7, 2].

Enqueue 6:

  • Since there’s a wrap-around, Rear goes back to 0 (the initial position), Queue finally looks like [6, 7, 2].
     

This example shows how the circular queue handles overflow by utilizing empty spaces left from dequeued elements, effectively maintaining its fixed size. It demonstrates the efficient use of space, as no position is wasted once it becomes available again. The front and rear pointers simply loop around the queue structure, ensuring seamless and continuous operations.

How to Implement a Circular Queue

Implementing a circular queue involves setting up a data structure with operations to add and remove elements efficiently. Here, we will discuss how to implement a circular queue : 

Setting Up: First, you need an array to hold the queue's elements and two pointers, front and rear, initially set to -1 to indicate the queue is empty.

Enqueue (Add Element)

  • Check if Full: Before adding an element, check if the queue is full. If rear + 1 is equal to front, the queue is full.
     
  • Initial Add: If the queue is empty (front and rear are -1), set both front and rear to 0.
     
  • Wrap Around: If adding an element would exceed the array's limit, wrap the rear pointer to 0 (circular motion).
     
  • Add the Element: Place the new element at the position indicated by rear and move the rear pointer one position forward.

Dequeue (Remove Element)

  • Check if Empty: Before removing an element, check if the queue is empty (front is -1).
     
  • Remove Element: Take out the element at front and, if only one element was left, reset front and rear to -1.
     
  • Move Front: If more elements are left, move the front pointer forward, wrapping around to 0 if it goes past the last array index.
     
  • Peek (Get Element at Front without Removing):
     
  • Check if Empty: Ensure the queue isn't empty.
     
  • Return Element: Return the element at the front position.

Example Code

  • Python

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
print(f"Inserted {item}")

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

def display(self):
if self.front == -1:
print("Queue is empty")
elif self.rear >= self.front:
print("Elements in the circular queue are:", end=" ")
for i in range(self.front, self.rear + 1):
print(self.queue[i], end=" ")
print()
else:
print("Elements in the circular queue are:", 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()

def peek(self):
if self.front == -1:
print("Queue is empty")
else:
return self.queue[self.front]

# Create a circular queue of size 5
cq = CircularQueue(5)
cq.enqueue(1)
cq.enqueue(2)
cq.enqueue(3)
cq.dequeue()
cq.enqueue(4)
cq.display()

Output

Inserted 1
Inserted 2
Inserted 3
Removed 1
Inserted 4
Elements in the circular queue are: 2 3 4 

Implement Circular Queue Using Array

This approach ensures efficient space utilization and provides constant time operations, like enqueue and dequeue.

Steps to Implement Circular Queue Using Array

Initialization

  • Start with an array of a fixed size. This size will determine the maximum number of elements the queue can hold.
     
  • Initialize two pointers, front and rear, to -1 to indicate that the queue is empty.

Enqueue Operation (Add Element)

  • Check Full Condition: First, check if the queue is full by seeing if (rear + 1) % array_size == front. If true, the queue is full, and no more elements can be added.
     
  • Add First Element: If the queue is empty (front == -1), set both front and rear to 0 and insert the element at rear.
     
  • Add Subsequent Elements: If not full, increment the rear pointer by one position circularly using the modulus operation (rear = (rear + 1) % array_size) and insert the new element at the rear position.

Dequeue Operation (Remove Element)

  • Check Empty Condition: Before removing, check if the queue is empty by checking if front == -1. If true, the queue is empty, and there's nothing to remove.
     
  • Remove Element: Remove the element at the front position.
     
  • Single Element Condition: If the queue becomes empty after the dequeue operation (front == rear), reset both front and rear to -1.
     
  • Adjust Front Pointer: Otherwise, increment the front pointer circularly (front = (front + 1) % array_size).

Peek Operation

Simply return the element at the front index without modifying the queue.

Example : 

  • Python
  • C++
  • Java
  • C

Python

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

def is_full(self):
return (self.rear + 1) % self.capacity == self.front

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

def enqueue(self, value):
if self.is_full():
print("Queue is full")
return
if self.is_empty():
self.front = 0
self.rear = (self.rear + 1) % self.capacity
self.queue[self.rear] = value
print(f"Enqueued: {value}")

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

def peek(self):
if self.is_empty():
print("Queue is empty")
return
return self.queue[self.front]
# Create a circular queue of size 5
cq = CircularQueue(5)
cq.enqueue(10)
cq.enqueue(20)
cq.enqueue(30)
cq.dequeue()
cq.enqueue(40)
cq.display()

C++

#include <iostream>
using namespace std;

class CircularQueue {
private:
int front, rear, size;
int *queue;
public:
CircularQueue(int sz) {
front = rear = -1;
size = sz;
queue = new int[sz];
}

void enqueue(int value) {
if ((rear + 1) % size == front) {
cout << "Queue is full" << endl;
return;
}
if (front == -1)
front = 0;
rear = (rear + 1) % size;
queue[rear] = value;
cout << "Enqueued: " << value << endl;
}

int dequeue() {
if (front == -1) {
cout << "Queue is empty" << endl;
return -1;
}
int data = queue[front];
if (front == rear)
front = rear = -1;
else
front = (front + 1) % size;
cout << "Dequeued: " << data << endl;
return data;
}

void display() {
if (front == -1) {
cout << "Queue is empty" << endl;
return;
}
cout << "Queue elements are: ";
int i;
for (i = front; i != rear; i = (i + 1) % size)
cout << queue[i] << " ";
cout << queue[i] << endl;
}
};

int main() {
CircularQueue q(5);
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
q.dequeue();
q.enqueue(40);
q.display();
return 0;
}

Java

public class CircularQueue {
private int[] queue;
private int front, rear, size;

public CircularQueue(int size) {
this.size = size;
queue = new int[size];
front = rear = -1;
}

public void enqueue(int value) {
if ((rear + 1) % size == front) {
System.out.println("Queue is full");
return;
}
if (front == -1)
front = 0;
rear = (rear + 1) % size;
queue[rear] = value;
System.out.println("Enqueued: " + value);
}

public int dequeue() {
if (front == -1) {
System.out.println("Queue is empty");
return -1;
}
int data = queue[front];
if (front == rear)
front = rear = -1;
else
front = (front + 1) % size;
System.out.println("Dequeued: " + data);
return data;
}

public void display() {
if (front == -1) {
System.out.println("Queue is empty");
return;
}
System.out.print("Queue elements: ");
for (int i = front; i != rear; i = (i + 1) % size)
System.out.print(queue[i] + " ");
System.out.println(queue[rear]);
}

public static void main(String[] args) {
CircularQueue q = new CircularQueue(5);
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
q.dequeue();
q.enqueue(40);
q.display();
}
}

C

#include <stdio.h>
#include <stdlib.h>

#define SIZE 5

int queue[SIZE], front = -1, rear = -1;

void enqueue(int value) {
if ((rear + 1) % SIZE == front) {
printf("Queue is full\n");
return;
}
if (front == -1)
front = 0;
rear = (rear + 1) % SIZE;
queue[rear] = value;
printf("Enqueued: %d\n", value);
}

int dequeue() {
if (front == -1) {
printf("Queue is empty\n");
return -1;
}
int data = queue[front];
if (front == rear)
front = rear = -1;
else
front = (front + 1) % SIZE;
printf("Dequeued: %d\n", data);
return data;
}

void display() {
if (front == -1) {
printf("Queue is empty\n");
return;
}
printf("Queue elements: ");
for (int i = front; i != rear; i = (i + 1) % SIZE)
printf("%d ", queue[i]);
printf("%d\n", queue[rear]);
}

int main() {
enqueue(10);
enqueue(20);
enqueue(30);
dequeue();
enqueue(40);
display();
return 0;
}

Output

Enqueued: 10
Enqueued: 20
Enqueued: 30
Dequeued: 10
Enqueued: 40
Queue elements: 20 30 40

Complexity Analysis of Circular Queue Operations

Complexity tells us about the time it takes to complete a task, like adding or removing an item in the queue, as the number of items grows.

Time Complexity

  • Enqueue (Adding an Element): This operation takes a fixed amount of time, regardless of how many elements are in the queue. We call this constant time, or O(1), because it doesn't change with the size of the queue.
     
  • Dequeue (Removing an Element): Just like enqueue, dequeue also operates in constant time, O(1). Removing an element always involves updating a couple of pointers, which takes the same amount of time no matter how full the queue is.
     
  • Peek (Viewing the Front Element): Looking at the front element is also a constant time operation, O(1), because it directly accesses the element at the front pointer without any extra work.

Space Complexity

The space complexity of a circular queue is O(n), where n is the capacity of the queue. This means the amount of memory needed depends on the maximum number of items the queue can hold. The space needed does not increase as you add or remove elements; it stays the same, defined by the maximum capacity set when the queue is created.
 

These complexities show that circular queues are very efficient for tasks where items are continuously added and removed. The operations are fast because they only require updating pointers and don't involve moving all other elements around. This makes circular queues a great choice in scenarios where performance matters, like in system buffers, resource management, or handling real-time data.

Applications of Circular Queue

Here are some of the main applications where circular queues make a big difference:

Computer Systems

  • CPU Scheduling: Circular queues are often used in managing processes within operating systems. They help organize the tasks waiting for CPU time, ensuring each process gets a turn and managing them efficiently as they rotate through their cycles.
     
  • Memory Management: Buffers, areas where data is temporarily stored while being transferred from one place to another, often use circular queues. This helps in continuously managing data flow, especially in streaming or real-time data processing.

Networking

  • Traffic Management: In network routers and switches, circular queues help manage packets of data waiting to be sent across the network, ensuring smooth data flow and reducing congestion or packet loss.
     
  • Resource Allocation: Managing limited resources like bandwidth or connections can be done effectively with circular queues, as they allocate and recycle resources without interruptions.

Application Level

  • Event Handling Systems: Many applications that need to handle a flow of incoming events, such as user inputs or system actions, use circular queues. This ensures all events are processed in a timely manner without any being skipped.
     
  • Data Stream Management: Applications that deal with continuous data streams, such as multimedia applications or telemetry systems, use circular queues to maintain a steady handling of data samples.

Consumer Devices

Circular Buffers in Media Players: Audio and video players use circular buffers to preload media data, which allows for smooth playback and control over streaming media, reducing lags or buffer underflow.

Frequently Asked Questions

What makes a circular queue different from a normal queue?

A circular queue uses its space more efficiently by wrapping around to the beginning when it reaches the end, unlike a normal queue that leaves space unused after dequeuing elements.

Can a circular queue become full if there is an empty space at the beginning?

Yes, a circular queue can be full even if there are empty spaces at the beginning because it depends on the position of the front and rear pointers. If the rear pointer is just behind the front pointer, the queue is considered full.

How do you check if a circular queue is empty or full?

The queue is empty if the front pointer is at -1. It’s full if (rear + 1) % capacity == front, which means the next position of the rear after incrementing will point to the front.

Conclusion

In this article, we have learned about circular queues, a dynamic data structure that optimizes storage use and improves data processing efficiency. We covered how circular queues operate, including their basic operations like enqueue and dequeue, and explored how to implement them using arrays in various programming languages. We also talked about their applications across different fields such as computer systems, networking, and consumer devices, demonstrating their wide-ranging utility. 

You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSADBMSCompetitive ProgrammingPythonJavaJavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure andAlgorithmsCompetitive ProgrammingOperating SystemsComputer Networks, DBMSSystem Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.

Previous article
Linked Transfer Queue
Next article
Priority Blocking Queue
Live masterclass