Implementation of Priority Queue using Linked List in Java

priority queue using linked list

Implementation of Priority Queue using Linked List in Java

Normal queue follows a First In First Out (FIFO) order to insert and remove an element. However, in a priority queue, an item with the highest priority comes out first. 

Every element in the priority queue is associated with a priority. It does not matter in which order we insert the items in the queue, the item with higher priority must be removed before the item with the lower priority. If the two items have same priorities, the order of removal is not defined and depends on implementation.

Let us look into real world example :

Have you ever seen in bank line that the higher priority is given to the disabled person then elderly person then comes normal person .In same way priority queue is functioned . 

OPERATIONS IN PRIORITY QUEUE :

  • insert(): This function is used to insert a new data into the queue.
  • delete(): This function removes the element with the highest priority form the queue.
  • peek() : This function is used to get the highest priority element in the queue without removing it from the queue.

ALGORITHM:

For Insertion :
  • START
  • USE FUNCTION INSERT
static Node insert(Node head, int d, int p) 
{ 
  Node start = (head); 
  
  // Create new Node 
  Node tp = newNode(d, p); 
  
  
  if ((head).prioritydata > p) { 
  
    // Insert New Node before head 
    tp.link = head; 
    (head) = tp; 
  } 
  else { 
  
    while (start.link != null && 
      start.link.prioritydata < p) { 
      start = start.link; 
    } 
  
    tp.link = start.link; 
    start.link = tp; 
  } 
  return head; 
}
  • END
For Deletion :
  • START
  • USE FUNCTION DELETE
 
static Node delete(Node head) 
{ 
  Node tp = head; 
  (head) = (head).link; 
  return head; 
}
  • END

JAVA CODE :

// Java program for  Priority Queue 
// using Linked List 
import java.util.* ; 

class prepinsta 
  
  
 
static class Node { 
  int data
  
  
  int prioritydata
  
  Node link
  

static Node node = new Node(); 
  

static Node newNode(int dint p
  Node tp = new Node(); 
  tp.data = d; 
  tp.prioritydata = p; 
  tp.link = null
  
  return tp; 
  
// Return the value at head 
static int peek(Node head
  return (head).data
  
//delete the element with the high priority

static Node delete(Node head
  Node tp = head; 
  (head) = (head).link
  return head; 
  
// Function to insert element
static Node insert(Node headint dint p
  Node start = (head); 
  
  // Create new Node 
  Node tp = newNode(d, p); 
  
  
  if ((head).prioritydata > p) { 
  
    // Insert New Node before head 
    tp.link = head; 
    (head) = tp; 
  } 
  else { 
  
    while (start.link != null && 
      start.link.prioritydata < p) { 
      start = start.link
    } 
  
    tp.link = start.link
    start.link = tp; 
  } 
  return head; 
  
// Function to check is list is empty 
static int isEmpty(Node head
  return ((head) == null)?1:0
  
// Driver code 
public static void main(String args[]) 
  // Create a Priority Queue 
  // 20 and 40 and 60 and 80 
  Node pq = newNode(401); 
  pq =insert(pq, 802); 
  pq =insert(pq, 603); 
  pq =insert(pq, 200); 
  
  while (isEmpty(pq)==0) { 
    System.out.printf(peek(pq)); 
    pq=delete(pq); 
  } 
  


OUTPUT:

20 40 60 80