Priority Queue Using Linked List in C

by

Posted on 18 December 2016

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 memory 
	temp->val=ele; //giving the new memory location value 
	temp->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("\n\tRemoved: %d",start->val);
	start = start->next;
	disp();
	}
	Else	//if no elements
	printf("\nError 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("\nPriority Queue: ");
	while(temp!=NULL)
	{
		printf("%d,%d ",temp->val, temp->pr);
		temp=temp->next;
	}
printf("\n");
}

 

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("\nPriority Queue: ");
	while(temp!=NULL)
	{
		printf("%d,%d ",temp->val, temp->pr);
		temp=temp->next;
	}
printf("\n");
}

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("\n\tRemoved: %d",start->val);
	start = start->next;
	disp();
	}
	else
	printf("\nError List Empty");
}


int main()
{
	int ch, ele, pr, check=1;
while(check==1)
{
	printf("\nIn Priority Queue Select:\n1. Insert\n2. Remove\n3. Exit\n");
	scanf("%d",&ch);
	switch(ch)
	{
		case 1:
			printf("\nEnter 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("\nPress 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.


If You Love this article, You Should Consider:

  • Like us on Facebook
  • Follow us on Instagram
  • Follow us on Twitter
  • Subscribe to our Newsletter.
  • Let us know your suggestions and queries in the comments below.

Thank you for your Love and Support

Share your thoughts

Search
Adverstisement
Adverstisement