Priority Queue data structure is a queue where each element is associated with priority with it.

What is the Priority Queue Data Structure?

Priority queue is an abstract data type which is similar to the queue data structure.
There are queues in which we can insert items or delete items from any position based on some priority. The elements are inserted at any time and while removing element the priority is checked.

Priority Queue Definition
A queue based on the properties of priority of a task to be processed is referred to as a Priority Queue.

In computer system jobs are assigned some priority, according to the priority of the job it is inserted at the end of the queue with that same priority.

Priority queue example

The figure shows that N jobs are with some priority. These jobs are executed or processed by considering some priority in the queue.

Priority Queue Data Structure
Priority Queue Data Structure

The priority queue follows FIFO (First in first out) behavior.

Operations on Priority Queue

1. Enqueue: To insert elements in the queue.
2. Dequeue: To remove elements from queue
3. Check Priority: To check the priority of element while dequeuing element.

How does Priority Queue work?

The priority queue is similar to queue except for Dequeue of an element.
1. Every element is stored with its priority.
2. Elements are dequeued based on priority. The high priority element is removed before the low priority element.
3. If the queue contains elements with the same priority then element is removed in order.

Priority queue algorithm

  1. Declare structure for queue.
  2. Write a function to insert data.
  3. Next function to delete data.
  4. Write display function.
  5. Call functions from queue

Priority queue program in c

#include<stdio.h>
#include<conio.h>
#include<malloc.h>

typedef struct node{
int pri;
int data;
struct node *next;
}NODE;

NODE *front=NULL;

// Insert in the priority queue

void insert(int data,int pri)

{

NODE *temp,*q;

temp=(NODE *)malloc (sizeof(NODE));

temp->data=data;

temp->pri=pri;

//check if queue is empty else not check priority of data.

if(front==NULL || pri < front->pri)

{

temp->next =front;

front = temp;

}

else{

q= front;

while(q->next != NULL && q->next->pri <= pri)

q=q->next;

temp->next= q->next;

q->next =temp;

}

}

//Delete in the priority queue.

void del(){

NODE *temp;

if(front == NULL)

printf("Queue is empty :");

else

{

temp=front;

printf("Deleted data is :%d ",temp->data);

front = front -> next;

free(temp);

}

}

//display the priority queue.

void display(){

NODE *temp;

temp=front;

if(front==NULL)

printf("Queue is empty:");

else

{

printf("\nOur priority queue is:");

printf("\nPriority Data\n");

while(temp!=NULL)

{

printf("%d %d\n",temp->pri,temp->data);

temp=temp->next;

}

}

}

//Start with main function

int main()

{

int ch,data,pri;

do{

printf("1.Insert\n");

printf("2.Delete\n");

printf("3.Display\n");

printf("4.Exit\n");

printf("Enter choice\n");

scanf("%d",&ch);

switch(ch)

{

case 1:

printf("Enter the data:\n");

scanf("%d",&data);

printf("Enter priority:");

scanf("%d",&pri);

insert(data,pri);

break;

case 2:

del();

break;

case 3:

display();

break;

case 4:

break;

default:

printf("Wrong choice");

break;

}

}while(ch!=4);

return 0;

}

Output:

Priority Queue

What is difference between Queue and Priority Queue?

The queue is a collection of an element where insertion of element is done at one end and elements are removed from another end. In a Priority Queue, elements are inserted in any order but removed based on priority.

Write A Comment