Explain Circular Queue?

Circular Queue

Deletions and insertions can only be performed at front and rear end respectively, as far as linear queue is concerned.

Consider the queue shown in the following figure.

 

The Queue shown in above figure is completely filled and there can't be inserted any more element due to the condition rear == max - 1 becomes true.

However, if we delete 2 elements at the front end of the queue, we still can not insert any element since the condition rear = max -1 still holds.

This is the main problem with the linear queue, although we have space available in the array, but we can not insert any more element in the queue. This is simply the memory wastage and we need to overcome this problem.

 

One of the solution of this problem is circular queue. In the circular queue, the first index comes right after the last index. You can think of a circular queue as shown in the following figure.

 

Circular queue will be full when front = -1 and rear = max-1. Implementation of circular queue is similar to that of a linear queue. Only the logic part that is implemented in the case of insertion and deletion is different from that in a linear queue.

Complexity

Time Complexity

Front	O(1)
Rear	O(1)
enQueue()	O(1)
deQueue()	O(1)

Insertion in Circular queue

There are three scenario of inserting an element in a queue.

1. If (rear + 1)%maxsize = front, the queue is full. In that case, overflow occurs and therefore, insertion can not be performed in the queue.
2. If rear != max - 1, then rear will be incremented to the mod(maxsize) and the new value will be inserted at the rear end of the queue.
3. If front != 0 and rear = max - 1, then it means that queue is not full therefore, set the value of rear to 0 and insert the new element there.

Algorithm to insert an element in circular queue

• Step 1: IF (REAR+1)%MAX = FRONT
  Write " OVERFLOW "
  Goto step 4
  [End OF IF]
• Step 2: IF FRONT = -1 and REAR = -1
  SET FRONT = REAR = 0
  ELSE IF REAR = MAX - 1 and FRONT ! = 0
  SET REAR = 0
  ELSE
  SET REAR = (REAR + 1) % MAX
  [END OF IF]
• Step 3: SET QUEUE[REAR] = VAL
• Step 4: EXIT

C Function

1. void insert(int item, int queue[])  
2. {  
3.     if((rear+1)%maxsize == front)  
4.     {  
5.         printf("\nOVERFLOW");  
6.         return;  
7.     }  
8.     else if(front == -1 && rear == -1)  
9.     {  
10.         front = 0;  
11.         rear = 0;  
12.     }  
13.     else if(rear == maxsize -1 && front != 0)   
14.     {  
15.         rear = 0;  
16.     }  
17.     else   
18.     {  
19.         rear = (rear+1)%maxsize;  
20.     }  
21.     queue[rear] = item;  
22. }  

Algorithm to delete an element from a circular queue

To delete an element from the circular queue, we must check for the three following conditions.

1. If front = -1, then there are no elements in the queue and therefore this will be the case of an underflow condition.
2. If there is only one element in the queue, in this case, the condition rear = front holds and therefore, both are set to -1 and the queue is deleted completely.
3. If front = max -1 then, the value is deleted from the front end the value of front is set to 0.
4. Otherwise, the value of front is incremented by 1 and then delete the element at the front end.

Algorithm

• Step 1: IF FRONT = -1
  Write " UNDERFLOW "
  Goto Step 4
  [END of IF]
• Step 2: SET VAL = QUEUE[FRONT]
• Step 3: IF FRONT = REAR
  SET FRONT = REAR = -1
  ELSE
  IF FRONT = MAX -1
  SET FRONT = 0
  ELSE
  SET FRONT = FRONT + 1
  [END of IF]
  [END OF IF]
• Step 4: EXIT

C Function

1. void delete()  
2. {   
3.     if(front == -1 & rear == -1)  
4.     {  
5.         printf("\nUNDERFLOW\n");  
6.         return;  
7.     }  
8.     else if(front == rear)  
9.     {  
10.         front = -1;  
11.         rear = -1;  
12.     }  
13.     else if(front == maxsize -1)  
14.         {  
15.             front = 0;  
16.         }  
17.     else   
18.         front = front + 1;  
19. }  

