# Priority queue using doubly linked list

The problem at hand is the implementation of a priority queue using a doubly linked list in the C programming language. A priority queue is a data structure that allows elements to be inserted with a priority value and supports operations to remove elements with the highest priority.

## Problem Statement

The task is to create a priority queue using a doubly linked list. The queue should have the following operations:

1. enqueue: Add an element with a priority value to the queue.
2. dequeue: Remove and return the element with the highest priority.
3. peek: Return the element with the highest priority without removing it.
4. isEmpty: Check if the queue is empty.
5. isSize: Return the number of elements in the queue.
6. printQdata: Display the elements in the queue.

## Explanation with an Example

Imagine you're managing tasks in a to-do list application. Each task has a priority, and you need to keep tasks organized based on their priorities. For instance, a task with a higher priority value should be completed before a task with a lower priority value.

## Idea to Solve

The idea to solve this problem is to use a doubly linked list to maintain the elements in the queue. Elements will be inserted in such a way that they are sorted based on their priority values. This way, the element with the highest priority will always be at the front of the queue.

## Pseudocode

``````Structure QNode:
data
next
prev

Structure PriorityQueue:
front
rear
size

newQueue():
Create and initialize a new PriorityQueue
Return the new PriorityQueue

enqueue(q, data):
Create a new QNode with the given data
Find the appropriate position to insert the new node based on priority
Adjust pointers to insert the node
Increment the size of the queue

dequeue(q):
Remove the front node from the queue
Return the data of the removed node

peek(q):
Return the data of the front node without removing it

isEmpty(q):
Check if the queue is empty and return a boolean value

isSize(q):
Return the size of the queue

printQdata(q):
Traverse the queue and print the data of each node

Main:
Initialize a new PriorityQueue
Add elements with different priority values to the queue
Print the queue elements and size
Dequeue elements and print them
Print the updated queue elements and size``````

## Algorithm Explanation

1. Initialize a new PriorityQueue using the `newQueue` function.
2. Add elements with varying priority values to the queue using the `enqueue` function.
3. Print the elements in the queue and its size using the `printQdata` and `isSize` functions.
4. Use the `dequeue` function to remove and print elements from the queue.
5. Print the updated elements in the queue and its size again.

## Code Solution

``````/*
C Program
Priority queue using doubly linked list
*/
#include <stdio.h>
#include <stdlib.h>

// Create structure of Doubly Linked List Node
struct QNode
{
int data;
struct QNode *next;
struct QNode *prev;
};
struct PriorityQueue
{
struct QNode *front;
struct QNode *rear;
int size;
};
// Returns a new queue
struct PriorityQueue *newQueue()
{
struct PriorityQueue *q = (struct PriorityQueue *) malloc(sizeof(struct PriorityQueue));
if (q == NULL)
{
printf("\n Memory overflow , When creating a new Queue");
}
else
{
q->front = NULL;
q->rear = NULL;
q->size = 0;
}
return q;
}
// Add a node into queue
void enqueue(struct PriorityQueue *q, int data)
{
//Create a dynamic node
struct QNode *node = (struct QNode *) malloc(sizeof(struct QNode));
if (node == NULL)
{
printf("\n Memory overflow , When creating a new Queue Node");
}
else
{
// Set node value
node->data = data;
node->next = NULL;
node->prev = NULL;
if (q->front == NULL)
{
// When adding a first node of queue
q->front = node;
q->rear = node;
}
else if (q->front->data <= data)
{
// Add node at beginning position
node->next = q->front;
q->front->prev = node;
q->front = node;
}
else if (q->rear->data >= data)
{
// Add node at last position
node->prev = q->rear;
q->rear->next = node;
q->rear = node;
}
else
{
struct QNode *temp = q->front;
// Find the location of inserting priority node
while (temp->data > data)
{
temp = temp->next;
}
node->next = temp;
node->prev = temp->prev;
temp->prev = node;
if (node->prev != NULL)
{
node->prev->next = node;
}
}
q->size = q->size + 1;
}
}
int isEmpty(struct PriorityQueue *q)
{
if (q->size == 0)
{
return 1;
}
else
{
return 0;
}
}
// Get a front element of queue
int peek(struct PriorityQueue *q)
{
if (isEmpty(q) == 1)
{
// When stack is empty
return -1;
}
else
{
return q->front->data;
}
}
int isSize(struct PriorityQueue *q)
{
return q->size;
}
// Remove a front node of a queue
int dequeue(struct PriorityQueue *q)
{
if (isEmpty(q) == 1)
{
printf("\n Empty Queue \n");
// When queue is empty
return -1;
}
else
{
int data = peek(q);
struct QNode *temp = q->front;
if (q->front == q->rear)
{
// When queue contains only one node
q->rear = NULL;
q->front = NULL;
}
else
{
q->front = q->front->next;
q->front->prev = NULL;
}
// Change queue size
q->size--;
free(temp);
return data;
}
}
// Print elements of queue
void printQdata(struct PriorityQueue *q)
{
struct QNode *node = q->front;
printf("\n Queue Element \n");
while (node != NULL)
{
printf(" %d", node->data);
node = node->next;
}
printf("\n");
}
int main(int argc, char
const *argv[])
{
struct PriorityQueue *q = newQueue();
enqueue(q, 7);
enqueue(q, 4);
enqueue(q, 8);
enqueue(q, 5);
enqueue(q, 3);
enqueue(q, 6);
printQdata(q);
printf(" Size : %d", isSize(q));
// Remove queue element
printf("\n Dequeue Node : %d", dequeue(q));
printf("\n Dequeue Node : %d", dequeue(q));
printf("\n Dequeue Node : %d", dequeue(q));
printf("\n Dequeue Node : %d", dequeue(q));
printf("\n Dequeue Node : %d", dequeue(q));
printQdata(q);
printf(" Size : %d", isSize(q));
return 0;
}``````

