Priority Queue
In priority queue insertion takes place from any end.It is same as simple queue.
# Director (Higher priority)
# Branch Manager
# Manager
# Clerk
# Clerk
Those item which have same priority than we use FCFS (First Come First Serve).
Here insertion process is same as simple queue.
INSERTION:
Insertion takes place as simple queue. So same procedure is apply for priority queue as in simple queue.
DELETION:
Procedure For Deletion:
int delete_pq()
{
int x=0,big,pos,temp;
if(F==-1)
{
printf("Queue underflow\n");
}
else
{
if(F==R)
{
x=queue[F];
F=-1;
R=-1;
}
else
{
big=queue[F];
pos=F;
for(int i=F+1;i<=R;i++)
{
if(big<queue[i])
{
big=queue[i];
pos=i;
}
}
temp=queue[F];
queue[F]=queue[pos];
queue[pos]=temp;
x=queue[F];
F++;
}
}
return(x);
}
Explanation:
Suppose we have queue of 5 elements i.e size=5 , R=4 & F=0
Here 23 is highest element , so it has highest priority that means 23 will delete first. So for deleting 23 we first swap with 10 or 0th element.
First control comes in the first condition i.e if (F==-1) which is false (because F=0), than control comes in else part and check if (F==R) which false (because F=0 & R=4), than control comes in next condition i.e big = queue[F] , here Big=10 & pos(position) = 0.
Than we apply a for loop which is (i = F+1; i<=R ; i++)
i=F+1=1
Condition if ( big < queue[ i ] ) i.e 10 < 7 :False
than Big=10
i++ , pos=0
i = 2
Condition if ( big < queue[ i ] ) i.e 10 < 21 :True
than Big=21
i++ , pos=1
i=3
Condition if ( big < queue[ i ] ) i.e 21 < 23 :True
than Big=23
i++ , pos=2
i=4
Condition if ( big < queue[ i ] ) i.e 23 < 8 :True
than Big=23
i++, pos=3
Than perform swapping between Big and queue[pos] i.e queue[F]=queue[pos] , after swapping elements are
Now we delete 23
i.e x=queue[F];
F++;
Now F point to 1st location
In the same way we perform deletion on remaining elements.
Complete Program for Inserting & Deleting element in Priority Queue.
#include <stdio.h>
#include <conio.h>
#define size 50
int queue[size];
int R=-1,F=-1;
void insert_pq(int x)
{
if(R==size-1)
{
printf("Queue overflow");
}
else
{
if(R==-1)
{
R=0;
F=0;
queue[R]=x;
}
else
{
R++;
queue[R]=x;
}
}
//printf("Queue:%d",queue[R]);
}
void display()
{
if(R==-1 && F==-1)
{
printf("Now Queue is empty!\n");
}
else
{
printf("Elements of queue are:");
for(int i=F;i<=R;i++)
{
printf("|%d|",queue[i]);
}
}
}
int delete_pq()
{
int x=0,big,pos,temp;
if(F==-1)
{
printf("Queue underflow\n");
}
else
{
if(F==R)
{
x=queue[F];
F=-1;
R=-1;
}
else
{
big=queue[F];
pos=F;
for(int i=F+1;i<=R;i++)
{
if(big<queue[i])
{
big=queue[i];
pos=i;
}
}
temp=queue[F];
queue[F]=queue[pos];
queue[pos]=temp;
x=queue[F];
F++;
}
}
return(x);
}
void main()
{
int x,ch=1;
do{
if(ch==1)
{
printf("Enter Element of Priority Queue:");
scanf("%d",&x);
insert_pq(x);
display();
printf("\n");
}
printf("Do you want to insert element in Preority Queue:0-Exit, 1-Insert, 2-Delete:");
scanf("%d",&ch);
if(ch==2)
{
int d=delete_pq();
printf("%d is deleted element\n",d);
display();
printf("\n");
}
}while(ch!=0);
getch();
}
OUT PUT :
No comments:
Post a Comment