Priority Queue

A priority queue is an abstract data structure and it is similar to the regular queue. Each element in the priority queue has a priority associated with it. In the priority queue, we dequeue the highest priority element before the lowest priority and if the priority is the same then as per the insertion order it will dequeue. One of the best real-time applications, CPU Scheduling is basically done the same thing. If the higher priority task occurs then it interrupts the ongoing process and shares the resources to the higher priority. We have taken the example of RabbitMq in the queue blog. In RabbitMq, we push elements in the queue and wait until the subscriber subscribes to the messages. Suppose, If there are n messages that are pending to subscribe and one of the messages needs to be processed as soon as possible. If we have pushed the message by setting the high priority in the queue then it will process first then rest of them.

Some of the languages implement the priority queue but it uses the element to compare the priority. Suppose you have created a priority queue with 2 elements then the highest element values become the highest priority in the queue a reassigned the position to front and lowest priority value will be reassigned to rear. 

We ask the user to pass the priority value and then we assign it to the right to the position based on it. We will implement it with the help of the Linked List. In Priority Queue, the front will hold the highest priority and rear will hold the lowest priority element.

NOTE: - Generic <T> type can accept any data type, If you have not passed explicitly then it will consider it as an Object.

Priority Queue Implementation using Linked List

#1 Initialization of Priority Queue - O(1)

public class CustomPriorityQueue<T> {
    Node<T> front, rear;
    int length = 0;
    class Node<T> {
       T data;
       Node<T> next;
       int priority;

       public Node(T data, int priority) {
           this.data = data;
           this.priority = priority;
       }

       public Node() {
       }

       public Node(T data, Node<T> next, int priority) {
           this.data = data;
           this.next = next;
           this.priority = priority;
       }
   }
}

#2 Enqueue an element - O(n)

public void enqueue(T data, int priority) {
    Node<T> node= new Node<>(data, priority);
    if (front == null) {
        front = rear = node;
    } else {
        Node<T> ref = front;
        if (ref.priority < priority) {
            node.next = front;
            front = node;
        } else {
            while (ref.next != null && ref.next.priority >= priority) {
                ref = ref.next;
            }
            Node<T> tempRef = ref.next;
            ref.next = node;
            node.next = tempRef;
            if (ref == rear)
                rear = node;
        }
    }
    length++;
}

#3 Deque an element - O(1)

public void dequeue() {
    if (length == 0)
        throw new NoSuchElementException();
    front = front.next;
    length--;
}

#4 Peek an element - O(1)

public T peek() {
    if (length == 0)
        throw new NoSuchElementException();
    return front.data;
}

#5 Clear All Priority Queue

public void clear() {
    front = rear = null;
    length = 0;
}