Java Program to Implement a Priority Queue

Introduction

A priority queue is a special type of queue in which each element is associated with a priority. Elements with higher priorities are dequeued before elements with lower priorities. If two elements have the same priority, they are dequeued according to their order in the queue. This guide will walk you through writing a Java program that implements a priority queue using an array.

Problem Statement

Create a Java program that:

Implements a priority queue using an array.
Provides methods to perform standard priority queue operations: enqueue, dequeue, peek, isEmpty, and isFull.
Displays the queue contents after various operations.

Example:

Input: Enqueue elements with priorities: (10, 2), (20, 1), (30, 3)
Operations: enqueue(40, 2), dequeue(), peek()
Output:
- After enqueuing: [(30, 3), (10, 2), (40, 2), (20, 1)]
- After dequeuing: [(10, 2), (40, 2), (20, 1)]
- Peeked element: (10, 2)

Solution Steps

Create the Priority Queue Structure: Define a PriorityQueue class to represent the queue, including methods for standard queue operations.
Implement Queue Operations: Implement methods to enqueue elements with a priority into the queue, dequeue elements from the queue, peek at the highest-priority element, and check if the queue is empty or full.
Handle Edge Cases: Ensure the queue handles underflow (dequeuing from an empty queue) and overflow (enqueuing to a full queue) conditions.
Display the Queue: Output the queue’s contents after performing various operations.

Java Program

// Java Program to Implement a Priority Queue // Author: https://www.rameshfadatare.com/ class PriorityQueue { private int maxSize; private int[] queueArray; private int[] priorityArray; private int nItems; // Constructor to initialize the priority queue public PriorityQueue(int size) { maxSize = size; queueArray = new int[maxSize]; priorityArray = new int[maxSize]; nItems = 0; } // Method to enqueue an element into the priority queue with a given priority public void enqueue(int value, int priority) { if (isFull()) { System.out.println("Priority Queue is full. Unable to enqueue " + value); return; } int i; // If the queue is empty, insert the first element if (nItems == 0) { queueArray[0] = value; priorityArray[0] = priority; } else { // Shift elements to the right to make room for the new element based on its priority for (i = nItems - 1; i >= 0; i--) { if (priority > priorityArray[i]) { queueArray[i + 1] = queueArray[i]; priorityArray[i + 1] = priorityArray[i]; } else { break; } } // Insert the new element at the correct position queueArray[i + 1] = value; priorityArray[i + 1] = priority; } nItems++; System.out.println("Enqueued " + value + " with priority " + priority + " into the queue."); } // Method to dequeue an element from the priority queue public int dequeue() { if (isEmpty()) { System.out.println("Priority Queue is empty. Unable to dequeue."); return -1; // Return a sentinel value indicating the queue is empty } // Remove the element with the highest priority (the first element in the array) int dequeuedValue = queueArray[--nItems]; System.out.println("Dequeued " + dequeuedValue + " from the queue."); return dequeuedValue; } // Method to peek at the element with the highest priority public int peek() { if (isEmpty()) { System.out.println("Priority Queue is empty. Nothing to peek."); return -1; // Return a sentinel value indicating the queue is empty } else { System.out.println("Peeked at the highest priority element: " + queueArray[nItems - 1]); return queueArray[nItems - 1]; } } // Method to check if the priority queue is empty public boolean isEmpty() { return (nItems == 0); } // Method to check if the priority queue is full public boolean isFull() { return (nItems == maxSize); } // Method to display the contents of the priority queue public void display() { if (isEmpty()) { System.out.println("Priority Queue is empty."); } else { System.out.print("Priority Queue contents: "); for (int i = 0; i < nItems; i++) { System.out.print("(" + queueArray[i] + ", " + priorityArray[i] + ") "); } System.out.println(); } } } public class PriorityQueueDemo { public static void main(String[] args) { PriorityQueue queue = new PriorityQueue(5); // Create a priority queue with a maximum size of 5 // Enqueue elements into the priority queue queue.enqueue(10, 2); queue.enqueue(20, 1); queue.enqueue(30, 3); queue.display(); // Enqueue another element queue.enqueue(40, 2); queue.display(); // Dequeue an element from the priority queue queue.dequeue(); queue.display(); // Peek at the highest priority element queue.peek(); queue.display(); // Attempt to enqueue more elements to test overflow queue.enqueue(50, 1); queue.enqueue(60, 4); // This will be enqueued with the highest priority queue.display(); // Dequeue all elements to test underflow queue.dequeue(); queue.dequeue(); queue.dequeue(); queue.dequeue(); // This dequeue should trigger an underflow condition queue.display(); } }

Explanation

Step 1: Initialize the PriorityQueue Class

The PriorityQueue class represents the priority queue, including methods for standard queue operations.
The queue is represented by two arrays: queueArray to store the elements and priorityArray to store the corresponding priorities. The maxSize defines the maximum capacity of the queue, and nItems keeps track of the number of elements in the queue.

Step 2: Implement Queue Operations

Enqueue: Adds an element to the queue based on its priority. The queue is kept sorted by priority, with higher-priority elements appearing before lower-priority ones. If the queue is full, an appropriate message is displayed.
Dequeue: Removes and returns the element with the highest priority (which is always at the end of the array). If the queue is empty, an appropriate message is displayed.
Peek: Returns the element with the highest priority without removing it. If the queue is empty, an appropriate message is displayed.
isEmpty: Checks if the queue is empty by verifying if nItems is 0.
isFull: Checks if the queue is full by verifying if nItems is equal to maxSize.
Display: Prints all elements currently in the queue along with their priorities.

Output Example

Enqueued 10 with priority 2 into the queue. Enqueued 20 with priority 1 into the queue. Enqueued 30 with priority 3 into the queue. Priority Queue contents: (30, 3) (10, 2) (20, 1) Enqueued 40 with priority 2 into the queue. Priority Queue contents: (30, 3) (10, 2) (40, 2) (20, 1) Dequeued 20 from the queue. Priority Queue contents: (30, 3) (10, 2) (40, 2) Peeked at the highest priority element: 40 Priority Queue contents: (30, 3) (10, 2) (40, 2) Enqueued 50 with priority 1 into the queue. Enqueued 60 with priority 4 into the queue. Priority Queue contents: (60, 4) (30, 3) (10, 2) (40, 2) (50, 1) Dequeued 50 from the queue. Dequeued 40 from the queue. Dequeued 10 from the queue. Dequeued 30 from the queue. Priority Queue is empty. Unable to dequeue. Priority Queue is empty.

Example with Different Queue Size

If you modify the queue size to 3:

PriorityQueue queue = new PriorityQueue(3); // Create a priority queue with a maximum size of 3

The output will adjust accordingly, demonstrating the queue’s overflow condition when more than 3 elements are enqueued.

Conclusion

This Java program demonstrates how to implement a priority queue using an array, including handling overflow and underflow conditions. The program efficiently manages queue operations, prioritizing elements based on their priority values. This exercise is valuable for understanding how to implement and manipulate priority queues in Java programming.