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.

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.

  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 + " ");
      }
    }
  }