#### Output

`````` Queue Element
8 7 6 5 4 3
Size : 6
Dequeue Node : 8
Dequeue Node : 7
Dequeue Node : 6
Dequeue Node : 5
Dequeue Node : 4
Queue Element
3
Size : 1``````
``````/*
Java Program
Priority queue using doubly linked list
*/
class QNode
{
public int data;
public QNode next;
public QNode prev;
public QNode(int data)
{
this.data = data;
this.next = null;
this.prev = null;
}
}
public class PriorityQueue
{
public QNode front;
public QNode rear;
public int size;
public PriorityQueue()
{
this.front = null;
this.rear = null;
this.size = 0;
}
// Add a node into queue Priority queue
public void enqueue(int data)
{
//Create a dynamic node
QNode node = new QNode(data);
if (this.front == null)
{
// When adding a first node of queue
this.front = node;
this.rear = node;
}
else if (this.front.data <= data)
{
// Add node at beginning position
node.next = this.front;
this.front.prev = node;
this.front = node;
}
else if (this.rear.data >= data)
{
// Add node at last position
node.prev = this.rear;
this.rear.next = node;
this.rear = node;
}
else
{
QNode temp = this.front;
// Find the location of inserting priority node
while (temp.data > data)
{
temp = temp.next;
}
node.next = temp;
node.prev = temp.prev;
temp.prev = node;
if (node.prev != null)
{
node.prev.next = node;
}
}
this.size = this.size + 1;
}
public boolean isEmpty()
{
if (this.size == 0)
{
return true;
}
else
{
return false;
}
}
// Get a front element of queue
public int peek()
{
if (this.isEmpty() == true)
{
System.out.print("\n Empty Queue \n");
// When stack is empty
return -1;
}
else
{
return this.front.data;
}
}
public int isSize()
{
return this.size;
}
// Remove a front node of a queue
public int dequeue()
{
if (this.isEmpty() == true)
{
// When queue is empty
return -1;
}
else
{
int data = this.peek();
QNode temp = this.front;
if (this.front == this.rear)
{
// When queue contains only one node
this.rear = null;
this.front = null;
}
else
{
this.front = this.front.next;
this.front.prev = null;
}
// Change queue size
this.size--;
return data;
}
}
// Print elements of queue
public void printQdata()
{
QNode node = this.front;
System.out.print("\n Queue Element \n");
while (node != null)
{
System.out.print("  " + node.data);
node = node.next;
}
System.out.print("\n");
}
public static void main(String[] args)
{
PriorityQueue q = new PriorityQueue();
q.enqueue(7);
q.enqueue(4);
q.enqueue(8);
q.enqueue(5);
q.enqueue(3);
q.enqueue(6);
q.printQdata();
System.out.print(" Size : " + q.isSize());
// Remove queue element
System.out.print("\n Dequeue Node : " + q.dequeue());
System.out.print("\n Dequeue Node : " + q.dequeue());
System.out.print("\n Dequeue Node : " + q.dequeue());
System.out.print("\n Dequeue Node : " + q.dequeue());
System.out.print("\n Dequeue Node : " + q.dequeue());
q.printQdata();
System.out.print(" Size : " + q.isSize());
}
}``````

#### Output

`````` Queue Element
8  7  6  5  4  3
Size : 6
Dequeue Node : 8
Dequeue Node : 7
Dequeue Node : 6
Dequeue Node : 5
Dequeue Node : 4
Queue Element
3
Size : 1``````
``````// Include header file
#include <iostream>
using namespace std;

/*
C++ Program
Priority queue using doubly linked list
*/

