×

Circular Queue

Circular Queue

Circular Queue is special type queue, which follows First in First Out (FIFO) rule and as well as instead of ending queue at the last position, it starts again from the first position after the last position and behaves like circular linear data structure.

We can say it is extension of the queue data structure such that last element of the queue is associated with the first element of the queue and it is also referred as Circular Buffer. If we talk about normal queue, no additional element can be added if queue if full. Also, we can’t add the element in the queue if there is space left in front of queue, so to overcome this problem Circular Queue comes to the picture, so we can use circular queue to solve this problem with efficient manner.

Circular Queue

Operations on Circular Queue

Enqueue Operation in Circular Queue:

  • Firstly, we have to whether the queue is full or not
  • For adding the first element in the queue, set front to 0
  • Increase rear by 1 circularly and add the new element at the position which is pointed by rear

Dequeue Operation in Circular Queue:

  • Firstly, we have to check whether the queue is empty or not.
  • Return the element which is pointed by front.
  • Increase front by 1
  • In case of last element of the queue, set values of front and rear to -1

Implementation of Circular Queue

The number of ways for implementing the circular queue using:

  • Array
  • Linked List

Circular Queue Implementation in C language

Using Array: -

# include < stdio.h >
   # define  len 7
  int queue[len];
   int front = -1, rear = -1;
 void enQueue(int item) // For add an element to the queue
  {
 if ((front == rear+1) || (front == 0 && rear == len-1)) // For checking whether the queue is full or not
    {
     printf("\nQueue is full\n");
     return;
    }
    else
   {
   if(front  ==  -1)
    {
   front = 0;
    }          
 rear = (rear+1) % len;
  queue[rear] = item;
 }          
  }
 void deQueue()   // For remove an element from the queue
  {
 if( front == -1 && rear == -1)     // For checking whether the queue is empty or not
   {
  printf("\nQueue is Empty\n");
  return;
  }
 else
  {
  printf("\n Deleted Element is %d" , queue[front]);
        if(front == rear)
    {
 front = - 1;
  rear = - 1;
   }
   else
  front = (front+1) % len;
        }
   }
    void traverse() //For print the elements of the queue
   {
  int i = front;
  printf("\nFront: ");
  while(i != rear)
  {          
    printf("%d ",queue[i]);
    i = (i+1) % len;
      }
     printf("%d",queue[rear]);
   printf(" :Rear");
       }
 int main()    // Driver code
 {
        enQueue(23);
     enQueue(33);
     enQueue(43);
       enQueue(53);
      enQueue(63);
  enQueue(73);
 enQueue(83);
     traverse();
 deQueue();
      traverse();
 enQueue(55);
     traverse();
   return 0;
 } 

Output

Circular Queue

Using LinkedList: -

#include<stdio.h>
 #include<stdlib.h>
 struct node // For declaration new node
 {
             int data;
             struct node* next;
 };
 struct node *front = NULL;
 struct node *rear = NULL;
 void enQueue(int d) // For add an element to the queue
 {
             struct node * n;
             n = (struct node*)malloc(sizeof(struct node));
             n->data = d;
             n->next = NULL;
             if((front == NULL)&&(rear == NULL))
             {
                         front = rear = n;
                         rear->next = front;
             }
             else
             {
                         rear->next = n;
                         rear = n;
                         n->next = front;
             }
 }
 void deQueue()// For remove an element from the queue
 {
             struct node* t;
             t = front;
             if((front == NULL)&&(rear == NULL)) // For checking whether the queue is empty or not
                         printf("\nQueue is Empty!!");
             else if(front == rear)
 {
                         front = rear = NULL;
                         free(t);
             }
             else
 {
                         front = front->next;
                         rear->next = front;
                         free(t);
             }
 }
 void traverse()//For print the elements of the queue
 {
             struct node* t;
             t = front;
             if((front==NULL)&&(rear==NULL))
                         printf("\nQueue is Empty!!");
             else{
                 printf("Queue elements are:");
                         do{
                                     printf("%d ",t->data);
                                     t = t->next;
                         }while(t != front);
             }
 }
 int main() // Driver code
 {
             int choice,n,i,data;     
             do{
                         printf("\n1 for Insert the Data \n2 for print the Data \n3 for Delete the data \n4 for Exit");
                         printf("\nEnter Your Choice:-");
                         scanf("%d",&choice);
                         switch(choice)
 {
           case 1:
                 printf("\nEnter the number of data: ");
                  scanf("%d",&n);
                  printf("\nEnter your data: ");
                 i=0;
               while(i<n){
             scanf("%d",&data);
            enQueue(data);
             i++;
       }
               break;
               case 2:
                traverse();
                break;
             case 3:
             deQueue();
              break;
      case 4:
         break;
       }
      }
 while(choice!=4);
 return 0;
 } 

Outputs: -

Circular Queue

