Circular Queue

Difficulty Level Easy
Frequently asked in Infosys MAQ o9 solutions Oracle
Queue School Programming TheoryViews 1802

A circular queue is an advanced form of a linear queue. In the linear queue, we can’t insert an element in the queue if the rear is pointing to the last index of the queue and the queue is not completely filled. This causes wastage of memory. To overcome this wastage we use the circular queue.

In a circular queue if the last index is filled then, then the rear points to the first index of the queue. It works on the First In First Out (FIFO) principle.

The red arrow is a front pointer and the black arrow is a rear pointer.

Circular Queue

 

Basic terminologies 

  1. Front: The first pointer points to the first element in the queue.
  2. Rear: The rear pointer points to the last element in the queue.
  3. Enqueue:  inserting an element into the queue is called enqueue.
  4. Dequeue: It is the process of deleting an element from the queue.

Insertion in the circular queue

Step-1:

  • Check if the queue is completely filled or not.
  • If (rear==queue size-1 AND front==0) OR (rear==front-1) then the queue is completely filled and we can’t  insert more elements in it.

Step-2:

  • Otherwise ,we check if rear ==queue size-1 then we assign rear =0 else rear =rear+1 and then we insert an element at rear position.

Deletion in the circular queue

Step-1:

  • We check if the queue contains any element.
  • If front ==-1 then the queue is empty.

Step-2:

  • When the queue is not empty and both front and the rear pointer is pointing to the same index then assign front=-1 and rear=-1  Otherwise, if front == queue size-1  then front =0.

Circular Queue

C++ program for insertion and deletion in Circular Queue

// C or C++ program for insertion and 
// deletion in Circular Queue 
#include<bits/stdc++.h> 
using namespace std; 

struct 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]; 
  } 

  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; 
  } 

  else if (front == -1) /* Insert First Element */
  { 
    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 of the program */
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; 
} 
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

Java program for insertion and deletion in Circular Queue

// Java program for insertion and 
// deletion in Circular Queue 
import java.util.* ; 

class Solution 
{ 
  
// Structure of a Node 
static class Node 
{ 
  int data; 
  Node link; 
} 
  
static class Queue 
{ 
  Node front, rear; 
} 
  
// Function to create Circular queue 
static void enQueue(Queue q, int value) 
{ 
  Node temp = new Node(); 
  temp .data = value; 
  if (q .front == null) 
    q .front = temp; 
  else
    q .rear .link = temp; 
  
  q .rear = temp; 
  q .rear .link = q .front; 
} 
  
// Function to delete element from Circular Queue 
static int deQueue(Queue q) 
{ 
  if (q .front == null) 
  { 
    System.out.printf ("Queue is empty"); 
    return Integer.MIN_VALUE; 
  } 
  
  // If this is the last node to be deleted 
  int value; // Value to be dequeued 
  if (q .front == q .rear) 
  { 
    value = q .front .data; 
    q .front = null; 
    q .rear = null; 
  } 
  else // There are more than one nodes 
  { 
    Node temp = q .front; 
    value = temp .data; 
    q .front = q .front .link; 
    q .rear .link= q .front; 
  } 
  
  return value ; 
} 
  
// Function displaying the elements of Circular Queue 
static void displayQueue( Queue q) 
{ 
  Node temp = q .front; 
  System.out.printf("\nElements in Circular Queue are: "); 
  while (temp .link != q .front) 
  { 
    System.out.printf("%d ", temp .data); 
    temp = temp .link; 
  } 
  System.out.printf("%d", temp .data); 
} 
  
/* Driver of the program */
public static void main(String args[]) 
{ 
  // Create a queue and initialize front and rear 
  Queue q = new Queue(); 
  q .front = q .rear = null; 
  
  // Inserting elements in Circular Queue 
  enQueue(q, 14); 
  enQueue(q, 22); 
  enQueue(q, 6); 
  
  // Display elements present in Circular Queue 
  displayQueue(q); 
  
  // Deleting elements from Circular Queue 
  System.out.printf("\nDeleted value = %d", deQueue(q)); 
  System.out.printf("\nDeleted value = %d", deQueue(q)); 
  
  // Remaining elements in Circular Queue 
  displayQueue(q); 
  
  enQueue(q, 9); 
  enQueue(q, 20); 
  displayQueue(q); 
  
} 
}
Elements in Circular Queue are: 14 22 6
Deleted value = 14
Deleted value = 22
Elements in Circular Queue are: 6
Elements in Circular Queue are: 6 9 20

Time Complexity

  1. enqueue() : O(1).
  2. dequeue() : O(1).

Application in real life

  1. In CPU scheduling the job which comes first is executed first.
  2. A computer-controlled traffic system uses a circular queue for traffic control.

References

Translate »