class QNode
{
public:
int data;
QNode *next;
QNode *prev;
QNode(int data)
{
this->data = data;
this->next = NULL;
this->prev = NULL;
}
};
class PriorityQueue
{
public:
QNode *front;
QNode *rear;
int size;
PriorityQueue()
{
this->front = NULL;
this->rear = NULL;
this->size = 0;
}
// Add a node into queue Priority queue
void enqueue(int data)
{
//Create a dynamic node
QNode *node = new QNode(data);
if (this->front == NULL)
{
// When adding a first node of queue
this->front = node;
this->rear = node;
}
else if (this->front->data <= data)
{
// Add node at beginning position
node->next = this->front;
this->front->prev = node;
this->front = node;
}
else if (this->rear->data >= data)
{
// Add node at last position
node->prev = this->rear;
this->rear->next = node;
this->rear = node;
}
else
{
QNode *temp = this->front;
// Find the location of inserting priority node
while (temp->data > data)
{
temp = temp->next;
}
node->next = temp;
node->prev = temp->prev;
temp->prev = node;
if (node->prev != NULL)
{
node->prev->next = node;
}
}
this->size = this->size + 1;
}
bool isEmpty()
{
if (this->size == 0)
{
return true;
}
else
{
return false;
}
}
// Get a front element of queue
int peek()
{
if (this->isEmpty() == true)
{
cout << "\n Empty Queue \n";
// When stack is empty
return -1;
}
else
{
return this->front->data;
}
}
int isSize()
{
return this->size;
}
// Remove a front node of a queue
int dequeue()
{
if (this->isEmpty() == true)
{
// When queue is empty
return -1;
}
else
{
int data = this->peek();
QNode *temp = this->front;
if (this->front == this->rear)
{
// When queue contains only one node
this->rear = NULL;
this->front = NULL;
}
else
{
this->front = this->front->next;
this->front->prev = NULL;
}
// Change queue size
this->size--;
delete temp;
temp = NULL;
return data;
}
}
// Print elements of queue
void printQdata()
{
QNode *node = this->front;
cout << "\n Queue Element \n";
while (node != NULL)
{
cout << "  " << node->data;
node = node->next;
}
cout << "\n";
}
};
int main()
{
PriorityQueue q = PriorityQueue();
q.enqueue(7);
q.enqueue(4);
q.enqueue(8);
q.enqueue(5);
q.enqueue(3);
q.enqueue(6);
q.printQdata();
cout << " Size : " << q.isSize();
// Remove queue element
cout << "\n Dequeue Node : " << q.dequeue();
cout << "\n Dequeue Node : " << q.dequeue();
cout << "\n Dequeue Node : " << q.dequeue();
cout << "\n Dequeue Node : " << q.dequeue();
cout << "\n Dequeue Node : " << q.dequeue();
q.printQdata();
cout << " Size : " << q.isSize();
return 0;
}``````

#### Output

`````` Queue Element
8  7  6  5  4  3
Size : 6
Dequeue Node : 8
Dequeue Node : 7
Dequeue Node : 6
Dequeue Node : 5
Dequeue Node : 4
Queue Element
3
Size : 1``````
``````// Include namespace system
using System;
/*
C# Program
Priority queue using doubly linked list
*/
public class QNode
{
public int data;
public QNode next;
public QNode prev;
public QNode(int data)
{
this.data = data;
this.next = null;
this.prev = null;
}
}
public class PriorityQueue
{
public QNode front;
public QNode rear;
public int size;
public PriorityQueue()
{
this.front = null;
this.rear = null;
this.size = 0;
}
// Add a node into queue Priority queue
public void enqueue(int data)
{
//Create a dynamic node
QNode node = new QNode(data);
if (this.front == null)
{
// When adding a first node of queue
this.front = node;
this.rear = node;
}
else if (this.front.data <= data)
{
// Add node at beginning position
node.next = this.front;
this.front.prev = node;
this.front = node;
}
else if (this.rear.data >= data)
{
// Add node at last position
node.prev = this.rear;
this.rear.next = node;
this.rear = node;
}
else
{
QNode temp = this.front;
// Find the location of inserting priority node
while (temp.data > data)
{
temp = temp.next;
}
node.next = temp;
node.prev = temp.prev;
temp.prev = node;
if (node.prev != null)
{
node.prev.next = node;
}
}
this.size = this.size + 1;
}
public Boolean isEmpty()
{
if (this.size == 0)
{
return true;
}
else
{
return false;
}
}
// Get a front element of queue
public int peek()
{
if (this.isEmpty() == true)
{
Console.Write("\n Empty Queue \n");
// When stack is empty
return -1;
}
else
{
return this.front.data;
}
}
public int isSize()
{
return this.size;
}
// Remove a front node of a queue
public int dequeue()
{
if (this.isEmpty() == true)
{
// When queue is empty
return -1;
}
else
{
int data = this.peek();
if (this.front == this.rear)
{
// When queue contains only one node
this.rear = null;
this.front = null;
}
else
{
this.front = this.front.next;
this.front.prev = null;
}
// Change queue size
this.size--;
return data;
}
}
// Print elements of queue
public void printQdata()
{
QNode node = this.front;
Console.Write("\n Queue Element \n");
while (node != null)
{
Console.Write("  " + node.data);
node = node.next;
}
Console.Write("\n");
}
public static void Main(String[] args)
{
PriorityQueue q = new PriorityQueue();
q.enqueue(7);
q.enqueue(4);
q.enqueue(8);
q.enqueue(5);
q.enqueue(3);
q.enqueue(6);
q.printQdata();
Console.Write(" Size : " + q.isSize());
// Remove queue element
Console.Write("\n Dequeue Node : " + q.dequeue());
Console.Write("\n Dequeue Node : " + q.dequeue());
Console.Write("\n Dequeue Node : " + q.dequeue());
Console.Write("\n Dequeue Node : " + q.dequeue());
Console.Write("\n Dequeue Node : " + q.dequeue());
q.printQdata();
Console.Write(" Size : " + q.isSize());
}
}``````

