Difference Between Priority Queue and Queue Implementation in Java

A Queue is a linear data structure to store and manipulate the data elements. A queue follows the concept of "First in, First out" (FIFO), where the first element inserted into the queue is the first one to be deleted from the queue.

A queue is open at both ends which enables insert operations to be performed at one end called REAR or TAIL and delete operations to be performed at another end called FRONT or HEAD.

What is a Priority Queue in Data Structure?

A priority queue is one particular kind of queue where each element of a queue is associated with a priority value, and elements are processed according to their priority, which means higher-priority elements are processed first.

Characteristics of a Priority queue:

• Each element in a priority queue is assigned a priority.
• An element with high priority is dequeued before one with low priority.
• Elements are processed in their order if they have the same priority.

Assigning priority value in a priority queue

In most cases, the element's value is taken into consideration for assigning the priority. As an illustration,

The highest priority element is the one with the highest value. In some situations, on the other hand, we can assume the element with the lowest value as the highest priority element. Setting priorities based on our requirements is also possible in the Priority Queue.

Difference between Priority Queue and Normal Queue

A priority queue is a type of normal queue used to store and manipulate the data elements. The major difference between both is -

A normal queue follows the concept of "First in, First out" (FIFO), where the first element inserted into the queue is the first one to be deleted from the queue, whereas a priority queue processes elements based on their priority, which means higher-priority elements are processed first.

Priority Queue Implementation

We can implement a priority queue using an array, a linked list, a heap data structure, or a binary search tree. Heap data structures are more preferred as compared to other data structures because heap data structures provide an efficient way to implement priority queues.

Given a simple example of Priority Queue in Java.

public class PriorityQueue {

  final int MAX;
  int[] intArray;
  int count;

  // Constructor
  public PriorityQueue(int size) {
    MAX = size;
    intArray = new int[MAX];
    count = 0;
  }

  // Method to insert an element into the PriorityQueue
  void insert(int data) {
    int i = 0;

    if (!isFull()) {
      // if queue is empty, insert the data
      if (count == 0) {
        intArray[count++] = data;
      } else {
        // start from the right end of the queue
        for (i = count - 1; i >= 0; i--) {
          // if data is larger, shift existing item to right end
          if (data > intArray[i]) {
            intArray[i + 1] = intArray[i];
          } else {
            break;
          }
        }
        // insert the data
        intArray[i + 1] = data;
        count++;
      }
    }
  }

  // Method to delete an element
  public int remove() {
    return intArray[--count];
  }

  // Method to peek an element
  public int peek() {
    return intArray[count - 1];
  }

  // Method to check Priority Queue is empty
  boolean isEmpty() {
    return count == 0;
  }

  // Method to check PriorityQueue is full
  boolean isFull() {
    return count == MAX;
  }

  // Method to return the size of the Priority Queue
  int size() {
    return count;
  }

  public static void main(String[] args) {
    // Create a Priority Queue
    PriorityQueue queue = new PriorityQueue(5);

    // Inserting an elements into the queue
    queue.insert(25);
    queue.insert(55);
    queue.insert(45);
    queue.insert(35);
    queue.insert(15);

    // Checking queue is full
    if (queue.isFull()) {
      System.out.println("Queue is full.");
    }

    // Remove an element from the queue
    int value = queue.remove();
    System.out.println("Element removed from the Priority Queue: " + value);

    System.out.println("Element at front: " + queue.peek());
    System.out.println("--------------------");
    System.out.println("index : 4 3 2  1  0");
    System.out.println("--------------------");
    System.out.print("Queue:  ");

    while (!queue.isEmpty()) {
      int n = queue.remove();
      System.out.print(n + " ");
    }
  }
}

Queue is full.
Element removed from the Priority Queue: 15
Element at front: 25
--------------------
index : 4 3 2  1  0
--------------------
Queue:  25 35 45 55