Implementation of Priority Queue using Linked List in C

Implementation of Priority Queue using Linked List

Implementation of priority Queue data structure by using linked list is efficient as compare to using arrays.

Linked list provide you the facility of Dynamic memory allocation.If we use Linked List for implementing Priority Queue then memory is not going to waste. We can free the memory which is not in use anymore.

This is the main advantage of using linked list over array to implement Queue.

Priority Queue using Linked list

Steps for Implementing Priority Queue using Linked List in C

enqueue(data)

  • In Enqueue function we will create a node and assign the data and priority in it.
  • Then we will check if front is null then we assign the new node address to front.
  • If front is pointing to some node then we traverse the linked list using temporary pointer till new node priority is highest to the priority of the data in linked list and there is not null.
  • Address of new node initialize to the temporary node and address of temporary next node assign to the new node link.

dequeue()

  • Check if queue is empty or not.
  • If queue is empty then dequeue is not possible.
  • Else store front in temp.
  • Print data of temp.
  • Free temp memory.
  • And make next of front as front.

print()

  • Check if there is some data in the queue or not.
  • If the queue is empty print “No data in the queue.”
  • Else define a node pointer and initialize it with front.
  • Print data of node pointer until the next of node pointer becomes NULL.
Priority queue using linked list in C

Algorithm for Implementing Priority Queue using linked list in C

enqueue(int d)

  1. Create a new node of structure node type.
  2. new_node->data = entered data.
  3. new_node->Priority = priority.
  4. IF(Front == NULL)||(Entered priorityPriority).
  5. new_node->next = Front.
  6. Front = new_node.
  7. End IF.
  8. ELSE
  9. Temp = Front 
  10. WHILE((Temp->next!=NULL)&&(Temp->Priority<=Entered Priority)
  11. Temp =  Temp->next
  12. new_node->next = temp->next
  13. temp->next = new_node
  14. End ELSE

dequeue()

  1. Create a temporary pointer temp  of node structure type
  2. IF(Front == NULL)
  3. Print  ‘Underflow Condition’
  4. End IF
  5. ELSE
  6. Temp = Front
  7. Front = Front->Next
  8. Print(data and priority)
  9. Free(temp)
  10. End ELSE

print()

  • STRUCT NODE* TEMP
  • IF((FRONT == NULL)&&(REAR == NULL))
  • RETURN
  • ELSE
  • TEMP = FRONT
  • WHILE(TEMP)
  • RETURN TEMP->DATA
  • TEMP = TEMP->NEXT

C Program to Implement Priority Queue using Linked list

#include<stdio.h>
#include<stdlib.h>
struct node
{
	int data,p;
	struct node* next;
};
struct node* f = NULL;
struct node* r = NULL;

void enqueue(int d,int pr) //Insert the element and priority in Queue
{ 	struct node* temp;
	struct node* new_n;
	new_n = (struct node*)malloc(sizeof(struct node));
	new_n->data = d;
	new_n->p = pr;

	if((f==NULL)||(prp)) 
	{
		new_n->next = f;
		f = new_n;
	}
	else
	{
		temp = f;
		while((temp->next != NULL)&&((temp->next->p) <= pr)) temp = temp->next;
		new_n->next = temp->next;
		temp->next = new_n;

	}
}
void print() //Print the data of Queue
{
	struct node* temp = f;
	while(temp != NULL) 
	{ 
		printf("\nData = %d\tPriority = %d ",temp->data,temp->p);	 
		temp = temp->next; 
	} 

}
void dequeue() //Deletion of highest priority element from the Queue
{
	struct node* temp;
	if(f==NULL) //Check for Underflow condition
		printf("\nQueue is Empty");
	else
	{
		temp = f;
		f = f->next;
		printf("\nDeleted element:- %d\t and Its Priority:- %d",temp->data,temp->p);
		free(temp);
	}
}
int main()
{
	int opt,n,i,data,pr;
	printf("Enter Your Choice:-");
	do{
		printf("\n\n1 for Insert the Data in Queue\n2 for show the Data in Queue \n3 for Delete the data from the Queue\n0 for Exit");
		scanf("%d",&opt);
		switch(opt){
			case 1:
				printf("\nEnter the number of data");
				scanf("%d",&n);
				printf("\nEnter your data and its priorities");
				i=0;
				while(i<n){
					scanf("%d %d",&data,&pr);
					enqueue(data,pr);
					i++;
				}
				break;
			case 2:
				print();
				break;
			case 3:
				 dequeue();
				break;
			case 0:
				break;
			default:
				printf("\nIncorrect Choice");

		}
	}while(opt!=0);
return 0;
}
Enter the number of data
5

Enter your data and its priorities

23 4
22 3
23 9
27 2
87 6

1 for Insert the Data in Queue
2 for show the Data in Queue
3 for Delete the data from the Queue
0 for Exit

3

Deleted element:- 27 and Its Priority:- 2

1 for Insert the Data in Queue
2 for show the Data in Queue
3 for Delete the data from the Queue
0 for Exit

2

Data = 22  Priority = 3
Data = 23  Priority = 4
Data = 87  Priority = 6
Data = 23  Priority = 9

1 for Insert the Data in Queue
2 for show the Data in Queue
3 for Delete the data from the Queue
0 for Exit

Queue using Array

Here we have already learned implementation of Priority Queue using Linked List in C , click the button below to learn the implementation of queue using array