#### Output

`````` Queue Element
8  7  6  5  4  3
Size : 6
Dequeue Node : 8
Dequeue Node : 7
Dequeue Node : 6
Dequeue Node : 5
Dequeue Node : 4
Queue Element
3
Size : 1``````
``````<?php
/*
Php Program
Priority queue using doubly linked list
*/
class QNode
{
public \$data;
public \$next;
public \$prev;

function __construct(\$data)
{
\$this->data = \$data;
\$this->next = null;
\$this->prev = null;
}
}
class PriorityQueue
{
public \$front;
public \$rear;
public \$size;

function __construct()
{
\$this->front = null;
\$this->rear = null;
\$this->size = 0;
}
// Add a node into queue Priority queue
public	function enqueue(\$data)
{
//Create a dynamic node
\$node = new QNode(\$data);
if (\$this->front == null)
{
// When adding a first node of queue
\$this->front = \$node;
\$this->rear = \$node;
}
else if (\$this->front->data <= \$data)
{
// Add node at beginning position
\$node->next = \$this->front;
\$this->front->prev = \$node;
\$this->front = \$node;
}
else if (\$this->rear->data >= \$data)
{
// Add node at last position
\$node->prev = \$this->rear;
\$this->rear->next = \$node;
\$this->rear = \$node;
}
else
{
\$temp = \$this->front;
// Find the location of inserting priority node
while (\$temp->data > \$data)
{
\$temp = \$temp->next;
}
\$node->next = \$temp;
\$node->prev = \$temp->prev;
\$temp->prev = \$node;
if (\$node->prev != null)
{
\$node->prev->next = \$node;
}
}
\$this->size = \$this->size + 1;
}
public	function isEmpty()
{
if (\$this->size == 0)
{
return true;
}
else
{
return false;
}
}
// Get a front element of queue
public	function peek()
{
if (\$this->isEmpty() == true)
{
echo "\n Empty Queue \n";
// When stack is empty
return -1;
}
else
{
return \$this->front->data;
}
}
public	function isSize()
{
return \$this->size;
}
// Remove a front node of a queue
public	function dequeue()
{
if (\$this->isEmpty() == true)
{
// When queue is empty
return -1;
}
else
{
\$data = \$this->peek();
if (\$this->front == \$this->rear)
{
// When queue contains only one node
\$this->rear = null;
\$this->front = null;
}
else
{
\$this->front = \$this->front->next;
\$this->front->prev = null;
}
// Change queue size
\$this->size--;
return \$data;
}
}
// Print elements of queue
public	function printQdata()
{
\$node = \$this->front;
echo "\n Queue Element \n";
while (\$node != null)
{
echo "  ". \$node->data;
\$node = \$node->next;
}
echo "\n";
}
}

function main()
{
\$q = new PriorityQueue();
\$q->enqueue(7);
\$q->enqueue(4);
\$q->enqueue(8);
\$q->enqueue(5);
\$q->enqueue(3);
\$q->enqueue(6);
\$q->printQdata();
echo " Size : ". \$q->isSize();
// Remove queue element
echo "\n Dequeue Node : ". \$q->dequeue();
echo "\n Dequeue Node : ". \$q->dequeue();
echo "\n Dequeue Node : ". \$q->dequeue();
echo "\n Dequeue Node : ". \$q->dequeue();
echo "\n Dequeue Node : ". \$q->dequeue();
\$q->printQdata();
echo " Size : ". \$q->isSize();
}
main();``````

#### Output

