Priority Queues

Stack and queue are data structures whose elements are ordered based on the sequence in which they have been inserted. The pop operation retrieves the last element inserted, and the remove operation retrieves the first element inserted. If there is an intrinsic order among the elements themselves (for example, numeric order or alphabetic order), it is ignored in the stack or queue operations.

The priority queue is a data structure in which the intrinsic ordering of the elements does determine the result of its basic operations. There are two types of priority queues: an ascending priority queue and a descending priority queue. An ascending priority queue is a collection of items into which items can be inserted arbitrarily and from which only the smallest item can be removed. If apq is an ascending priority queue, the operation pqinsert(apq,x) inserts element x into apq and pqmindelete(apq) removes the minimum element from apq and returns its value.

A descending priority queue is similar but allows deletion of only the largest item. The operations applicable to a descending priority queue, dpq, are pqinsert(dpq,x) and pqmaxdelete(dpq). pqinsert(dpq,x) inserts an element x into dpq and is logically identical to pqinsert for an ascending priority queue. pqmaxdelete(dpq) removes the maximum element from dpq and returns its value.

The operation empty(pq) applies to both types of priority queue and determines whether a priority queue is empty. pqmindelete or pqmaxdelete can only be applied to a nonempty priority queue (that is, if empty(pq) is false).

Once pqmindelete has been applied to retrieve the smallest element of an ascending priority queue, it can be applied again to retrieve the next smallest, and so on. Thus the operations successively retrieve elements of a priority queue in ascending order. (However, if a small element is inserted after several deletions, the next retrieval will return that small element, which may be smaller than a previously retrieved element.) Similarly, pqmaxdelete retrieves elements of a descending priority queue in descending order. This explains the designation of a priority queue as either ascending or descending.

The elements of a priority queue need not be numbers or characters that can be compared directly. They may be complex structures that are ordered on one or several fields. For example, telephone-book listings consist of last names, first names, addresses, and phone numbers and are ordered by last name.

Sometimes the field on which the elements of a priority queue are ordered is not even part of the elements themselves; it may be a special, external value used specifically for the purpose of ordering the priority queue. For example, a stack may be viewed as a descending priority queue whose elements are ordered by time of insertion. The element that was inserted last has the greatest insertion time value and is the only item that can be retrieved. A queue may similarly be viewed as an ascending priority queue whose elements are ordered by time of insertion. In both cases the time of insertion is not part of the elements themselves but is used to order the priority queue.

C++ Implementation: Program of priority queue using linked list.

#include<iostream.h> #include<process.h> #include<conio.h> struct node {      int priority;      int info;      struct node *link; }*front = NULL; void insert(); void del(); void display(); void main() {      cout<<"Program of priority queue using linked list";      int choice;      while(1)      {         getch();         clrscr();         cout<<"1.Insertn";         cout<<"2.Deleten";         cout<<"3.Displayn";         cout<<"4.Quitn";         cout<<"Enter your choice : ";         cin>>choice;      switch(choice)      {         case 1:            insert();            break;         case 2:            del();            break;         case 3:            display();            break;         case 4:            exit(1);         default :         cout<<"Wrong choicen"; } } }/*End of main()*/ void insert() {      node *tmp,*q;      int added_item,item_priority;      tmp = new node;      cout<<"Input the item value to be added in the queue : ";      cin>>added_item;      cout<<"Enter its priority : ";      cin>>item_priority;      tmp->info = added_item;      tmp->priority = item_priority;      /*Queue is empty or item to be added has priority more than first item*/      if( front == NULL || item_priority < front->priority )      {      tmp->link = front;      front = tmp;      }      else      {      q = front;      while( q->link != NULL && q->link->priority <= item_priority )      q=q->link;      tmp->link = q->link;      q->link = tmp;      } }/*End of insert()*/ void del() {      node *tmp;      if(front == NULL)         cout<<"Queue Underflown";      else      {         tmp = front;         cout<<"Deleted item is "<<tmp->info;         front = front->link;         delete tmp;      } }/*End of del()*/ void display() {      node *ptr;      ptr = front;      if(front == NULL)         cout<<"Queue is emptyn";      else      {         cout<<"Queue is :n";         cout<<"Priority Itemn";         while(ptr != NULL)         {            cout<<"tt"<<ptr->priority;            cout<<"-"<<ptr->info;            ptr = ptr->link;         }      } }/*End of display() */

Output: