Priority Queue Using Linked List

Priority Queue:

Priority queue is an abstract data type, It is a type of queue in which each element has a priority assigned to it. The priority of the element determines the order in which elements are removed from the priority queue. In the priority queue, all the elements are arranged either in ascending order or descending order.

Priority Queue Properties:

  • In the priority queue, every element has priority assigned to it.
  • The element with highest priority first.
  • If two elements are having the same priority then they are served according to their order in the queue.

Linked List:

Linked list is a linear data structure just like arrays. In the linked list the elements are not stored in contiguous locations, the elements are connected or linked using pointers. Each node stores the data and the address of the next node.

  • Data: The Data which is stored at the particular address.
  • Reference: The address of the next node of the linked list.

Linked List Representation:

Implementation using linked list:

The highest priority element will always be the head of the linked list. The list will be arranged in the descending order based on the priority of the elements due to which we can remove the highest priority element in O(1) time.
For inserting an element we have to traverse the list and find the proper position to insert the element so that the sequence of the priority queue will be maintained.

Algorithm:

  • Create a new node with data and priority.
  • Check the priority with the head Node.
  • If the head has lower priority, then connect the new node with the head and move the head pointer to the new node.
  • Else traverse the priority queue and find the proper position of the new node.

Code Implementation

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
	int data;

	int priority;

	struct node* next;

} Node;

Node* newNode(int d, int p)
{
	Node* temp = (Node*)malloc(sizeof(Node));
	temp->data = d;
	temp->priority = p;
	temp->next = NULL;

	return temp;
}

int peek(Node** head)
{
	return (*head)->data;
}

void pop(Node** head)
{
	Node* temp = *head;
	(*head) = (*head)->next;
	free(temp);
}

void push(Node** head, int d, int p)
{
	Node* start = (*head);

	Node* temp = newNode(d, p);

	if ((*head)->priority > p) {

		temp->next = *head;
		(*head) = temp;
	}
	else {

		while (start->next != NULL &&
			start->next->priority < p) {
			start = start->next;
		}

		temp->next = start->next;
		start->next = temp;
	}
}

int isEmpty(Node** head)
{
	return (*head) == NULL;
}

int main()
{
	// Create a Priority Queue
	// 70->40->50->60
	Node* pq = newNode(40, 1);
	push(&pq, 50, 2);
	push(&pq, 60, 3);
	push(&pq, 70, 0);

	while (!isEmpty(&pq)) {
		printf("%d ", peek(&pq));
		pop(&pq);
	}

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

// Node
typedef struct node
{
	int data;

	int priority;

	struct node* next;

} Node;

Node* newNode(int d, int p)
{
	Node* temp = (Node*)malloc(sizeof(Node));
	temp->data = d;
	temp->priority = p;
	temp->next = NULL;

	return temp;
}

int peek(Node** head)
{
	return (*head)->data;
}

void pop(Node** head)
{
	Node* temp = *head;
	(*head) = (*head)->next;
	free(temp);
}

void push(Node** head, int d, int p)
{
	Node* start = (*head);

	// Create new Node
	Node* temp = newNode(d, p);

	if ((*head)->priority > p)
	{
		
		temp->next = *head;
		(*head) = temp;
	}
	else
	{
		while (start->next != NULL &&
			start->next->priority < p)
		{
			start = start->next;
		}

		temp->next = start->next;
		start->next = temp;
	}
}

int isEmpty(Node** head)
{
	return (*head) == NULL;
}

int main()
{
	
	// Create a Priority Queue
	// 70->40->50->60
	Node* pq = newNode(40, 1);
	push(&pq, 50, 2);
	push(&pq, 60, 3);
	push(&pq, 70, 0);

	while (!isEmpty(&pq))
	{
		cout << " " << peek(&pq);
		pop(&pq);
	}
	return 0;
}
import java.util.* ;

class Solution
{
	
static class Node {
	int data;
	
	int priority;
	
	Node next;
	
}

static Node node = new Node();
	
static Node newNode(int d, int p)
{
	Node temp = new Node();
	temp.data = d;
	temp.priority = p;
	temp.next = null;
	
	return temp;
}
	
static int peek(Node head)
{
	return (head).data;
}
	
static Node pop(Node head)
{
	Node temp = head;
	(head) = (head).next;
	return head;
}
	
static Node push(Node head, int d, int p)
{
	Node start = (head);
	
	Node temp = newNode(d, p);
	
	if ((head).priority > p) {
	
		temp.next = head;
		(head) = temp;
	}
	else {
	
		while (start.next != null &&
			start.next.priority < p) {
			start = start.next;
		}
	
		temp.next = start.next;
		start.next = temp;
	}
	return head;
}
	
static int isEmpty(Node head)
{
	return ((head) == null)?1:0;
}
	
public static void main(String args[])
{
	// Create a Priority Queue
	// 70.40.50.60
	Node pq = newNode(4, 1);
	pq =push(pq, 5, 2);
	pq =push(pq, 6, 3);
	pq =push(pq, 7, 0);
	
	while (isEmpty(pq)==0) {
		System.out.printf("%d ", peek(pq));
		pq=pop(pq);
	}
	
}
}

class PriorityQueueNode:
  
  def __init__(self, value, pr):
      
    self.data = value
    self.priority = pr
    self.next = None
  
class PriorityQueue:
  
  def __init__(self):
    
    self.front = None
    
  def isEmpty(self):
    
    return True if self.front == None else False
  
  def push(self, value, priority):
    
    if self.isEmpty() == True:
      
      self.front = PriorityQueueNode(value, priority)
      return 1
      
    else:
      
      if self.front.priority > priority:
        
        newNode = PriorityQueueNode(value, priority)
        
        newNode.next = self.front
        
        self.front = newNode
        
        return 1
        
      else:
        
        temp = self.front
        
        while temp.next:
          
          if priority <= temp.next.priority:
            break
          
          temp = temp.next
        
        newNode = PriorityQueueNode(value, priority)
        newNode.next = temp.next
        temp.next = newNode
        
        return 1
  
  def pop(self):
    
    if self.isEmpty() == True:
      return
    
    else:
      
      self.front = self.front.next
      return 1
      
  def peek(self):
    
    if self.isEmpty() == True:
      return
    else:
      return self.front.data
      
  def traverse(self):
    
    if self.isEmpty() == True:
      return "Queue is Empty!"
    else:
      temp = self.front
      while temp:
        print(temp.data, end = " ")
        temp = temp.next

if __name__ == "__main__":
  
  pq = PriorityQueue()
  pq.push(4, 1)
  pq.push(5, 2)
  pq.push(6, 3)
  pq.push(7, 0)
  
  pq.traverse()
  
  pq.pop()

This article tried to discuss the Implementation of Priority Queue Using Linked List. Hope this blog helps you understand the concept. To practice more problems feel free to check MYCODE | Competitive Programming at Prepbytes.

Leave a Reply

Your email address will not be published. Required fields are marked *