Horje
How to manage Full Circular Queue event?

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. 
    1. Check whether queue is Full – Check ((rear == SIZE-1 && front == 0) || (rear == front-1)).
    2. 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. 
    1. Check whether the queue is Empty means check (front==-1).
    2. If it is empty then display Queue is empty. If the queue is not empty then step 3
    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 queue
void 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 Queue
int 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 Queue
void 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 code
int 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 Queue
 
import 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 code
q = Queue(5)
 
# Inserting elements in Circular Queue
q.enQueue(14)
q.enQueue(22)
q.enQueue(13)
q.enQueue(-6)
q.displayQueue()
 
# Deleting elements from Circular Queue
print("\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 Queue
 
using 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:

  1. 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.
  2. 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.
  3. 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.
  4. 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:


 


Reffered: https://www.geeksforgeeks.org

Data Structures

Related
How is the default max Java Heap size determined? How is the default max Java Heap size determined?
Should we declare as Queue or Priority Queue while using Priority Queue in Java? Should we declare as Queue or Priority Queue while using Priority Queue in Java?
Python Program to Reverse all Prime Numbers in Array Without Affecting Elements Python Program to Reverse all Prime Numbers in Array Without Affecting Elements
Python Program to find XOR of all the key value pairs in a Dictionary Python Program to find XOR of all the key value pairs in a Dictionary
Python Program to Get Sum of cubes of alternate even numbers in an array Python Program to Get Sum of cubes of alternate even numbers in an array

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 18



 

Horje