CIRCULAR
QUEUE
As in a
circle after last element , first element occurs.
Here after
(n-1)th element, 0th element occurs. Similarly we take
assumptions that after last element of queue the 1st element will
occur.
Eg:
(a)Initial queue
5
|
10
|
15
|
0 1 2 3
Front=1; rear=3;
(b) Deletion
in queue
10
|
15
|
0
1 2 3
Front=2;
rear=3;
(c)
Addition in queue
20
|
10
|
15
|
0 1 2 3
Front=2;
rear=0;
(d)
Addition in queue
20
|
25
|
10
|
15
|
0 1 2 3
Front=2;
rear=1;
[overflow
condition]
(e)
Deletion in queue
20
|
25
|
15
|
0 1 2 3
Front=3;
rear=1;
(f)
Deletion in queue
20
|
25
|
0 1 2 3
Front=0;
rear=1;
(g)
Deletion in queue
25
|
0 1 2 3
Front=1;
rear=1;
(h)
Deletion in queue
0 1 2
3
Front=-1;
rear=-1;
[underflow
condition]
ALGORITHM
FOR ADDITION OPERATION IN CIRCULAR QUEUE:
STEP-1: If ((front==0 && rear==n-1)||(front==rear+1))
print queue overflow otherwise go to step-2.
STEP-1: If ((front==0 && rear==n-1)||(front==rear+1))
print queue overflow otherwise go to step-2.
STEP-2:
If (front==-1) then front=0; rear=0
otherwise go to step-3.
STEP-3: If (rear==n-1) then rear=0
STEP-4: rear++;
STEP-5: read the item to be deleted.
STEP-6: cq(rear)=item
STEP-7: return rear.
DELETE
OPERATION:
STEP-1: If (front==-1 && rear==-1)
print queue underflow and return front.
print queue underflow and return front.
STEP-2: read the item to be deleted then cq[front]=’\0’.
STEP-3: If (front==rear) then
front=-1,rear=-1.
STEP-4: If (front==n-1) then front=0 otherwise
go to step-4.
STEP-5: front++ and return front.
DISPLAY
OPERATION:
STEP-1: If((front==-1 && rear==-1)||(front>rear)).
print queue is empty otherwise go to step-2.
print queue is empty otherwise go to step-2.
STEP-2: print queue elements are from i=0 to
n.
STEP-3: print position of front and rear.
/* circular queue implementation using array */
import java.util.Scanner;
class rkcirqueue
{
static int i,n,item,front=-1,rear=-1,ch;
static Scanner cq=new Scanner(System.in);
public static void main(String[] args)
{
System.out.printf("\nEnter the length of the circular queue :\n");
n=cq.nextInt();
a=new int[n];
while(true)
{
System.out.printf("\n MENU \n\n");
System.out.printf(" 1.Add \n");
System.out.printf(" 2.Delete \n");
System.out.printf(" 3.Display \n");
System.out.printf(" 4.Quit \n");
System.out.printf("Enter u r choice: ");
ch=cq.nextInt();
switch(ch)
{
case 1:add();break;
case 2:del();break;
case 3:display();break;
case 4:System.exit(1);break;
default:
System.out.printf("u have entered wrong choice");break;
}
System.out.printf("\n");
}
}
static int add()
{
if((front==0 && rear==n-1)||(front==rear + 1))
{
System.out.printf("\n circular queue is overflow ");
return rear;
}
if(front==-1)
{
front=0;
rear=0;
}
else
{
if(rear==n-1)
rear=0;
else
rear++;
}
System.out.printf("\n enter item to be added on to the circular queue:");
item=cq.nextInt();
a[rear]=item;
return rear;
}
static int del()
{
if(front==-1 && rear==-1)
{
System.out.printf("\n circular queue is underflow ");
return rear;
}
System.out.printf("\n The deleted item = %d ",a[front]);
a[front]='\0';
if(front==rear)
{
front=-1;
rear=-1;
}
else
{
if(front==n-1)
front=0;
else
front++;
}
return front;
}
static int display()
{
if(front==-1 && rear==-1)
{
System.out.printf("\n circular queue is empty");
return rear;
}
System.out.printf("\ncircular queue elements are:");
for(i=0;i<=n-1;i++)
{
if(a[i]==0)
System.out.printf("\t");
else
System.out.printf("\t%d",a[i]);
}
System.out.printf("\n Position of Front=%d and Rear=%d",front,rear);
return rear;
}
}
No comments:
Post a Comment