Last Updated on December 14, 2022 by Prepbytes
Problem Statement:
Given nodes with their priority, we have to implement a priority queue using a doubly linked list.
What is a Priority Queue?
Priority queues are abstract data structures where each element in the queue has a priority value. For example, in any airline, baggage under the “First-Class” or “Business” arrives before other baggage.
A priority Queue is a type of queue that follows the given below properties:
- An item with higher priority will be dequeued before the item with lower priority.
- If two elements present in the priority queue are having the same priority, then they will be served according to the order in which they are present in the queue.
The priority queue is widely used in many applications like job scheduling algorithms, CPU and Disk scheduling, and managing various resources shared between different processes, etc.
How is the Priority Value assigned in the Priority Queue?
Usually, an element’s value is considered for assigning the priority. For example, the element with bigger value will have a higher priority than the element with lower value.
We can also set priorities according to our demand.
Functions used for implementing priority queue:-
- push(new_element): This function is used to insert a new element into the queue.
- pop(): This function deletes the element with the lowest priority value from the queue.
- peek()/top(): This function is used to get the lowest priority element in the queue without deleting it from the queue.
Approach:
- Create a doubly linked list having fields data (hold the information of the Node), priority (hold the priority of the Node), prev (point to previous Node), next (point to next Node).
- Insert both element and priority in the Node.
- Arrange the Nodes in the increasing order of priority.
// C code to implement priority
// queue using doubly linked list
#include <stdio.h>
#include <stdlib.h>
struct Node {
int info;
int priority;
struct Node *prev, *next;
};
void push(struct Node** fr, struct Node** rr, int n, int p)
{
struct Node* news
= (struct Node*)malloc(sizeof(struct Node*));
news->info = n;
news->priority = p;
if (*fr == NULL) {
*fr = news;
*rr = news;
news->next = NULL;
}
else {
if (p <= (*fr)->priority) {
news->next = *fr;
(*fr)->prev = news->next;
*fr = news;
}
else if (p > (*rr)->priority) {
news->next = NULL;
(*rr)->next = news;
news->prev = (*rr)->next;
*rr = news;
}
else {
struct Node* start = (*fr)->next;
while (start->priority > p)
start = start->next;
(start->prev)->next = news;
news->next = start->prev;
news->prev = (start->prev)->next;
start->prev = news->next;
}
}
}
int peek(struct Node* fr) { return fr->info; }
int isEmpty(struct Node* fr) { return (fr == NULL); }
int pop(struct Node** fr, struct Node** rr)
{
struct Node* temp = *fr;
int res = temp->info;
(*fr) = (*fr)->next;
free(temp);
if (*fr == NULL)
*rr = NULL;
return res;
}
int main()
{
struct Node *front = NULL, *rear = NULL;
push(&front, &rear, 2, 3);
push(&front, &rear, 3, 4);
push(&front, &rear, 4, 5);
push(&front, &rear, 5, 6);
push(&front, &rear, 6, 7);
push(&front, &rear, 1, 2);
printf("%d\n", pop(&front, &rear));
printf("%d\n", peek(front));
return 0;
}
#include <bits/stdc++.h>
using namespace std;
struct Node {
int info;
int priority;
struct Node *prev, *next;
};
void push(Node** fr, Node** rr, int n, int p)
{
Node* news = (Node*)malloc(sizeof(Node));
news->info = n;
news->priority = p;
if (*fr == NULL) {
*fr = news;
*rr = news;
news->next = NULL;
}
else {
if (p <= (*fr)->priority) {
news->next = *fr;
(*fr)->prev = news->next;
*fr = news;
}
else if (p > (*rr)->priority) {
news->next = NULL;
(*rr)->next = news;
news->prev = (*rr)->next;
*rr = news;
}
else {
Node* start = (*fr)->next;
while (start->priority > p)
start = start->next;
(start->prev)->next = news;
news->next = start->prev;
news->prev = (start->prev)->next;
start->prev = news->next;
}
}
}
int peek(Node* fr) { return fr->info; }
bool isEmpty(Node* fr) { return (fr == NULL); }
int pop(Node** fr, Node** rr)
{
Node* temp = *fr;
int res = temp->info;
(*fr) = (*fr)->next;
free(temp);
if (*fr == NULL)
*rr = NULL;
return res;
}
int main()
{
Node *front = NULL, *rear = NULL;
push(&front, &rear, 2, 3);
push(&front, &rear, 3, 4);
push(&front, &rear, 4, 5);
push(&front, &rear, 5, 6);
push(&front, &rear, 6, 7);
push(&front, &rear, 1, 2);
cout << pop(&front, &rear) << endl;
cout << peek(front);
return 0;
}
import java.util.*;
class Solution {
static Node front, rear;
static class Node {
int info;
int priority;
Node prev, next;
}
static void push(Node fr, Node rr, int n, int p)
{
Node news = new Node();
news.info = n;
news.priority = p;
if (fr == null) {
fr = news;
rr = news;
news.next = null;
}
else {
if (p <= (fr).priority) {
news.next = fr;
(fr).prev = news.next;
fr = news;
}
else if (p > (rr).priority) {
news.next = null;
(rr).next = news;
news.prev = (rr).next;
rr = news;
}
else {
Node start = (fr).next;
while (start.priority > p)
start = start.next;
(start.prev).next = news;
news.next = start.prev;
news.prev = (start.prev).next;
start.prev = news.next;
}
}
front = fr;
rear = rr;
}
static int peek(Node fr) { return fr.info; }
static boolean isEmpty(Node fr) { return (fr == null); }
static int pop(Node fr, Node rr)
{
Node temp = fr;
int res = temp.info;
(fr) = (fr).next;
if (fr == null)
rr = null;
front = fr;
rear = rr;
return res;
}
public static void main(String args[])
{
push(front, rear, 2, 3);
push(front, rear, 3, 4);
push(front, rear, 4, 5);
push(front, rear, 5, 6);
push(front, rear, 6, 7);
push(front, rear, 1, 2);
System.out.println(pop(front, rear));
System.out.println(peek(front));
}
}
class Node:
def __init__(self):
self.info = 0
self.priority = 0
self.next = None
self.prev = None
front = None
rear = None
def push(fr, rr, n, p):
global front, rear
news = Node()
news.info = n
news.priority = p
if (fr == None):
fr = news
rr = news
news.next = None
else:
if (p <= (fr).priority):
news.next = fr
(fr).prev = news.next
fr = news
elif (p > (rr).priority):
news.next = None
(rr).next = news
news.prev = (rr).next
rr = news
else:
start = (fr).next
while (start.priority > p):
start = start.next
(start.prev).next = news
news.next = start.prev
news.prev = (start.prev).next
start.prev = news.next
front = fr
rear = rr
def peek(fr):
return fr.info
def isEmpty(fr):
return fr == None
def pop(fr, rr):
global front , rear
temp = fr
res = temp.info
(fr) = (fr).next
if (fr == None):
rr = None
front = fr
rear = rr
return res
if __name__=='__main__':
push( front, rear, 2, 3)
push( front, rear, 3, 4)
push( front, rear, 4, 5)
push( front, rear, 5, 6)
push( front, rear, 6, 7)
push( front, rear, 1, 2)
print(pop(front, rear))
print(peek(front))
This article tried to discuss the concept of Priority Queue using Doubly Linked List. Hope this blog helps you understand the concept. To practice problems you can check out MYCODE | Competitive Programming – Heaps at Prepbytes