`````` Queue Element
8  7  6  5  4  3
Size : 6
Dequeue Node : 8
Dequeue Node : 7
Dequeue Node : 6
Dequeue Node : 5
Dequeue Node : 4
Queue Element
3
Size : 1``````
``````/*
Node Js Program
Priority queue using doubly linked list
*/
class QNode
{
constructor(data)
{
this.data = data;
this.next = null;
this.prev = null;
}
}
class PriorityQueue
{
constructor()
{
this.front = null;
this.rear = null;
this.size = 0;
}
// Add a node into queue Priority queue
enqueue(data)
{
//Create a dynamic node
var node = new QNode(data);
if (this.front == null)
{
// When adding a first node of queue
this.front = node;
this.rear = node;
}
else if (this.front.data <= data)
{
// Add node at beginning position
node.next = this.front;
this.front.prev = node;
this.front = node;
}
else if (this.rear.data >= data)
{
// Add node at last position
node.prev = this.rear;
this.rear.next = node;
this.rear = node;
}
else
{
var temp = this.front;
// Find the location of inserting priority node
while (temp.data > data)
{
temp = temp.next;
}
node.next = temp;
node.prev = temp.prev;
temp.prev = node;
if (node.prev != null)
{
node.prev.next = node;
}
}
this.size = this.size + 1;
}
isEmpty()
{
if (this.size == 0)
{
return true;
}
else
{
return false;
}
}
// Get a front element of queue
peek()
{
if (this.isEmpty() == true)
{
process.stdout.write("\n Empty Queue \n");
// When stack is empty
return -1;
}
else
{
return this.front.data;
}
}
isSize()
{
return this.size;
}
// Remove a front node of a queue
dequeue()
{
if (this.isEmpty() == true)
{
// When queue is empty
return -1;
}
else
{
var data = this.peek();
if (this.front == this.rear)
{
// When queue contains only one node
this.rear = null;
this.front = null;
}
else
{
this.front = this.front.next;
this.front.prev = null;
}
// Change queue size
this.size--;
return data;
}
}
// Print elements of queue
printQdata()
{
var node = this.front;
process.stdout.write("\n Queue Element \n");
while (node != null)
{
process.stdout.write("  " + node.data);
node = node.next;
}
process.stdout.write("\n");
}
}

function main()
{
var q = new PriorityQueue();
q.enqueue(7);
q.enqueue(4);
q.enqueue(8);
q.enqueue(5);
q.enqueue(3);
q.enqueue(6);
q.printQdata();
process.stdout.write(" Size : " + q.isSize());
// Remove queue element
process.stdout.write("\n Dequeue Node : " + q.dequeue());
process.stdout.write("\n Dequeue Node : " + q.dequeue());
process.stdout.write("\n Dequeue Node : " + q.dequeue());
process.stdout.write("\n Dequeue Node : " + q.dequeue());
process.stdout.write("\n Dequeue Node : " + q.dequeue());
q.printQdata();
process.stdout.write(" Size : " + q.isSize());
}
main();``````

#### Output

`````` Queue Element
8  7  6  5  4  3
Size : 6
Dequeue Node : 8
Dequeue Node : 7
Dequeue Node : 6
Dequeue Node : 5
Dequeue Node : 4
Queue Element
3
Size : 1``````
``````#   Python 3 Program
#   Priority queue using doubly linked list

class QNode :

def __init__(self, data) :
self.data = data
self.next = None
self.prev = None

class PriorityQueue :

def __init__(self) :
self.front = None
self.rear = None
self.size = 0

#  Add a node into queue Priority queue
def enqueue(self, data) :
# Create a dynamic node
node = QNode(data)
if (self.front == None) :
#  When adding a first node of queue
self.front = node
self.rear = node

elif(self.front.data <= data) :
#  Add node at beginning position
node.next = self.front
self.front.prev = node
self.front = node

elif(self.rear.data >= data) :
#  Add node at last position
node.prev = self.rear
self.rear.next = node
self.rear = node
else :
temp = self.front
#  Find the location of inserting priority node
while (temp.data > data) :
temp = temp.next

node.next = temp
node.prev = temp.prev
temp.prev = node
if (node.prev != None) :
node.prev.next = node

self.size = self.size + 1

def isEmpty(self) :
if (self.size == 0) :
return True
else :
return False

#  Get a front element of queue
def peek(self) :
if (self.isEmpty() == True) :
print("\n Empty Queue ")
#  When stack is empty
return -1
else :
return self.front.data

def isSize(self) :
return self.size

#  Remove a front node of a queue
def dequeue(self) :
if (self.isEmpty() == True) :
#  When queue is empty
return -1
else :
data = self.peek()
if (self.front == self.rear) :
#  When queue contains only one node
self.rear = None
self.front = None
else :
self.front = self.front.next
self.front.prev = None

