LINEAR QUEUE:
As the name implies we can see the example of
queue in daily life as queue of people, queue of cars, etc.
Queue is an ordered list of elements in which we
can add elements only at one end called the rear of the queue and
delete elements only at the other end called the front of the
queue. So queue is also called FIFO data structure.
Eg: qa[5]
Front =-1
Rear=-1
0 1 2 3 4
(a)empty queue
5
|
Front=0
Rear=0
0 1 2 3 4
(b) adding an element in
queue
5
|
10
|
Front=0
Rear=1
0 1 2 3 4
(c) adding an element in
queue
5
|
10
|
12
|
Front=0
Rear=2
0 1
2 3 4
(d) adding an element in queue
10
|
12
|
Front=1
Rear=2
0
1 2 3
4
(e) deleting an
element from queue
Front=1
10
|
12
|
16
|
Rear=3
0 1 2 3 4
(f) adding an
element in queue
ARRAY IMPLEMENTATION
OF QUEUE:
As stack, queue is also the
collection of same type of elements. Since we want to add an item in queue at
the rear end and delete the item in the queue at the front we take two
variables rear( keeps the status of last added item in queue) and front(keeps
the status of first item of queue).
It may be possible that condition arises
when there is no place for adding elements in queue. This is called overflow,
so first we check the value of rear with size of array.
If there is no element in queue then
value of front and rear will be -1(or) front will be greater than [5>4]
rear, so we check other condition before deleting the element of the queue.
Qa[7]=
|
|
5
|
10
|
15
|
20
|
|
|
0 1 2 3 4 5 6
Front=1
Rear=4
Here queue is
implemented with array-queue array size of queue is 7. The value of the front
is 1 means element will be deleted from the 1st position of queue
array, value of the rear is 4 means the element will be added at the 5th
position of queue-array. The elements of the queue are
qa[1]=5 qa[2]=10
qa[3]=15 qa[4]=20
import java.util.Scanner;
class rkqueue
{
static int[] a;
static int i,n,item,front=-1,rear=-1,ch;
static Scanner q=new Scanner(System.in);
public static void main(String xp[])
{
System.out.printf("\nEnter the length of the queue :\n");
n=q.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 ur choice: ");
ch=q.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(rear==n-1)
{
System.out.printf("\n queue overflow");
return rear;
}
else
{
if(front == -1)
{
front=0;
}
rear++;
System.out.printf("\n enter item to be added on to the queue:");
item=q.nextInt();
a[rear]=item;
return rear;
}
}
static int del()
{
if(front==-1 || front>rear)
{
System.out.printf("\n queue underflow");
return front;
}
else
{
System.out.printf("\n deleted item from queue is %d",a[front]);
a[front]='\0';
if(front==rear)
{
front=-1;
rear=-1;
}
front++;
return front;
}
}
static void display()
{
if((front==-1 && rear==-1) || (front>rear))
{
System.out.printf("\n queue is empty");
}
else
{
System.out.printf("\nqueue elements are:");
for(i=0;i<n;i++)
{
if(a[i]=='\0')
System.out.printf("\t");
else
System.out.printf("%d\t",a[i]);
}
System.out.printf("\n\n position of front %d and rear %d",front,rear);
}
}
}
No comments:
Post a Comment