Home » Data Structure

Implementation of priority queue using linked list

In this article, we are going to learn how to implement a priority queue using C language with the linked list in the data structure? By Manu Jemini, on December 21, 2017

What is priority queue?

A priority queue is a very important data structure because it can store data in a very practical way. This is a concept of storing the item with its priority. This way we can prioritize our concept of a queue.

Image source: https://netmatze.files.wordpress.com/2014/08/priorityqueue.png

Code explanation to implementation of priority queue using linked list

In the Code below there are four parts. First three function to implement three different operations like Insert a node, delete a node and display the list. The Fourth part is the main function, in that a do while loop is implemented to keep the user engaged and provide him the all the given choices, according to the choice one of the three function get called.

The First function creates a new node and then checks whether the queue is empty or not. If the queue is empty it adds the node at the first place, else it reaches to the last position and adds the item there.

The Second function checks whether the list is empty, or it is not. If any node exists, it will delete the node.

The Third function will simply print all the elements of the Queue if exist. If not, then it will say Queue is Empty.

C program to implement priority queue

#include <malloc.h>
#include <stdio.h>

typedef struct node {
  int priority;
  int info;
  struct node *link;
} NODE;
NODE *front = NULL;

/*Begin of insert*/
void insert(int item, int priority) {
  NODE *tmp, *q;

  tmp = (NODE *)malloc(sizeof(NODE));
  tmp->info = item;
  tmp->priority = priority;
  /*Queue is empty or item to be added has priority more than first item*/
  if (front == NULL || priority < front->priority) {
    tmp->link = front;
    front = tmp;
  } else {
    q = front;
    while (q->link != NULL && q->link->priority <= priority) q = q->link;
    tmp->link = q->link;
    q->link = tmp;
  }
}
/*End of insert*/

/*Begin of del*/
void del() {
  NODE *tmp;
  if (front == NULL)
    printf("Queue Underflow\n");
  else {
    tmp = front;
    printf("Deleted item is %d\n", tmp->info);
    front = front->link;
    free(tmp);
  }
}
/*End of del*/

/*Begin of display*/
void display() {
  NODE *ptr;
  ptr = front;
  if (front == NULL)
    printf("Queue is empty\n");
  else {
    printf("Queue is :\n");
    printf("Priority       Item\n");
    while (ptr != NULL) {
      printf("%5d        %5d\n", ptr->priority, ptr->info);
      ptr = ptr->link;
    }
  }
}
/*End of display*/

/*Begin of main*/
int main() {
  int choice, item, priority;
  do {
    printf("1.Insert\n");
    printf("2.Delete\n");
    printf("3.Display\n");
    printf("4.Quit\n");
    printf("Enter your choice : ");
    scanf("%d", &choice);
    switch (choice) {
      case 1:
        printf("Input the item value to be added in the queue : ");
        scanf("%d", &item);
        printf("Enter its priority : ");
        scanf("%d", &priority);
        insert(item, priority);
        break;
      case 2:
        del();
        break;
      case 3:
        display();
        break;
      case 4:
        break;
      default:
        printf("Wrong choice\n");
    }
  } while (choice != 4);

  return 0;
}
/*End of main*/

Output