#  Change queue size
self.size -= 1
return data

#  Print elements of queue
def printQdata(self) :
node = self.front
print("\n Queue Element ")
while (node != None) :
print("  ", node.data, end = "")
node = node.next

print(end = "\n")

def main() :
q = PriorityQueue()
q.enqueue(7)
q.enqueue(4)
q.enqueue(8)
q.enqueue(5)
q.enqueue(3)
q.enqueue(6)
q.printQdata()
print(" Size : ", q.isSize(), end = "")
#  Remove queue element
print("\n Dequeue Node : ", q.dequeue(), end = "")
print("\n Dequeue Node : ", q.dequeue(), end = "")
print("\n Dequeue Node : ", q.dequeue(), end = "")
print("\n Dequeue Node : ", q.dequeue(), end = "")
print("\n Dequeue Node : ", q.dequeue(), end = "")
q.printQdata()
print(" Size : ", q.isSize(), end = "")

if __name__ == "__main__": main()``````

#### Output

`````` Queue Element
8   7   6   5   4   3
Size :  6
Dequeue Node :  8
Dequeue Node :  7
Dequeue Node :  6
Dequeue Node :  5
Dequeue Node :  4
Queue Element
3
Size :  1``````
``````#  Ruby Program
#  Priority queue using doubly linked list

class QNode
# Define the accessor and reader of class QNode
attr_accessor :data, :next, :prev

def initialize(data)
self.data = data
self.next = nil
self.prev = nil
end

end

class PriorityQueue
# Define the accessor and reader of class PriorityQueue
attr_accessor :front, :rear, :size

def initialize()
self.front = nil
self.rear = nil
self.size = 0
end

#  Add a node into queue Priority queue
def enqueue(data)
# Create a dynamic node
node = QNode.new(data)
if (self.front == nil)
#  When adding a first node of queue
self.front = node
self.rear = node
elsif(self.front.data <= data)
#  Add node at beginning position
node.next = self.front
self.front.prev = node
self.front = node
elsif(self.rear.data >= data)
#  Add node at last position
node.prev = self.rear
self.rear.next = node
self.rear = node
else
temp = self.front
#  Find the location of inserting priority node
while (temp.data > data)
temp = temp.next
end

node.next = temp
node.prev = temp.prev
temp.prev = node
if (node.prev != nil)
node.prev.next = node
end

end

self.size = self.size + 1
end

def isEmpty()
if (self.size == 0)
return true
else
return false
end

end

#  Get a front element of queue
def peek()
if (self.isEmpty() == true)
print("\n Empty Queue \n")
#  When stack is empty
return -1
else
return self.front.data
end

end

def isSize()
return self.size
end

#  Remove a front node of a queue
def dequeue()
if (self.isEmpty() == true)
#  When queue is empty
return -1
else
data = self.peek()
if (self.front == self.rear)
#  When queue contains only one node
self.rear = nil
self.front = nil
else
self.front = self.front.next
self.front.prev = nil
end

#  Change queue size
self.size -= 1
return data
end

end

#  Print elements of queue
def printQdata()
node = self.front
print("\n Queue Element \n")
while (node != nil)
print("  ", node.data)
node = node.next
end

print("\n")
end

end

def main()
q = PriorityQueue.new()
q.enqueue(7)
q.enqueue(4)
q.enqueue(8)
q.enqueue(5)
q.enqueue(3)
q.enqueue(6)
q.printQdata()
print(" Size : ", q.isSize())
#  Remove queue element
print("\n Dequeue Node : ", q.dequeue())
print("\n Dequeue Node : ", q.dequeue())
print("\n Dequeue Node : ", q.dequeue())
print("\n Dequeue Node : ", q.dequeue())
print("\n Dequeue Node : ", q.dequeue())
q.printQdata()
print(" Size : ", q.isSize())
end

main()``````

#### Output

