Priority Queue Using Linked List in C

What is Priority Queue?

A priority queue is a data structure in which each element is assigned a priority. The priority of the element will be used to determine the order in which the elements will be processed.

Time Complexity — O(log n)
Lower the number, Higher the priority!

Priority Range:

  • 0 -Highest
  • 1 -High
  • 2 -Medium

So on..

The general rules of processing are

  • An element with higher priority is processed before an element with a lower priority.
  • Two elements with the same priority are processed on a first-come-first-served (FCFS) basis.

A priority queue can be thought of as a modified queue in which when an element has to be removed from the queue, the one with the highest priority is retrieved first. The priority of the element can be set based on various factors. Priority queues are widely used in operating systems to execute the highest priority process first.

When a Priority Queue is implemented using a linked list, then every node of the list will have three parts:

(a) the information or data part

(b) the priority number of the element, and

(c) the address of the next element.

If we are using a sorted linked list, then the element with the higher priority will come before the element with the lower priority. (for processing it before)

also, read:
Understanding the Concepts of Linked List-The Easy Way

C Program to Delete a Node from Linked List

C program to perform implementation of Linked List

Insertion

When a new element has to be inserted in a priority queue, we have to traverse the entire list until we find a node that has a priority lower than that of the new element. The new node is inserted before the node with the lower priority. However, if there exists an element that has the same priority as the new element, the new element is inserted after that element based on FCFS Rule.

void push(int ele,int pri) { struct node *temp, *t;//declaring pointer temp = (struct node *)malloc(sizeof(struct node)); //allocating new memorytemp->val=ele; //giving the new memory location valuetemp->pr=pri;  //assigning priority temp->next=NULL; //makes the address part NULL  if(start==NULL)  //check if it’s the first node in Queue start = temp; //make the new node as 1st node else if(start->pr>pri) { temp->next=start;start=temp; //printf("First Element Now is \%d \%d ",start->val,start->pr); } else { t=start; while(t->next!=NULL && (t->next)->pr<=pri ) t=t->next; temp->next=t->next; t->next=temp; } disp(); }

priority queue using linked list

Explanation:

  • If checks whether it’s the 1st element,
  • else if checks whether the priority of the first element is greater than the priority of the temp( a new element), if yes it means temp( a new element) will be inserted before the start.
  • else assigns the value of the 1st element to t for traversal in the Priority Queue until the list is empty or the priority of next element in PQ is less than the priority of temp. Now modify so addr of temp node points to addr of t, and addr of t points to temp.

Deletion

Deletion is a very simple process in this case. The first node of the list will be deleted and the data of that node will be processed first.

void del() { if(start!=NULL) //if elements are present { printf("\tRemoved: \%d",start->val); start = start->next; disp(); } Else//if no elements printf("Error List Empty"); } 

Display

Simply traverse from the first node and go up to the last node whose address part is NULL.

void disp() { struct node *temp; //declare temp to hold pointer of start temp = start; printf("Priority Queue: "); while(temp!=NULL) { printf("\%d,\%d ",temp->val, temp->pr); temp=temp->next; } printf(""); }

The Whole Program:

#include<stdio.h> #include<stdlib.h>  struct node { int val, pr; struct node *next; }*start;//start is declared  void push(int, int);//declaration of mmethod we are going to use void pop();//declaration  void disp() { struct node *temp; temp = start; printf("Priority Queue: "); while(temp!=NULL) { printf("\%d,\%d ",temp->val, temp->pr); temp=temp->next; } printf(""); }  void push(int ele,int pri) { struct node *temp, *t; temp = (struct node *)malloc(sizeof(struct node)); temp->val=ele; temp->pr=pri; temp->next=NULL;  if(start==NULL) start = temp; else if(start->pr>pri) { temp->next=start; start=temp; } else { t=start; while(t->next!=NULL && (t->next)->pr<=pri ) t=t->next; temp->next=t->next; t->next=temp; } disp(); }  void del() //remove elements { if(start!=NULL) { printf("\tRemoved: \%d",start->val); start = start->next; disp(); } else printf("Error List Empty"); }   int main() { int ch, ele, pr, check=1; while(check==1) { printf("In Priority Queue Select:1. Insert2. Remove3. Exit"); scanf("\%d",&ch); switch(ch) { case 1: printf("Enter element and its priority: "); scanf("\%d\%d",&ele,&pr); //input from user push(ele,pr);//Send Element and its priority for insertion break; case 2: del(); break; case 3: check=0; //Stops the loop break; default: printf("Wrong Choice"); printf("Press 1 to continue or 0 to stop"); scanf("\%d",&check); } } return 0; } //end of Main 

Output

priority queue using linked list in c

Thank you for reading

Tweet your queries and feedback to @PsychoCodes or leave a message on our Facebook page. You can also comment your questions below.

Also, don’t forget to subscribe to our Newsletter.

If you like this article, then please share it and help us grow.


Preorder and Postorder Traversal of binary tree in Python
02 September 2018

Binary Tree in Python
02 September 2018

Image Sharpening by High Pass Filter using Python and OpenCV
17 August 2018

Explaining Register variables in C with examples
17 August 2018

C program to generate all combinations of N-Bit Binary String
10 July 2018

Data Autosave System using PHP, MySQL and AJAX
06 July 2018

Понравилась статья? Поделиться с друзьями:
Добавить комментарий