Implementation of Priority Queue Using Linked List in C++

Priority Queue using linked list in C++

 

In this section we will implement the priority queue using linked list. Priority Queue implementation using linked list is more efficient than using array. As 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.

Priority Queue using linked list

Algorithm for Priority Queue Implementation using Linked List: 

  • Create a node structure for creating nodes of the linked list.
  • insert() : This function is used to insert the elements based on the priority level in linked list.
  • delete() : This function delete the head node of the linked list, and make free that memory and then the next node will become the head node of                         the linked list.
  • display() : This function is used to display the elements of the priority queue that is implemented using linked list.
  • peak() : This function is used to display the top element of the priority queue. 
Insertion/Deletion operation on priority queue

Code Implementation for Priority Queue using Linked List

#include<bits/stdc++.h>
using namespace std;

struct Node
{
int data;
int priority;
Node * next;
};

Node * front = NULL;

void insert (int data, int priority)
{

Node * temp, *curr, *pre = NULL;

temp = new Node;
temp->data = data;
temp->priority = priority;

if (front == NULL or priority >= front->priority)
{
temp->next = front;
front = temp;
}

else
{
curr = front;

while (curr and priority <= curr->priority)
{
pre = curr;
curr = curr->next;
}

temp->next = pre->next;
pre->next = temp;
}
}

void Delete ()
{
if (front == NULL)
{
cout << "Priority Queue is underflow" << endl;
return;
}

else
{
Node * temp;
temp = front;

cout << "Deleted item is " << temp->data << endl;

front = temp->next;
free (temp);
}
}

void display ()
{
if (front == NULL)
cout << "Priority-Queue is empty" << endl;

Node * curr = front;

cout<<"\nPriority-Queue elements are : ";

while (curr)
{
cout << curr->data << " ";
curr = curr->next;
}

cout << endl;

return;
}

void peak ()
{
cout << "Peak element is :" << front->data << endl;
}

int main ()
{
insert (2, 9);
insert (3, 4);
insert (6, 8);

display ();

peak();

Delete ();
Delete ();
display ();

return 0;

}
Output:

Priority-Queue elements are :2 6 3

Peak element is : 2

Deleted element : 2

Deleted element : 6

Priority-Queue elements are : 3