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.