Menu-Driven program implementing all the operations on a circular queue

1. #include<stdio.h>   
2. #include<stdlib.h>  
3. #define maxsize 5  
4. void insert();  
5. void delete();  
6. void display();  
7. int front = -1, rear = -1;  
8. int queue[maxsize];  
9. void main ()  
10. {  
11.     int choice;   
12.     while(choice != 4)   
13.     {     
14.         printf("\n*************************Main Menu*****************************\n");  
15.         printf("\n=================================================================\n");  
16.         printf("\n1.insert an element\n2.Delete an element\n3.Display the queue\n4.Exit\n");  
17.         printf("\nEnter your choice ?");  
18.         scanf("%d",&choice);  
19.         switch(choice)  
20.         {  
21.             case 1:  
22.             insert();  
23.             break;  
24.             case 2:  
25.             delete();  
26.             break;  
27.             case 3:  
28.             display();  
29.             break;  
30.             case 4:  
31.             exit(0);  
32.             break;  
33.             default:   
34.             printf("\nEnter valid choice??\n");  
35.         }  
36.     }  
37. }  
38. void insert()  
39. {  
40.     int item;  
41.     printf("\nEnter the element\n");  
42.     scanf("%d",&item);    
43.     if((rear+1)%maxsize == front)  
44.     {  
45.         printf("\nOVERFLOW");  
46.         return;  
47.     }  
48.     else if(front == -1 && rear == -1)  
49.     {  
50.         front = 0;  
51.         rear = 0;  
52.     }  
53.     else if(rear == maxsize -1 && front != 0)   
54.     {  
55.         rear = 0;  
56.     }  
57.     else   
58.     {  
59.         rear = (rear+1)%maxsize;  
60.     }  
61.     queue[rear] = item;  
62.     printf("\nValue inserted ");  
63. }  
64. void delete()  
65. {  
66.     int item;   
67.     if(front == -1 & rear == -1)  
68.     {  
69.         printf("\nUNDERFLOW\n");  
70.         return;  
71.     }  
72.     else if(front == rear)  
73.     {  
74.         front = -1;  
75.         rear = -1;  
76.     }  
77.     else if(front == maxsize -1)  
78.         {  
79.             front = 0;  
80.         }  
81.     else   
82.         front = front + 1;  
83. }  
84.       
85. void display()  
86. {  
87.    int i;        
88.    if(front == -1)  
89.       printf("\nCircular Queue is Empty!!!\n");  
90.    else  
91.    {  
92.       i = front;  
93.       printf("\nCircular Queue Elements are : \n");  
94.       if(front <= rear){  
95.      while(i <= rear)  
96.         printf("%d %d %d\n",queue[i++],front,rear);  
97.       }  
98.       else{  
99.      while(i <= maxsize - 1)  
100.         printf("%d %d %d\n", queue[i++],front,rear);  
101.      i = 0;  
102.      while(i <= rear)  
103.         printf("%d %d %d\n",queue[i++],front,rear);  
104.       }  
105.    }  
106. }  

Output:

**********Main Menu**********

=============================

1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?1

Enter the element
1

Value inserted 
**********Main Menu**********

=============================
1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?1

Enter the element
2

Value inserted 
**********Main Menu**********

=============================
1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?1

Enter the element
3

Value inserted 
**********Main Menu**********

=============================
1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?3

Circular Queue Elements are : 
1
2
3

**********Main Menu**********

=============================
1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?2

**********Main Menu**********

=============================
1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?1

Enter the element
4

Value inserted 
**********Main Menu**********

=============================
1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?3

Circular Queue Elements are : 
2
3
4

**********Main Menu**********

=============================
1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?1

Enter the element
1

OVERFLOW
**********Main Menu**********

=============================
1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?

4