Priority Queue - C/C++

A priority queue is different from a "normal" queue, because instead of being a "first-in-first-out" data structure, values come out in order by priority.
A priority queue might be used, for example, to handle the jobs sent to the Computer Science Department's printer: Jobs sent by the department chair should be printed first, then jobs sent by professors, then those sent by graduate students, and finally those sent by undergraduates. The values put into the priority queue would be the priority of the sender 
(e.g., using 4 for the chair, 3 for professors, 2 for grad students, and 1 for undergrads), and the associated information would be the document to print. Each time the printer is free, the job with the highest priority would be removed from the print queue, and printed. (Note that it is OK to have multiple jobs with the same priority; if there is more than one job with the samehighest priority when the printer is free, then any one of them can be selected.



Implementation of Priority Queue in C.


//priority queue
#include<stdio.h>
#include<conio.h>
struct q
{
 int info, prio;
 struct q *link;
}*front = NULL, *rear = NULL, *temp, *neww, *prev;
 
void insert();
void delet();
void display();
 
void main()
{
 char ch;
 int choice;
 do
 {
  clrscr();
  printf("\n1 -> Insert");
  printf("\n2 -> Delete");
  printf("\n3 -> Display");
  printf("\n0 -> Exit");
  printf("\n\nEnter Your Choice -> ");
  scanf("%d", &choice);
  switch (choice)
  {
  case 1:
   insert();
   break;
  case 2:
   delet();
   break;
  case 3:
   display();
   break;
  case 0:
   exit();
  default:
   printf("\n\nInvalid Choice");
  }
  printf("\n\nDo u Want to Continue -> ");
  ch = getche();
 } while (ch == 'y' || ch == 'Y');
}
 
void insert()
{
 int data, p;
 printf("\nEnter Q Element -> ");
 scanf("%d", &data);
 printf("\nEnter Priority  -> ");
 scanf("%d", &p);
 
 neww = (struct q *)malloc(sizeof(struct q));
 neww->info = data;
 neww->prio = p;
 neww->link = NULL;
 
 if (front == NULL)
 {
  front = rear = neww;
 }
 else
 {
  temp = front;
  while (temp->prio <= p && temp != NULL)
  {
   prev = temp;
   temp = temp->link;
  }
 
  if (prev == rear)
  {
   rear->link = neww;
   rear = neww;
  }
 
  else if (temp == front)
  {
   neww->link = front;
   front = neww;
  }
 
  else
  {
   neww->link = temp;
   prev->link = neww;
  }
 
  printf("\nElement Inserted Successfully");
 }
}
 
void delet()
{
 if (front == NULL)
 {
  printf("\n\nSorry! Q is Empty");
 }
 else
 {
  temp = front;
  front = front->link;
  free(temp);
  printf("\nElemnt Deleted Successfully");
 }
}
 
void display()
{
 if (front == NULL)
 {
  printf("\n\nSorry! Priority Q is Empty");
 }
 else
 {
  temp = front;
  printf("\n\nInfo\tPrio\n");
  while (temp != NULL)
  {
   printf("\n%d\t%d", temp->info, temp->prio);
   temp = temp->link;
  }
 }
}


Check out other methods of sorting in Data Structure :
1. Implementation of Insertion Sort in C
2. Implementation of Selection Sort in C
3. Implementation of Quick Sort in C
4. Implementation of Bubble Sort in C
5. Implementation of Heap sort in C
6. Implementation of Merge Sort in C
7. Implementation of Radix Sort in C

Post a Comment