Priority Queue

Algorithm : Priority  Queue  Operations

Let us consider a queue structure,”PQ” of size N,with front and rear called Priority  Queue
which has two part-i)element part and ii)priority part.Here,each element in the queue is
assigned a value called priority of that element,and an element can be inserted not only
the ends but at any position of that queue maintaining the priority.
This algorithm helps to perform Priority Queue operations.

PQinsert(PQ)
{
 if(rear=N)           //checks if rear reaches to the last position
 {
  Printf  "Queue full"
 }
 else
 {
  rear=rear+1                    //rear is incremented by 1
  Q[rear].element=PQ.element
  Q[rear].pr=PQ.pr
  if(front=-1)         //if no elements in PQ is inserted then front
  {                      and rear both are initialized to 0
   front=rear=0
  }
 }
                       Sort elements of “PQ” in descending order of their priority.
}

PQdelete(PQ)
{
 if(front=-1)              //checks if there is no element in PQ
 {
  Printf  "Queue empty"
 }
 else
 {
   PQ.element=Q[front].element
   PQ.pr=Q[front].pr
  if(front=rear)       //if there is only 1 element in PQ then front
  {                      and rear both are initialized to -1
   front=rear=-1
  }
  else
  {
   front=front+1           //front is incremented by 1
  }
 }
 return PQ
}

C Program For priority queue

Source Code:


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

struct queue
{
 int element;
 int pr;
};

struct queue Q[5];

int f=-1,r=-1;

void PQinsert(struct queue PQ)
{
 int i,j,x,y;
 if(r==4)
 {
  printf("\nQueue full.");
 }
 else
 {
  r=r+1;
  Q[r].element=PQ.element;
  Q[r].pr=PQ.pr;
  if(f==-1)
  {
   f=0;
   r=0;
  }
 }
  for(i=f;i<=r-1;i++)
  {
   for(j=i+1;j<=r;j++)
   {
       if(Q[i].pr>Q[j].pr)
       {
	  x=Q[i].element;
	  y=Q[i].pr;
	  Q[i].element=Q[j].element;
	  Q[i].pr=Q[j].pr;
	  Q[j].element=x;
	  Q[j].pr=y;
       }
    }
  }
}

struct queue PQdelete()
{
 int k,i,j,s,m;
 struct queue PQ;
 if(f==-1)
 {
  printf("\nQueue empty.");
 }
 else
 {
   PQ.element=Q[f].element;
   PQ.pr=Q[f].pr;
  if(f==r)
  {
   f=-1;
   r=-1;
  }
  else
  {
   f=f+1;
  }
 }
 return PQ;
}

void show()
{
 int i=0;
 if(f==-1)
 {
   printf("\nQueue empty.");
 }
 else
 {
 printf("\nThe elements of the Queue are:");
  for(i=0;i<=4;i++)
  {
   if(i>=f && i<=r)
     printf("  %d(p->%d)",Q[i].element,Q[i].pr);
   else
     printf("  _");
  }
  printf("\n");
 }
}

void main()
{
 int ch;
 struct queue PQ;
 while(1)
 {
   printf("\n1.PQinsert  2.PQdelete  3.Show  4.Exit");
   printf("\nEnter your choice:");
   scanf("%d",&ch);
   switch(ch)
   {
     case 1:
	    printf("\nEnter element and priority:");
	    scanf("%d,%d",&PQ.element,&PQ.pr);
	    PQinsert(PQ);
	    break;
     case 2:
	    PQ=PQdelete();
	    if(f!=-1)
	    {
	    printf("\nThe popped item is->  %d(p->%d)\n",PQ.element,PQ.pr);
	    }
	    break;
     case 3:
	    show();
	    break;
    
     case 4:
	    exit(0);

   }
 }
}



 OUTPUT :
 1.PQinsert  2.PQdelete  3.Show  4.Exit
Enter your choice:1

Enter element and priority:22,4

1.PQinsert  2.PQdelete  3.Show  4.Exit
Enter your choice:1

Enter element and priority:12,1

1.PQinsert  2.PQdelete  3.Show  4.Exit
Enter your choice:3

The elements of the Queue are:  12(p->1)  22(p->4)  _  _  _

1.PQinsert  2.PQdelete  3.Show  4.Exit
Enter your choice:1

Enter element and priority:45,3

1.PQinsert  2.PQdelete  3.Show  4.Exit
Enter your choice:1

Enter element and priority:67,2

1.PQinsert  2.PQdelete  3.Show  4.Exit
Enter your choice:3

The elements of the Queue are:  12(p->1)  67(p->2)  45(p->3)  22(p->4)  _

1.PQinsert  2.PQdelete  3.Show  4.Exit
Enter your choice:1

Enter element and priority:66,5

1.PQinsert  2.PQdelete  3.Show  4.Exit
Enter your choice:3

The elements of the Queue are:  12(p->1)  67(p->2)  45(p->3)  22(p->4)  66(p->5)

1.PQinsert  2.PQdelete  3.Show  4.Exit
Enter your choice:1

Enter element and priority:99,6

Queue full.

1.PQinsert  2.PQdelete  3.Show  4.Exit
Enter your choice:2

The popped item is->  12(p->1)

1.PQinsert  2.PQdelete  3.Show  4.Exit
Enter your choice:2

The popped item is->  67(p->2)

1.PQinsert  2.PQdelete  3.Show  4.Exit
Enter your choice:3

The elements of the Queue are:  _  _  45(p->3)  22(p->4)  66(p->5)

1.PQinsert  2.PQdelete  3.Show  4.Exit
Enter your choice:2

The popped item is->  45(p->3)

1.PQinsert  2.PQdelete  3.Show  4.Exit
Enter your choice:2

The popped item is->  22(p->4)

1.PQinsert  2.PQdelete  3.Show  4.Exit
Enter your choice:2

1.PQinsert  2.PQdelete  3.Show  4.Exit
Enter your choice:2

Queue empty.