What is a Priority Queue and how to implement Priority Queue in C Programming?
A priority queue is a special type of queue in which
- Each element is associated with a priority value. And, elements are inserted on the basis of their priority. That is, higher priority elements are served first.
- An element with high priority is dequeued before an element with low priority.
- However, if elements with the same priority occur, they are served according to their order in the queue.
The real-world example of a priority queue would be a line in a bank where there is a special privilege for disabled and old people. The disabled people have the highest priority followed by elderly people and the normal person has the lowest priority.
Types of Priority Queue:
- Min Priority Queue: In the min priority Queue a minimum number of values gets the highest priority and the lowest number of elements gets the highest priority.
- Max Priority Queue: Max priority Queue is the opposite of min priority Queue in it maximum number value gets the highest priority and a minimum number of value gets the minimum priority.
Operations on queue:-
1.EnQueue (Insert): EnQueue operation inserts an item into the queue. The item can be inserted at the end of the queue or at the front of the queue or at the middle based on the priority value.
2.DeQueue (Delete): DeQueue operation deletes the item with the highest priority from the queue
How to implement a priority queue?
Insertion
- Ask the data and its priority from the user.
- If start is equal to null then Queue is empty create node and make node as the front of the queue.
- Else if the front is not equal to null then iterate over the queue till its reaches the node with priority less than the new node.
- Insert the data in the queue before at the position where newnode priority is greater than the priority of the element in the queue.
Deletion
- Remove the element and the priority from the front of the queue.
- Make start pointer pointing to next address of the front node.
- Using loop takes the starting point from the front of the queue and iterates over all the nodes.
CODE:
#include<stdio.h>
#include<stdlib.h>
struct node
{
int info,priority; // each node in queue has info and priority of node.
struct node *next; // also Node will keep track of address of next node.
}; //end of structure
struct node *start=NULL; // initialisation
// function to add node in queue according to priority
void insert(int x,int n)
{
struct node *p,*prev;
struct node *newnode;
newnode=(struct node *)malloc(sizeof(struct node)); // This will create node in Dynamic manner.
prev=(struct node *)malloc(sizeof(struct node));
newnode->info=x;// store given input info in new node
newnode->priority=n;// store priority of node
newnode->next=NULL; // store address of next node
//Base Condition
// Checks if Queue is Empty If it is Then It will allot Newnode as Start/First Node
if(start==NULL)
start=newnode;
//Check if Incoming Node Priority is lower than start Node
else if(newnode->priority>start->priority)
{
prev=start;// this will store start node to temporary Node Called as Prev
p=start;
// iterate over nodes till it finds node with less priority
while(p!=NULL && p->priority<=newnode->priority)
{
prev=p;
p=p->next;
}
newnode->next=p;
prev->next=newnode;
}//End of else if
// if incoming Node has highest priority then Make as Start Node and Start Node as Next Node
else
{
newnode->next=start;
start=newnode;
}
} //end of insert
// function to delete to Node From Queue
void delete()
{
//Base Condition
// Checks if Queue is Already Empty
struct node *p;
if(start==NULL)
printf("List is Empty\n");
// delete first Node
else
{
p=start;
start=start->next;
printf("The deleted node is %d\n",p->info);
free(p);
}
} //end of delete
void display()
{
struct node *p;
//Base Condition
// Checks if Queue is Already Empty
if(start==NULL)
printf("List is Empty\n");
// iterate over all node and simultaneously print its data
else
{
p=start;
printf("The elements in the link list are\n");
printf("PRIORITY INFO\n");
while(p!=NULL)
{
printf("%d %d\n",p->priority,p->info);
p=p->next;
}//end of while
}//end of else
} //end of display
// Utility Function
void main()
{
struct node *p;
int x,choice,n;
// User Choice
while(1)
{
printf("Enter your choice:\n1.insert as per priority\n2.delete \n3.display\n4.exit\n");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("Enter value to be entered into queue :");
scanf("%d",&x);
printf("Enter priority of the node :");
scanf("%d",&n);
insert(x,n);
break;
case 2:
delete();
break;
case 3:
display();
break;
case 4:
printf("Thank you\n");
exit(0);
default:
printf("Invalid input\n");
}//end of switch
} //end of while
}
/*
Enter your choice:
1.insert as per priority
2.delete
3.display
4.exit
1
Enter value to be entered into queue :12
Enter priority of the node :12
Enter your choice:
1.insert as per priority
2.delete
3.display
4.exit
1
Enter value to be entered into queue :23
Enter priority of the node :233
Enter your choice:
1.insert as per priority
2.delete
3.display
4.exit
1
Enter value to be entered into queue :1
Enter priority of the node :1
Enter your choice:
1.insert as per priority
2.delete
3.display
4.exit
2
The deleted node is 1
Enter your choice:
1.insert as per priority
2.delete
3.display
4.exit
1
Enter value to be entered into queue :1
Enter priority of the node :1
Enter your choice:
1.insert as per priority
2.delete
3.display
4.exit
3
The elements in the link list are
PRIORITY INFO
1 1
12 12
233 23
Enter your choice:
1.insert as per priority
2.delete
3.display
4.exit
*/
OUTPUT :
Hope this blog was informative and you might have learnt it “How to Implement Priority Queue in C Programming”. If you need any Programming and Coding help you can contact us now.
