Circular queue and its operations

Circular Queue is a linear data structure that follows FIFO (First In First Out) principle. FIFO means item that inserted first in queue will be taken out first.

Why Circular queue?

There was a limitation in normal Queue that if rear reaches at the end of size of queue and there are some space left in front of queue which cannot be utilized. So, to overcome such limitations the concept of the circular queue has come.

Front: Front is used to get front item from the Queue.

Rear: Rear is used to get rear item from the Queue.

Operations on Circular Queue

The following are the operations that can be performed on a circular queue:

• enQueue(value)
• deQueue()

enQueue(value)

This function is used to insert an item in the Queue. The new item will be inserted from the rear only if there is some space available in queue.

There are two scenarios in which queue have some space:

• If rear != max – 1, then rear will be incremented to mod(maxsize) and the new value will be inserted at the rear end of the queue.
• If front != 0 and rear = max – 1, it means that the queue is not full, then set the value of rear to 0 and insert the new element there.

There are two cases in which the element cannot be inserted:

• When front ==0 && rear = max-1, which means that front is at the first position of the Queue and rear is at the last position of the Queue.
• if front== rear + 1; display Queue is full.

Steps to perform Enqueue Operation

enQueue() is a function which is used to insert an element into the circular queue. In a circular queue, the new element is always inserted at rear position. The enQueue() function takes one integer value as parameter and inserts that value into the circular queue. Below are the following steps to insert an element into the circular queue

Algorithm to perform enqueue operation in a circular queue

 step 1: Check IF FRONT == 0 and REAR == SIZE - 1  or  FRONT == REAR + 1  Then Display "Queue is Overflow"
 step 2: IF FRONT = -1 and REAR = -1 then SET FRONT = REAR = 0  
 step 3: Else If rear != SIZE - 1 then set REAR = REAR + 1  goto step 5
 step 4: Else If front != 0 and rear = SIZE - 1 then set REAR=0
 step 5: Set QUEUE[REAR] = ITEM
 step 6: Print: ITEM inserted
 step 7: Exit 

deQueue()

This function is used to delete an item from the Queue. Item will be delete from the front of a Queue only if there is atleast one item in queue.

Steps to perform Dequeue Operation

• If front = –1, then there are no elements in the queue. So, an underflow condition will be reported.
• If the queue is not empty and front = rear, then after deleting the element at the front the queue becomes empty and the front and rear are set to –1.
• If the queue is not empty and front = MAX–1, then after deleting the element at the front, the front is set to 0.

Algorithm to perform dequeue operation in a circular queue

 deQueue()
 Step 1: If FRONT = -1 then Display "Queue is Underflow" and Goto step 5
 Step 2: Print value QUEUE[FRONT]
 Step 3: If REAR == FRONT then set FRONT = -1 and REAR = -1
 Step 4: Else If FRONT == SIZE-1 then FRONT = 0 else FRONT = FRONT + 1
 Step 5: Exit 

C Program to insert the element in circular queue

#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
int cqueue[5];
int front = -1, rear = -1, n=5;
void enqueue(int val){
    if ((front == 0 && rear == n-1) || (front == rear+1)) {
      printf("Queue Overflow \n");
      return;
   }
   if (front == -1) {
      front = 0;
      rear = 0;
   }
   else {
      if (rear == n - 1)
         rear = 0;
      else
         rear = rear + 1;
   }
   cqueue[rear] = val ;
}
void display(){
   int f = front, r = rear;
   if (front == -1) {
       printf("Queue is empty");
      return;
   }
   printf("Queue elements are :\n");
   if (f <= r) {
      while (f <= r){
          printf("%d", cqueue[f]);
         f++;
      }
   }
   else {
      while (f <= n - 1) {
          printf("%d",cqueue[f]);
         f++;
      }
      f = 0;
      while (f <= r) {
          printf("%d",cqueue[f]);
         f++;
      }
   }
  
}  
  
int menu(){
    int choice;
    printf("\n 1.Add value to the list");   
    printf("\n 2. Travesre/View List");
    printf("\n 3. exit");
    printf("\n Please enter your choice: \t");
    scanf("%d",&choice);
    return(choice);
}
void main(){
    int value;
    while(1){
        switch(menu()){
            case 1:
                printf("Input for insertion: ");
                scanf("%d",&value);
                enqueue(value);
                break;          
            case 2:
                display();
                break;
            case 3:
                exit(0);
            default:
                printf("invalid choice");
        }
    }
        getch();
    }

---

[wpusb]