Sample Java Code: Implementing a Priority Queue with LinkedList for AP CS A

📚 Understanding Priority Queues

A priority queue is an abstract data type similar to a regular queue or stack data structure, but where each element additionally has a "priority" associated with it. In a priority queue, elements are served based on their priority. Higher priority elements are served before lower priority elements, regardless of their insertion order. If elements have the same priority, they are served according to their order in the queue.

📜 History and Background

The concept of priority queues dates back to the early days of computer science, arising from the need to efficiently manage tasks or events based on importance. The implementation using data structures like heaps and linked lists evolved over time to optimize performance.

🔑 Key Principles of Implementation

• ⏱️ Ordering: Elements are ordered based on their priority.
• 🔄 Insertion: New elements are inserted into the queue while maintaining the priority order.
• 📤 Removal: The element with the highest priority is removed first.
• 🔎 Peek: Allows viewing the highest priority element without removing it.

💻 Sample Java Code with LinkedList

Below is a sample Java implementation of a priority queue using a LinkedList. This example provides a basic understanding of how to manage elements with priorities.

import java.util.LinkedList;

public class PriorityQueueLinkedList {

    private LinkedList tasks = new LinkedList<>();

    public void enqueue(Task task) {
        if (tasks.isEmpty()) {
            tasks.add(task);
        } else {
            int i = 0;
            while (i < tasks.size() && task.priority >= tasks.get(i).priority) {
                i++;
            }
            tasks.add(i, task);
        }
    }

    public Task dequeue() {
        return tasks.removeFirst();
    }

    public Task peek() {
        return tasks.getFirst();
    }

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

    public int size() {
        return tasks.size();
    }

    static class Task {
        String name;
        int priority;

        public Task(String name, int priority) {
            this.name = name;
            this.priority = priority;
        }

        @Override
        public String toString() {
            return "Task{" + "name='" + name + '\'' + ", priority=" + priority + '}';
        }
    }

    public static void main(String[] args) {
        PriorityQueueLinkedList priorityQueue = new PriorityQueueLinkedList();

        priorityQueue.enqueue(new Task("Low Priority Task", 1));
        priorityQueue.enqueue(new Task("High Priority Task", 3));
        priorityQueue.enqueue(new Task("Medium Priority Task", 2));

        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.dequeue());
        }
    }
}

💡 Code Explanation

• ➕ Enqueue: Adds a new task to the queue based on its priority. The task is inserted at the correct position to maintain priority order.
• ➖ Dequeue: Removes and returns the task with the highest priority (the first element in the LinkedList).
• 👀 Peek: Returns the task with the highest priority without removing it.
• ✅ isEmpty: Checks if the queue is empty.
• 📏 Size: Returns the number of tasks in the queue.

⚙️ Real-world Examples

• 🏥 Hospital Emergency Room: Patients are treated based on the severity of their condition (priority).
• 🖥️ Operating System Task Scheduling: Processes are executed based on their priority level.
• ✈️ Airline Boarding: Passengers with higher priority (e.g., first-class) board before others.

📝 Conclusion

Implementing a priority queue using a LinkedList in Java provides a practical way to manage elements with associated priorities. While LinkedLists might not be the most efficient for large-scale applications due to their linear time complexity for certain operations, they offer simplicity and ease of understanding, making them suitable for educational purposes and smaller applications.