In linear queue, since both rear and the front index-markers grows unidirectional, and the overflow condition becomes true immediately when the rear marker reaches the last element of the queue, but there could be vacant elements at the bottom of the queue if some retrieval would have taken place, further, the situation become worst when all elements of the queue would be retrieved, in such case both the underflow and the overflow would happen simultaneously and that is obviously absurd.

To do-away with such flaw of linear queue the conception of circular queue was proposed.

In a circular queue both the rear-index marker and the front-index marker moves circularly, that means when a marker reaches the last element it is taken back to the first element.

While implementing circular queue, we change the rear and front marker in the following way:

Q.rear=(Q.rear+1)%SIZE and

Q.front=(Q.front+1)%SIZE. So that the markers moves to the next element but except for one case, when the markers are at the last element of the QUEUE they are assigned to 0 by the above operation.

Queue q is an array of size=10 elements. rear is the poition/index of last inserted element intially rear =-1
front is the position/index of last retrived element intially front=0

Insert operation on queue
1.START Insert (Element e)
2.If (rear+1)%size :=front Then        ( If rear is the last element index)
3.Display “Queue OVERFLOW”
4.Goto END
5.END If
6.rear:=(rear+1)%size
7.q[rear]:=e
8.END Insert

Retrieve operation on queue
1.START Retrive()
2.If front=rear Then
3.Display “Queue UNDERFLOW”
4.GOTO END
5.END If
6.Element e:=q[front]
7.front:=(front+1)%size
8.Return e
9.END Retrieve

/*******************C IMPLEMENTATION OF CIRCULAR QUEUE********/

The code for implementing the Circular Queue : CircularQueue

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

#define size 6

int queue[size];
int front=size-1,rear=size-1;

void insert(int val)
{
if((rear+1)%size==front)
printf(“queue overflow\n”);
else
{
rear=(rear+1)%size;
queue[rear]=val;
printf(“the value is inserted\n”);
}
}

int retrive()
{
int value;

if(front==rear)
{
//printf(“queue underflow\n”);
return -9999;
}
else
{
front=(front+1)%size;
value= queue[front];
queue[front]=0;
return value;
}
}

void display()
{
int i;
for(i=0;i<=rear;i++)
{
printf(“%d\t”,queue[i]);

}
printf(“\n\n”);

}

void main()
{
int value,choice;
clrscr();
while(1)
{
printf(” press 1 for Insert\n press 2 for Retrive\n press 3 for diplay\n press 4 for exit\n\n”);
printf(“\nenter your choice:”);
scanf(“%d”,&choice);

switch(choice)
{
case 1:
printf(“enter the value which is to be inserted\n”);
scanf(“%d”,&value);
insert(value);
break;

case 2:
value= retrive();
if (value==-9999)
printf(“queue underflow\n\n\n”);
else
printf(“the retrive data is %d\n”,value);

break;

case 3:
display();
break;

case 4:
exit(0);
break;

default: printf(“invalid choice\n”);

}//end of switch
}//end of while

getch();
}

/***********C IMPLEMENTATION OF CIRCULAR QUEUE********/

Let us consider the following queue type.

type QUEUE is [

ELEMENT ITEM[SIZE]

INTEGER REAR

INTEGER FRONT

]

Let Q is a QUEUE of SIZE = 100 elements,

initially Q.REAR:= SIZE-1 and Q.FRONT:=SIZE-1

Insertion operation into a CIRCULAR QUEUE

1.START OPERATION INSERT (QUEUE S, ELEMENT e)

2.IF  (Q.REAR+1)%SIZE := Q.FRONT THEN

3.DISPLAY “QUEUE OVERFLOW”

4.GOTO END

5.END IF

6.  Q.REAR :=(Q.REAR + 1)%SIZE    //INCREMENT THE REAR OF THE QUEUE BY 1

7. Q.ITEM [Q.REAR] : = e  //ASSIGN THE ELEMENT AT THE TOP POSITION OF THE QUEUE

8.END OPERATION INSERT

Retrieve operation on CIRSULAR QUEUE

1.START OPERATION RETRIEVE (QUEUE Q)

2.IF Q.FRONT=Q.REAR THEN

3.DISPLAY “QUEUE UNDERFLOW”

4.GOTO END

5.END IF

6. Q.FRONT :=(Q.FRONT + 1)%SIZE

7. ELEMENT e:=Q.ITEM[Q.FRONT]

8.RETURN e

9.END OPERATION RETRIEVE

/***C IMPLEMENTATION OF CIRCULAR QUEUE Using Pointer ***/

The code for implementing the Circular Queue: CircularQueueUsingPointer

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

#define size 6

typedef struct
{
int item[size];
int front;
int rear;
}CirQueue;

void insert(CirQueue *cq,int val)
{
if((cq->rear+1)%size==cq->front)
printf(“queue overflow\n”);
else
{
cq->rear=(cq->rear+1)%size;
cq->item[cq->rear]=val;
printf(“the value is inserted\n”);
}
}

int retrive(CirQueue *cq)
{
int value;

if(cq->front==cq->rear)
{
//printf(“queue underflow\n”);
return -9999;
}
else
{
cq->front=(cq->front+1)%size;
value=cq->item[cq->front];
cq->item[cq->front]=0;
return value;
}
}

void display(CirQueue *cq)
{
int i;
for(i=0;i<=cq->rear;i++)
{
printf(“%d\t”,cq->item[i]);

}
printf(“\n\n”);
}

void main()
{
CirQueue cq;
int value,choice;
cq.front=size-1;
cq.rear=size-1;

clrscr();
while(1)
{
printf(” press 1 for Insert\n press 2 for Retrive\n press 3 for diplay\n press 4 for exit\n\n”);
printf(“\nenter your choice:”);
scanf(“%d”,&choice);

switch(choice)
{
case 1:
printf(“enter the value which is to be inserted\n”);
scanf(“%d”,&value);
insert(&cq,value);
break;

case 2:
value= retrive(&cq);
if (value==-9999)
printf(“queue underflow\n\n\n”);
else
printf(“the retrive data is %d\n”,value);

break;

case 3:
display(&cq);
break;

case 4:
exit(0);
break;

default: printf(“invalid choice\n”);

}//end of switch
}//end of while

getch();
}

/***C IMPLEMENTATION OF CIRCULAR QUEUE Using Pointer ***/

Advertisements