What is a circular Queue?
A circular queue is a non-primitive, linear data structure. It is an extended version of a linear queue. It is also called a Circular buffer or cyclic buffer. It offers a quick and clean way of storing First First Out (FIFO) data with a maximum size.
Mainly it is used in memory management, process scheduling, and traffic systems, and also o good for serial data stream operation in Embedded systems.
Operations on Circular Queue:
- Front: Get the front item from the queue.
- Rear: Get the last item from the queue.
- enQueue(value) This function is used to insert an element into the circular queue. In a circular queue, the new element is always inserted at the Rear position.
- Check whether queue is Full – Check ((rear == SIZE-1 && front == 0) || (rear == front-1)).
- If it is full then display Queue is full. If the queue is not full then, check if (rear == SIZE – 1 && front != 0) if it is true then set rear=0 and insert the element.
- deQueue() This function is used to delete an element from the circular queue. In a circular queue, the element is always deleted from the front position.
- Check whether the queue is Empty means check (front==-1).
- If it is empty then display Queue is empty. If the queue is not empty then step 3
- Check if (front==rear) if it is true then set front=rear= -1 else check if (front==size-1), if it is true then set front=0 and return the element.
Full Circular Event (Overflow):
In a circular queue, when the queue becomes full it will start overwriting the inputs from the beginning of the queue.
Initially, when such a queue is empty, the “front” and the “rear” values are 0 & -1 respectively; and the queue has a NULL value for its entire element.
Every time we add an element to the queue, the “rear” value increments by 1 until it reaches the queue’s upper limit; after which it starts over again from 0. Similarly, every time we delete an element from the queue, the “front” value increments by 1 until it reaches the queue’s upper limit; after which it starts over again from 0.
Managing Full Circular Queue
- First initialize the queue, the size of the queue (i.e. MaxSize), and front & rear pointers.
- Enqueue:
- Check if the no. of elements is equal to the max size of the queue.
- If true, Print “Queue is full”
- If false, increment the rear pointer by 1.
- Dequeue:
- Check if the no. of elements is equal to zero
- If true, Print “Queue is empty”.
- If false, increment the front position by 1.
- Size:
- If rear ≥ front then, size = rear – front.
- If front > rear then, size = MaxSize – (front – rear).
Pseudo Codes:
Enqueue operation:
void enqueue(Queue q, int x)
{
if((rear+1)%maxsize)==front)
{
printf(“overflow”);
break;
}
else if(rear!=-1)
{
rear=(rear+1)%maxsize;
q[rear]=x;
}
}
Dequeue operation:
void dequeue(Queue q)
{
if(front!=-1)
printf(“underflow”);
else
front=(front+1)%maxsize;
}
Below is the implementation of the above approach.
C++
// C++ program for insertion and// deletion in Circular Queue#include <bits/stdc++.h>using namespace std;class Queue { // Initialize front and rear int rear, front; // Circular Queue int size; int* arr;public: Queue(int s) { front = rear = -1; size = s; arr = new int[s]; } void enQueue(int value); int deQueue(); void displayQueue();};// Function to create Circular queuevoid Queue::enQueue(int value){ if ((front == 0 && rear == size - 1) || (rear == (front - 1) % (size - 1))) { printf("\nQueue is Full"); return; } // Insert First Element else if (front == -1) { front = rear = 0; arr[rear] = value; } else if (rear == size - 1 && front != 0) { rear = 0; arr[rear] = value; } else { rear++; arr[rear] = value; }}// Function to delete element from Circular Queueint Queue::deQueue(){ if (front == -1) { printf("\nQueue is Empty"); return INT_MIN; } int data = arr[front]; arr[front] = -1; if (front == rear) { front = -1; rear = -1; } else if (front == size - 1) front = 0; else front++; return data;}// Function displaying the elements// of Circular Queuevoid Queue::displayQueue(){ if (front == -1) { printf("\nQueue is Empty"); return; } printf("\nElements in Circular Queue are: "); if (rear >= front) { for (int i = front; i <= rear; i++) printf("%d ", arr[i]); } else { for (int i = front; i < size; i++) printf("%d ", arr[i]); for (int i = 0; i <= rear; i++) printf("%d ", arr[i]); }}// Driver codeint main(){ Queue q(5); // Inserting elements in Circular Queue q.enQueue(14); q.enQueue(22); q.enQueue(13); q.enQueue(-6); // Display elements present in Circular Queue q.displayQueue(); // Deleting elements from Circular Queue printf("\nDeleted value = %d", q.deQueue()); printf("\nDeleted value = %d", q.deQueue()); q.displayQueue(); q.enQueue(9); q.enQueue(20); q.enQueue(5); q.displayQueue(); q.enQueue(20); return 0;} |
Java
// Java program for insertion and// deletion in Circular Queueimport java.io.*;class Queue { // Initialize front and rear int rear, front; // Circular Queue int size; int[] arr; Queue(int s) { front = rear = -1; size = s; arr = new int[s]; } // Function to create Circular queue void enQueue(int value) { if ((front == 0 && rear == size - 1) || (rear == (front - 1) % (size - 1))) { System.out.println("Queue is Full"); return; } // Insert First Element else if (front == -1) { front = rear = 0; arr[rear] = value; } else if (rear == size - 1 && front != 0) { rear = 0; arr[rear] = value; } else { rear++; arr[rear] = value; } } // Function to delete element from Circular Queue int deQueue() { if (front == -1) { System.out.println("Queue is Empty"); return Integer.MIN_VALUE; } int data = arr[front]; arr[front] = -1; if (front == rear) { front = -1; rear = -1; } else if (front == size - 1) { front = 0; } else { front++; } return data; } // Function displaying the elements // of Circular Queue void displayQueue() { if (front == -1) { System.out.println("Queue is Empty"); return; } System.out.print( "Elements in Circular Queue are: "); if (rear >= front) { for (int i = front; i <= rear; i++) { System.out.print(arr[i] + " "); } } else { for (int i = front; i < size; i++) { System.out.print(arr[i] + " "); } for (int i = 0; i <= rear; i++) { System.out.print(arr[i] + " "); } } System.out.println(); }}class GFG { public static void main(String[] args) { Queue q = new Queue(5); // Inserting elements in Circular Queue q.enQueue(14); q.enQueue(22); q.enQueue(13); q.enQueue(-6); // Display elements present in Circular Queue q.displayQueue(); // Deleting elements from Circular Queue System.out.println("Deleted value = " + q.deQueue()); System.out.println("Deleted value = " + q.deQueue()); q.displayQueue(); q.enQueue(9); q.enQueue(20); q.enQueue(5); q.displayQueue(); q.enQueue(20); }}// This code is contributed by lokesh |
Python3
class Queue: # Initialize front and rear def __init__(self, s): self.front = self.rear = -1 self.size = s self.arr = [None] * s def enQueue(self, value): if (self.front == 0 and self.rear == self.size - 1) or (self.rear == (self.front - 1) % (self.size - 1)): print("\nQueue is Full") return # Insert First Element elif self.front == -1: self.front = self.rear = 0 self.arr[self.rear] = value elif self.rear == self.size - 1 and self.front != 0: self.rear = 0 self.arr[self.rear] = value else: self.rear += 1 self.arr[self.rear] = value def deQueue(self): if self.front == -1: print("\nQueue is Empty") return float("-inf") data = self.arr[self.front] self.arr[self.front] = None if self.front == self.rear: self.front = -1 self.rear = -1 elif self.front == self.size - 1: self.front = 0 else: self.front += 1 return data def displayQueue(self): if self.front == -1: print("\nQueue is Empty") return print("\nElements in Circular Queue are: ") if self.rear >= self.front: for i in range(self.front, self.rear+1): print(self.arr[i], end=" ") else: for i in range(self.front, self.size): print(self.arr[i], end=" ") for i in range(0, self.rear+1): print(self.arr[i], end=" ")# Driver codeq = Queue(5)# Inserting elements in Circular Queueq.enQueue(14)q.enQueue(22)q.enQueue(13)q.enQueue(-6)q.displayQueue()# Deleting elements from Circular Queueprint("\nDeleted value = ", q.deQueue())print("\nDeleted value = ", q.deQueue())q.displayQueue()q.enQueue(9)q.enQueue(20)q.enQueue(5)q.displayQueue()q.enQueue(20)# This code is contributed by akashish__ |
C#
// C# program for insertion and// deletion in Circular Queueusing System;class Queue { // Initialize front and rear public int rear, front; // Circular Queue public int size; public int[] arr; public Queue(int s) { front = rear = -1; size = s; arr = new int[s]; } // Function to create Circular queue public void enQueue(int value) { if ((front == 0 && rear == size - 1) || (rear == (front - 1) % (size - 1))) { Console.WriteLine("Queue is Full"); return; } // Insert First Element else if (front == -1) { front = rear = 0; arr[rear] = value; } else if (rear == size - 1 && front != 0) { rear = 0; arr[rear] = value; } else { rear++; arr[rear] = value; } } // Function to delete element from Circular Queue public int deQueue() { if (front == -1) { Console.WriteLine("Queue is Empty"); return Int32.MinValue; } int data = arr[front]; arr[front] = -1; if (front == rear) { front = -1; rear = -1; } else if (front == size - 1) { front = 0; } else { front++; } return data; } // Function displaying the elements // of Circular Queue public void displayQueue() { if (front == -1) { Console.WriteLine("Queue is Empty"); return; } Console.Write("Elements in Circular Queue are: "); if (rear >= front) { for (int i = front; i <= rear; i++) { Console.Write(arr[i] + " "); } } else { for (int i = front; i < size; i++) { Console.Write(arr[i] + " "); } for (int i = 0; i <= rear; i++) { Console.Write(arr[i] + " "); } } Console.WriteLine(); }}public class GFG { static public void Main() { Queue q = new Queue(5); // Inserting elements in Circular Queue q.enQueue(14); q.enQueue(22); q.enQueue(13); q.enQueue(-6); // Display elements present in Circular Queue q.displayQueue(); // Deleting elements from Circular Queue Console.WriteLine("Deleted value = " + q.deQueue()); Console.WriteLine("Deleted value = " + q.deQueue()); q.displayQueue(); q.enQueue(9); q.enQueue(20); q.enQueue(5); q.displayQueue(); q.enQueue(20); }}// This code is contributed by lokeshmvs21. |
Javascript
class Queue { // Initialize front and rear constructor(s) { this.front = this.rear = -1; this.size = s; this.arr = new Array(s); } enQueue(value) { if ((this.front === 0 && this.rear === this.size - 1) || (this.rear === (this.front - 1) % (this.size - 1))) { console.log("\nQueue is Full"); return; } // Insert First Element else if (this.front === -1) { this.front = this.rear = 0; this.arr[this.rear] = value; } else if (this.rear === this.size - 1 && this.front !== 0) { this.rear = 0; this.arr[this.rear] = value; } else { this.rear++; this.arr[this.rear] = value; } } deQueue() { if (this.front === -1) { console.log("\nQueue is Empty"); return Number.MIN_SAFE_INTEGER; } let data = this.arr[this.front]; this.arr[this.front] = -1; if (this.front === this.rear) { this.front = -1; this.rear = -1; } else if (this.front === this.size - 1) { this.front = 0; } else { this.front++; } return data; } displayQueue() { if (this.front === -1) { console.log("\nQueue is Empty"); return; } console.log("\nElements in Circular Queue are: "); if (this.rear >= this.front) { for (let i = this.front; i <= this.rear; i++) { console.log(this.arr[i] + " "); } } else { for (let i = this.front; i < this.size; i++) { console.log(this.arr[i] + " "); } for (let i = 0; i <= this.rear; i++) { console.log(this.arr[i] + " "); } } }}// Driver code let q = new Queue(5); // Inserting elements in Circular Queue q.enQueue(14); q.enQueue(22); q.enQueue(13); q.enQueue(-6); // Display elements present in Circular Queue q.displayQueue(); // Deleting elements from Circular Queue console.log("Deleted value = " + q.deQueue()); console.log("Deleted value = " + q.deQueue()); q.displayQueue(); q.enQueue(9); q.enQueue(20); q.enQueue(5); q.displayQueue(); q.enQueue(20);// This code is contributed by akashish__ |
Output
Elements in Circular Queue are: 14 22 13 -6 Deleted value = 14 Deleted value = 22 Elements in Circular Queue are: 13 -6 Elements in Circular Queue are: 13 -6 9 20 5 Queue is Full
Time Complexity: Time complexity of enQueue(), deQueue() operation is O(1) as there is no loop in any of the operation.
Auxiliary Space: O(N) where N is the maximum possible size of the queue.
When to use full circular queue?
A full circular queue is used in situations where a traditional linear queue is not suitable. The main advantage of a circular queue over a linear queue is that it allows for more efficient memory usage in certain cases.
Here are some common scenarios where a full circular queue is used:
- Real-time Systems: In real-time systems, such as embedded systems, a full circular queue can be used to buffer data that is generated at a high rate and processed at a slower rate. This helps to ensure that no data is lost and the system runs smoothly.
- Audio/Video Streaming: In audio and video streaming, a full circular queue can be used to buffer incoming data so that it can be played smoothly even if there are interruptions in the data flow.
- Networking: In networking, a full circular queue can be used to buffer incoming data packets so that they can be processed in a timely manner, even if the processing rate is slower than the incoming data rate.
- Batch Processing: In batch processing, a full circular queue can be used to store the items that need to be processed in a batch. Once the queue is full, the batch processing can be triggered to process all the items in the queue in one go.
Related Articles:
- Introduction to Queue – Data Structures and Algorithms Tutorials
- Introduction and Array Implementation of Circular Queue
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