`````` Queue Element
8  7  6  5  4  3
Size : 6
Dequeue Node : 8
Dequeue Node : 7
Dequeue Node : 6
Dequeue Node : 5
Dequeue Node : 4
Queue Element
3
Size : 1``````
``````/*
Scala Program
Priority queue using doubly linked list
*/
class QNode(var data: Int , var next: QNode , var prev: QNode)
{
def this(data: Int)
{
this(data, null, null);
}
}
class PriorityQueue(var front: QNode , var rear: QNode , var size: Int)
{
def this()
{
this(null, null, 0);
}
// Add a node into queue Priority queue
def enqueue(data: Int): Unit = {
//Create a dynamic node
var node: QNode = new QNode(data);
if (this.front == null)
{
// When adding a first node of queue
this.front = node;
this.rear = node;
}
else if (this.front.data <= data)
{
// Add node at beginning position
node.next = this.front;
this.front.prev = node;
this.front = node;
}
else if (this.rear.data >= data)
{
// Add node at last position
node.prev = this.rear;
this.rear.next = node;
this.rear = node;
}
else
{
var temp: QNode = this.front;
// Find the location of inserting priority node
while (temp.data > data)
{
temp = temp.next;
}
node.next = temp;
node.prev = temp.prev;
temp.prev = node;
if (node.prev != null)
{
node.prev.next = node;
}
}
this.size = this.size + 1;
}
def isEmpty(): Boolean = {
if (this.size == 0)
{
return true;
}
else
{
return false;
}
}
// Get a front element of queue
def peek(): Int = {
if (this.isEmpty() == true)
{
print("\n Empty Queue \n");
// When stack is empty
return -1;
}
else
{
return this.front.data;
}
}
def isSize(): Int = {
return this.size;
}
// Remove a front node of a queue
def dequeue(): Int = {
if (this.isEmpty() == true)
{
// When queue is empty
return -1;
}
else
{
var data: Int = this.peek();
if (this.front == this.rear)
{
// When queue contains only one node
this.rear = null;
this.front = null;
}
else
{
this.front = this.front.next;
this.front.prev = null;
}
// Change queue size
this.size -= 1;
return data;
}
}
// Print elements of queue
def printQdata(): Unit = {
var node: QNode = this.front;
print("\n Queue Element \n");
while (node != null)
{
print("  " + node.data);
node = node.next;
}
print("\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var q: PriorityQueue = new PriorityQueue();
q.enqueue(7);
q.enqueue(4);
q.enqueue(8);
q.enqueue(5);
q.enqueue(3);
q.enqueue(6);
q.printQdata();
print(" Size : " + q.isSize());
// Remove queue element
print("\n Dequeue Node : " + q.dequeue());
print("\n Dequeue Node : " + q.dequeue());
print("\n Dequeue Node : " + q.dequeue());
print("\n Dequeue Node : " + q.dequeue());
print("\n Dequeue Node : " + q.dequeue());
q.printQdata();
print(" Size : " + q.isSize());
}
}``````

#### Output

`````` Queue Element
8  7  6  5  4  3
Size : 6
Dequeue Node : 8
Dequeue Node : 7
Dequeue Node : 6
Dequeue Node : 5
Dequeue Node : 4
Queue Element
3
Size : 1``````
``````/*
Swift 4 Program
Priority queue using doubly linked list
*/
class QNode
{
var data: Int;
var next: QNode? ;
var prev: QNode? ;
init(_ data: Int)
{
self.data = data;
self.next = nil;
self.prev = nil;
}
}
class PriorityQueue
{
var front: QNode? ;
var rear: QNode? ;
var size: Int;
init()
{
self.front = nil;
self.rear = nil;
self.size = 0;
}
// Add a node into queue Priority queue
func enqueue(_ data: Int)
{
//Create a dynamic node
let node: QNode? = QNode(data);
if (self.front == nil)
{
// When adding a first node of queue
self.front = node;
self.rear = node;
}
else if (self.front!.data <= data)
{
// Add node at beginning position
node!.next = self.front;
self.front!.prev = node;
self.front = node;
}
else if (self.rear!.data >= data)
{
// Add node at last position
node!.prev = self.rear;
self.rear!.next = node;
self.rear = node;
}
else
{
var temp: QNode? = self.front;
// Find the location of inserting priority node
while (temp!.data > data)
{
temp = temp!.next;
}
node!.next = temp;
node!.prev = temp!.prev;
temp!.prev = node;
if (node!.prev  != nil)
{
node!.prev!.next = node;
}
}
self.size = self.size + 1;
}
func isEmpty()->Bool
{
if (self.size == 0)
{
return true;
}
else
{
return false;
}
}
// Get a front element of queue
func peek()->Int
{
if (self.isEmpty() == true)
{
print("\n Empty Queue ");
// When stack is empty
return -1;
}
else
{
return self.front!.data;
}
}
func isSize()->Int
{
return self.size;
}
// Remove a front node of a queue
func dequeue()->Int
{
if (self.isEmpty() == true)
{
// When queue is empty
return -1;
}
else
{
let data: Int = self.peek();
if (self.front === self.rear)
{
// When queue contains only one node
self.rear = nil;
self.front = nil;
}
else
{
self.front = self.front!.next;
self.front!.prev = nil;
}
// Change queue size
self.size -= 1;
return data;
}
}
// Print elements of queue
func printQdata()
{
var node: QNode? = self.front;
print("\n Queue Element ");
while (node  != nil)
{
print("  ", node!.data, terminator: "");
node = node!.next;
}
print(terminator: "\n");
}
}
func main()
{
let q: PriorityQueue = PriorityQueue();
q.enqueue(7);
q.enqueue(4);
q.enqueue(8);
q.enqueue(5);
q.enqueue(3);
q.enqueue(6);
q.printQdata();
print(" Size : ", q.isSize(), terminator: "");
// Remove queue element
print("\n Dequeue Node : ", q.dequeue(), terminator: "");
print("\n Dequeue Node : ", q.dequeue(), terminator: "");
print("\n Dequeue Node : ", q.dequeue(), terminator: "");
print("\n Dequeue Node : ", q.dequeue(), terminator: "");
print("\n Dequeue Node : ", q.dequeue(), terminator: "");
q.printQdata();
print(" Size : ", q.isSize(), terminator: "");
}
main();``````

#### Output

`````` Queue Element
8   7   6   5   4   3
Size :  6
Dequeue Node :  8
Dequeue Node :  7
Dequeue Node :  6
Dequeue Node :  5
Dequeue Node :  4
Queue Element
3
Size :  1``````
``````/*
Kotlin Program
Priority queue using doubly linked list
*/
class QNode
{
var data: Int;
var next: QNode ? ;
var prev: QNode ? ;
constructor(data: Int)
{
this.data = data;
this.next = null;
this.prev = null;
}
}
class PriorityQueue
{
var front: QNode ? ;
var rear: QNode ? ;
var size: Int;
constructor()
{
this.front = null;
this.rear = null;
this.size = 0;
}
// Add a node into queue Priority queue
fun enqueue(data: Int): Unit
{
//Create a dynamic node
var node: QNode ? = QNode(data);
if (this.front == null)
{
// When adding a first node of queue
this.front = node;
this.rear = node;
}
else if (this.front!!.data <= data)
{
// Add node at beginning position
node?.next = this.front;
this.front?.prev = node;
this.front = node;
}
else if (this.rear!!.data >= data)
{
// Add node at last position
node?.prev = this.rear;
this.rear?.next = node;
this.rear = node;
}
else
{
var temp: QNode ? = this.front;
// Find the location of inserting priority node
while (temp!!.data > data)
{
temp = temp.next;
}
node?.next = temp;
node?.prev = temp.prev;
temp.prev = node;
if (node?.prev != null)
{
node.prev?.next = node;
}
}
this.size = this.size + 1;
}
fun isEmpty(): Boolean
{
if (this.size == 0)
{
return true;
}
else
{
return false;
}
}
// Get a front element of queue
fun peek(): Int
{
if (this.isEmpty() == true)
{
print("\n Empty Queue \n");
// When stack is empty
return -1;
}
else
{
return this.front!!.data;
}
}
fun isSize(): Int
{
return this.size;
}
// Remove a front node of a queue
fun dequeue(): Int
{
if (this.isEmpty() == true)
{
// When queue is empty
return -1;
}
else
{
var data: Int = this.peek();
if (this.front == this.rear)
{
// When queue contains only one node
this.rear = null;
this.front = null;
}
else
{
this.front = this.front?.next;
this.front?.prev = null;
}
// Change queue size
this.size -= 1;
return data;
}
}
// Print elements of queue
fun printQdata(): Unit
{
var node: QNode ? = this.front;
print("\n Queue Element \n");
while (node != null)
{
print("  " + node.data);
node = node.next;
}
print("\n");
}
}
fun main(args: Array < String > ): Unit
{
var q: PriorityQueue = PriorityQueue();
q.enqueue(7);
q.enqueue(4);
q.enqueue(8);
q.enqueue(5);
q.enqueue(3);
q.enqueue(6);
q.printQdata();
print(" Size : " + q.isSize());
// Remove queue element
print("\n Dequeue Node : " + q.dequeue());
print("\n Dequeue Node : " + q.dequeue());
print("\n Dequeue Node : " + q.dequeue());
print("\n Dequeue Node : " + q.dequeue());
print("\n Dequeue Node : " + q.dequeue());
q.printQdata();
print(" Size : " + q.isSize());
}``````

#### Output

`````` Queue Element
8  7  6  5  4  3
Size : 6
Dequeue Node : 8
Dequeue Node : 7
Dequeue Node : 6
Dequeue Node : 5
Dequeue Node : 4
Queue Element
3
Size : 1``````

## Time Complexity

1. Enqueue operation: O(n)
2. Dequeue operation: O(1)
3. Peek operation: O(1)
4. IsEmpty operation: O(1)
5. IsSize operation: O(1)

The enqueue operation takes O(n) time in the worst case since the algorithm needs to find the appropriate position to insert based on priority. Other operations like dequeue, peek, isEmpty, and isSize have constant time complexity.

This implementation provides a basic understanding of implementing a priority queue using a doubly linked list and serves as a foundation for more efficient priority queue data structures.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.