Why circular queue is preferred over linear queue ? Write down algorithms for inserting and deleting item form circular queue.

Illustrating using real-life examples, the term queue is very familiar to us in our day to day life, as we see people standing in a queue at various places. In any situation, a person who just arrives will stand at the end of the queue and the person who is leading the queue is the one who reached that particular place before anywhere else. 

Now in the data structure, we use the same concept the definition of the queue says that the 

A queue is an ordered collection of items where elements are inserted from one end and are deleted from another end. The end where then new elements are added is known as rear-end whereas the other end where deletion takes place is known as front end.

Using this approach in the Queue we have an acronym i.e FIFO which means First In First Out. Hence, the Queue is a FIFO data structure.

Since queue elements are stored in linear order, it can be implemented using arrays and linked lists. Based on the insertion and deletion of elements the queue is classified as:

• Linear Queue
• Circular Queue
• Double-ended Queue (Dequeue)
• Priority Queue

What is Linear Queue and Circular Queue? 

Linear Queue:  It is also known as an ordinary key and working is based on the FIFO approach.

Circular Queue: In the circular queue, the elements of a given can be stored in an array so as to "Wrap Around" accordingly the rear end of the queue is followed by the front end of the queue.

How is a  Circular Queue better than a Linear Queue? 

• Memory Space:  Linear queue drains the memory space while the circular makes the valuable and efficient use of space.

• Linear queue follows first in first out order whereas the circular queue doesn't have any specific order.

• The insertion and deletion of the elements are fixed in linear queue i.e, addition from the rear end and deletion from the front end. On the other hand, the circular queue is capable of inserting and deleting the element from any point or any side until it is abandoned or unoccupied. 

Algorithm for inserting and deleting items from the circular queue.

Insertion in Circular queue

There are three scenarios of inserting in a queue. 

1. If (rear + 1)% max size = 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 real will be incremented to the mod(max size) and the new value will be inserted at the real end of the queue. 
3. If front !=0 and rear = max-1, then it means that the queue is not full, therefore, set the value of rear to 0 and insert the new element there.

Algorithm to insert an element in a circular queue.

Step 1: IF (REAR+1)%MAX = FRONT

Write " OVERFLOW "

Go to 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. }  

Deletion in 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 the front is incremented by 1 and then deletes the element at the front end.

Algorithm to delete an element in the circular queue.

Step 1: IF FRONT = -1

Write " UNDERFLOW "

Go to 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. }  

Program to insert and delete element in the 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

Views