Circular Queue Implementation in Java language

  public class CircularQueue
 {
 int len = 5;
 int front, rear;
 int queue[] = new int[len];
 CircularQueue()
  {
 front = -1;
 rear = -1;
 }
 int isFull()// For checking whether the queue is full or not
 {
 if (front == 0 && rear == len -1 || front == rear + 1 )
 {
 return 1;
 }
 return 0;
 }
 int isEmpty()// For checking whether the queue is empty or not
 {
 if (front == -1)
 return 1;
 else
 return 0;
 }
 void enQueue(int item) // For add an element to the queue
 {
 if (isFull()==1)
 {
 System.out.println("Queue is full");
 }
 else
 {
 if (front == -1)
 front = 0;
 rear = (rear + 1) % len;
 queue[rear] = item;
 }
 }
 int deQueue()// For remove an element from the queue
 {
 int item;
 if (isEmpty()==1)
 {
 System.out.println("Queue is empty");
 return (-1);
 }
 else
 {
 item = queue[front];
 if (front == rear)
 {
 front =  -1;
 rear =  -1;
 }
 else
 {
 front = (front + 1) % len;
 }
 return (item);
 }
 }
 void traverse()//For print the elements of the queue
 {
 int i;
 if (isEmpty() == 1)
 {
 System.out.println("Empty Queue");
 }
 else
 {
 System.out.print("Front: ");
 for (i = front ; i != rear ; i = (i + 1) % len)
 System.out.print(queue[i] + " ");
 System.out.print(queue[i]);
 System.out.println(" :Rear" );
 }
 }
 public static void main(String[] args)// Driver code
 {
 CircularQueue q = new CircularQueue();
 q.deQueue();
 q.enQueue(1);
 q.enQueue(2);
 q.enQueue(3);
 q.enQueue(4);
 q.enQueue(5);
 q.enQueue(6);
 q.traverse();
 int element = q.deQueue();
 if (element != -1)
 {
 System.out.println("Deleted Element is " + element);
 }
 q.traverse();
 q.enQueue(7);
 q.traverse();
 q.enQueue(8);
 }
 } 

Output: -

Circular Queue

Time Complexity: -

if we talk about time complexity of enqueue and dequeue operation of a Circular Queue is O(1) for array Implementation.

Advantages of Circular Queue

  • No leaks of memory because it doesn’t use dynamic memory.
  • Simple implementation
  • All operations in constant time O(1)

Applications of Circular Queue

  • Memory Management in Operating System
  • CPU Scheduling
  • Buffering Data Streams
  • Trafficking Signal Systems

Related Topics

Application of Stack in Data Structures

In this article, we will discuss all the different applications of stack. What is meant by stack? The stack is a non-primitive linear data structure in which the insertion of the new...

11 minutes read.

Treap data structure

In this article, we will discuss the treap data structure. The word treap is a combination of 'tree' and 'heap'. So, treap data structure is a combination of a heap...

8 minutes read.

Types of Data Structures

Almost every programme or software system that has been built makes use of data structures. Furthermore, data structures are basics of computer science and software engineering. When it comes to...

7 minutes read.

AVL Tree

AVL Tree AVL Tree is referred to as self-balanced or height-balanced binary search tree where the difference between heights of its left subtree and right subtree (Balance Factor) can't more than...

25 minutes read.

Bubble sort algorithm using Javascript

Sorting is a very useful technique in many algorithms and programs. Basically, sorting operations help us to arrange a set of data in a particular manner. Bubble sort is one...

3 minutes read.

Heap Data Structure

In this article, we will learn in detail about Heap (Min heap and Max heap). Before going to the main topics, let’s have a look at what is complete binary...

19 minutes read.

Optimal binary search tree in DSA

Implementation // A simple way of the recursive implementation of the optimal search that we will perform on the binary tree.   #include <bits/stdc++.h> using namespace std; // we have to create a basic utility...

8 minutes read.

Find the fractional (n/kth) node in the linked list

Find the fractional (n/kth) node in the linked list In this problem, we have given a singly linked list and a number k. Here we need to find the (n/k)th element...

2 minutes read.

Permutation Sort or Bogo Sort

In Permutation Sort or Bogo Sort, you have been given one array, which consists of different values. You have to sort the array using BOGO sort. Let’s take an example: Input-...

3 minutes read.

Depth of binary tree

We all know that a binary tree is a kind of tree that helps us maintain the order and balance of the tree. It is a type of tree in...

4 minutes read.

What are Forest Trees in Data Structure

Data structure A data model manages and optimizes computer resources, and a database stores and manages data. It's one of many uses for data structures to hold data. Data structures come...

5 minutes read.

Stack vs Array

Difference between Array and Stack In this article, we are going to discuss the major differences between the stack and array data structures: Array – In the data structure, the array is...

3 minutes read.

Dijkstra’s vs Bellman-Ford Algorithm

The Dijkstra Algorithm One of the SSSP (Single Source Shortest Path) algorithms is Dijkstra's. As a result, it finds the shortest path between a source node and all other nodes in...

7 minutes read.

Semi-Structured data

In this article, we will discuss the semi-structured data. Data can be defined as the distinct piece of information that is gathered and translated for some purpose. It can be...

5 minutes read.

Binary Tree Inorder Traversal

The binary tree is a type of tree in which each and every node has atleast two children except the leaf nodes. We have various operations in the binary tree,...

4 minutes read.

Singly Linked list

Singly Linked list A singly linked list is a kind of linked list which is unidirectional. If we talk about singly linked list, then we can say it can be traversed...

3 minutes read.

Delete a Node without head pointer from the linked list

Delete a Node without head pointer from the linked list This article will explain how to delete a node without a head pointer from the linked list. We have given a...

2 minutes read.

Red Black Tree vs AVL Tree: Data Structure

Difference Between Red Black Tree vs AVL Tree Red Black Tree: A red-black tree is referred as self-balancing binary search tree. In red-black, each node stores an extra bit that determines...

4 minutes read.

About Data Structures

What exactly are data structures? A data structure is a type of storage that is used to organise and store data. It is a method of organising data on a computer...

5 minutes read.

Blowfish algorithm

The Blowfish algorithm is the very first encryption algorithm which is symmetric. It was firstly used as an alternate algorithm for the DES algorithm. It was designed by Bruce Steiner...

3 minutes read.