Priority Queue
ØA Priority Queue is a collection of elements
such that each element has been assigned a
priority and such that the order in which elements
are processed comes from the following rules:
   oAn element of higher priority is processed before
         any element of lower priority.
   oTwo elements with the same priority are
         processed according to the order in which they
         were added to the queue.


Example
ØTime sharing systems: Programs of high priority are processed first.
         One-way list Representation of  Priority queues
ØEach node in the list contains three types of
information fields (Information INFO, Priority
Number PRN, and a link LINK).
ØA node X precedes a node Y in the list when:
      oX has higher priority than Y.
      oBoth X and Y have same priority but X was added before Y.
Deletion in a Priority Queue
1.Set ITEM = INFO [START].
2.Delete First node from the list.
3.Process ITEM.
4.Exit.
Insertion in a Priority Queue
1.Traverse the One-Way list until finding a node X
whose priority number exceeds N.
2.Insert ITEM in front of node X.
3.If no such node is found, insert the ITEM as the last
element of the list.
4.Exit.
    Array Representation of Priority Queues
ØUse a separate queue for each level of priority (for
each priority number).
ØEach such queue will appear in its own circular array
and have its own pointers FRONT and REAR.

Deletion in a Priority Queue
ØDelete and process the first element in a priority
queue maintained by a two-dimensional
array QUEUE.

1.[Find the first non-empty queue.]
Find the smallest K such that FRONT [K] ≠ NULL.

2.Delete and process the front element in row K of QUEUE.

3.Exit.
Insertion in a Priority Queue
ØInsert an ITEM with priority number M to a
priority queue maintained by a two
dimensional array QUEUE.
1.Insert ITEM as the REAR element in row K of
QUEUE.
2.Exit.

Code to implement priority Queue

  #include<iostream>
 using namespace std;
struct node{
int info;
int priority;
node *link;
}*front=NULL,*rear=NULL;
int emptyQueue()
{
if(front==NULL)
{
return 1;
}
else {
return 0;
}
}
int size()
{
int count=0;
node *ptr=front;
while(ptr!=NULL)
{
++count;
ptr=ptr->link;
        }
return count;
}
void Display()
{
node *ptr=front;
cout<<"\nPrority\tData";
while(ptr!=NULL)
{
cout<<endl<<ptr->priority<<"\t"<<ptr->info<<"\n";
ptr=ptr->link;
}
}
void insert(int item,int p)      //item will be stored as it is theuser is inserting
{
node *ptr=new node;
ptr->info=item;
ptr->link=NULL;
ptr->priority=p;
if(front==NULL)
       {
front=rear=ptr;
}
else
{
rear->link=ptr;
rear=ptr;
}
rear->info=item;
}
int delete1()                              //item will be deleted as per the priority 
{
if(!emptyQueue())
{
int p=front->priority;
    node *ptr=front->link;
    node *ptr1=front;
    while(ptr!=NULL)
    {
    if(p<=ptr->priority)
    {
        ptr=ptr->link;
    }
    else
    {
    p=ptr->priority;
    ptr-ptr->link;
    } 
}
ptr=front;
while(ptr!=NULL)
{
if(front->priority==p)
{
int item=front->info;
front=front->link;
        return item;
}
else if(ptr->priority==p)
{
int item=ptr->info;
        ptr1->link=ptr->link;
       return item;
}
else
{
ptr1=ptr;
ptr=ptr->link;
}
}
}
else
{
return 0;
}
}
int main()
{
int n,item,prior;
while(1)
{
cout<<"\n1. For Insert\n2. Delete\n3. Total Elements\n4. Display\n5. Exit";
    cout<<"\nEnter Your Choice ";
    cin>>n;
 switch(n)
    {
     case 1:
     cout<<"\nEnter the priority";
     cin>>prior;
     cout<<"\nEnter the value to be entered";
     cin>>item;
     insert(item,prior);
     break;
     case 2:
     item=delete1();
     if(item!=0)
     {
     cout<<"\ndeleted item is "<<item;

}
else
{
cout<<"\nQueue is Empty";
}
break;
case 3:
item=size();
if(item!=0)
{
cout<<"Total Elements is queue is "<<item;
}
else
{
cout<<"Queue is empty";
}
break;
case 4:
Display();
break;
case 5:
exit(0);
}
}
return 0;
       }