Implementing a Custom Priority Queue in Java

 

In this article, we’ll cover a basic Priority Queue implementation in Java using custom code. We’ll explore the Java built-in PriorityQueue class as well, which provides a more efficient solution for real-world applications.

What is a Priority Queue?

A Priority Queue is a data structure where each element has a priority. Elements with higher priority are dequeued before elements with lower priority. If two elements have the same priority, they follow the order of insertion.

Code Implementation

Let’s implement a basic Priority Queue in Java using a List to hold elements and priorities. This example uses a min-heap approach, meaning elements with the lowest priority values come first.

Custom Priority Queue in Java

Here’s the code for a simple custom Priority Queue:

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

class PriorityQueue<T> {
    // Nested class to hold data and priority as a pair
    private static class Node<T> {
        int priority;
        T data;

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

    private final List<Node<T>> queue;

    public PriorityQueue() {
        queue = new ArrayList<>();
    }

    // Function to add an element with a specific priority
    public void enqueue(T data, int priority) {
        Node<T> newNode = new Node<>(data, priority);
        queue.add(newNode);

        // Sort based on priority (min-heap)
        queue.sort(Comparator.comparingInt(n -> n.priority));
    }

    // Function to remove and return the highest-priority element
    public T dequeue() {
        if (queue.isEmpty()) {
            System.out.println("Queue is empty! Cannot dequeue.");
            return null;
        }
        return queue.remove(0).data;
    }

    // Function to check if the queue is empty
    public boolean isEmpty() {
        return queue.isEmpty();
    }

    // Function to display all elements with their priorities
    public void display() {
        for (Node<T> node : queue) {
            System.out.println("Element: " + node.data + " | Priority: " + node.priority);
        }
    }
}

public class Main {
    public static void main(String[] args) {
        PriorityQueue<String> pq = new PriorityQueue<>();

        // Insert elements with priorities
        pq.enqueue("Task 1", 2);
        pq.enqueue("Task 2", 1);
        pq.enqueue("Task 3", 3);
        pq.enqueue("Task 4", 0);

        System.out.println("Priority Queue:");
        pq.display();

        System.out.println("\nDequeuing elements based on priority:");
        while (!pq.isEmpty()) {
            System.out.println("Dequeued: " + pq.dequeue());
        }
    }
}

Explanation of the Code

Let’s go through each section of this code to understand how it works.

1. The Node Class

The nested Node class stores:

• data: the element to store.
• priority: the priority level associated with the element.

2. The PriorityQueue Class

Our custom PriorityQueue class contains a List<Node<T>> to hold each element and its priority.

enqueue Method

public void enqueue(T data, int priority) {
    Node<T> newNode = new Node<>(data, priority);
    queue.add(newNode);
    queue.sort(Comparator.comparingInt(n -> n.priority));
}

• Adds a new Node with data and priority to the queue.
• Sorts the queue based on priority so that the lowest priority elements are at the front.

dequeue Method

public T dequeue() {
    if (queue.isEmpty()) {
        System.out.println("Queue is empty! Cannot dequeue.");
        return null;
    }
    return queue.remove(0).data;
}

• Removes and returns the element with the highest priority (lowest priority number).
• If the queue is empty, it returns null and prints an error message.

isEmpty Method

public boolean isEmpty() {
    return queue.isEmpty();
}

• Returns true if the queue is empty, false otherwise.

display Method

public void display() {
    for (Node<T> node : queue) {
        System.out.println("Element: " + node.data + " | Priority: " + node.priority);
    }
}

• Prints each element and its priority, allowing us to inspect the queue contents.

Summary

We’ve built a basic Priority Queue in Java using custom code to understand the fundamentals and then explored the more efficient PriorityQueue provided by Java. For applications where efficiency is key, the built-in PriorityQueue is recommended, as it is optimized for performance.

---

Happy coding! This guide should give you a solid foundation for working with Priority Queues in Java.