Skip to main content

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
    Adjust pointers and size

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;
			}
			// Add node
			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();
	// Add queue element
	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;
			}
			// Add node
			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();
		// Add queue element
		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;
			}
			// Add node
			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();
	// Add queue element
	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;
			}
			// Add node
			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();
		// Add queue element
		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;
			}
			// Add node
			$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();
	// Add queue element
	$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;
			}
			// Add node
			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();
	// Add queue element
	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
			
			#  Add node
			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()
	#  Add queue element
	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_reader :data, :next, :prev
	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_reader :front, :rear, :size
	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

			#  Add node
			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()
	#  Add queue element
	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;
			}
			// Add node
			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();
		// Add queue element
		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;
			}
			// Add node
			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();
	// Add queue element
	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;
			}
			// Add node
			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();
	// Add queue element
	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.

Last updated on by Kalkicode




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.

New Comment