# 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. ## 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. ## 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;
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 data5Enter your data and its priorities23 422 323 927 287 61 for Insert the Data in Queue2 for show the Data in Queue3 for Delete the data from the Queue0 for Exit3Deleted element:- 27 and Its Priority:- 21 for Insert the Data in Queue2 for show the Data in Queue3 for Delete the data from the Queue0 for Exit2Data = 22  Priority = 3Data = 23  Priority = 4Data = 87  Priority = 6Data = 23  Priority = 91 for Insert the Data in Queue2 for show the Data in Queue3 for Delete the data from the Queue0 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