Circular Queue in Data Structures

Circular Queue

The Regular, static queues  in data structures have a very big drawback, that once the queue is FULL, even though we delete few elements. From the “  front” and relive some occupied space, we are not able to add anymore elements, as the “rear” has already reaches the queues rear most partition. To overcome this drawback we can implement the queue as a circular queue. Here as we go on adding elements to the queue and reach the end of the array, the next element is stored in the first slot of the array (provide it is free). As the name suggests, this queue is not straight but circular; meaning; you go to have a following structure like this         Initially when such a circular queue is empty ,the “Front” and the “rear” values are-1 and -1 respectively; and the queue has a null value of all us element. Every time we add on element to the queue the “rear” value increments by 1 till the time it reaches the upper limit of queue; after which it starts all over again from’0’ Similarly, every time we delete an element from queue, the “front” value increments by till the time it reaches the upper limit of queue. After which  it starts all over again from ‘0’.  

Program :

Implementation at circular Queue # include <stdio.h> # include <conio.h> # include <stdlib.h> # define max 5 Int rear = -1; Int front = -1; Int cq [max]; Void insertion() { Int item; If(( front == 0)&& (rear==max-1)||(front==rear +1)) { Print (“Queue is overflow \n”) } Else { Print (“enter the value”) Scanf(“%d”, & item); If(front ==-1); { Font =0; Rear =0; } Else { If(rear == max-1) { Rear=0; } Else { Rear = rear+1 Cq[rear] = item; } } Void deletion() Int item; If(front==-1) { Printf(“Queue is underflow \n”); } Else Item = cq[front]; Printf(“the deleted item is:%d,”item); Cq[front] =0; If(front== rear) { Front=-1; Rear= -1; } Else { If(front== max-1) { Front=0; } Else { Front= front+1; } } } void display () { int i; for(i=0; i<=max;i++) { printf(“%d”,cq[i]);} } } void main() { int op; clrscr(); printf(“1.insertion \n”); printf(“2. Deletion \n”); printf(“3. Display \n”) ; printf(“4. Exit \n”); do { printf(“Enter your option \n”); scanf(“%d”, &op); switch(op) { case 1: insertion (); break; case 2: Deletion (); break; case 3: display (); break; case 4: exit; break; } while(op<=4) } }  

1). Initial State:

2). After inserting element 10

3). After Inserting elements 20,30,40,50...

4). Inserting element 60

Circular Queue is overflow  

5). After deleting elements 10,20

7).After inserting element 60,70

8). After Deleting elements 30,40

9). After deleting 50

10).Ater deleting 60,70