Priority Queue using Doubly Linked List

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:

  1. 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).
  2. Insert both element and priority in the Node.
  3. 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

Leave a Reply

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