MACRO NEPAL
Queue Interface and PriorityQueue in Java
awiskar acharya
October 30, 2025
9:36 am

The Queue interface and PriorityQueue class provide FIFO (First-In-First-Out) and priority-based data structures in Java.

1. Queue Interface Basics

Queue Interface Definition and Methods

import java.util.*;
public class QueueInterfaceBasics {
public static void main(String[] args) {
// Queue is an interface, so we need a concrete implementation
Queue<String> queue = new LinkedList<>();
// Basic Queue operations
System.out.println("=== Basic Queue Operations ===");
// Add elements - offer() returns false if capacity restricted
queue.offer("First");
queue.offer("Second");
queue.offer("Third");
System.out.println("Queue after offers: " + queue);
// Add elements - add() throws exception if capacity restricted
queue.add("Fourth");
System.out.println("Queue after add: " + queue);
// Examine elements
System.out.println("Peek (examine head): " + queue.peek());
System.out.println("Element (examine head): " + queue.element());
// Remove elements
System.out.println("Poll (remove head): " + queue.poll());
System.out.println("Queue after poll: " + queue);
System.out.println("Remove (remove head): " + queue.remove());
System.out.println("Queue after remove: " + queue);
// Check queue status
System.out.println("Queue size: " + queue.size());
System.out.println("Is queue empty? " + queue.isEmpty());
// Process all elements
System.out.println("\nProcessing all elements:");
while (!queue.isEmpty()) {
String element = queue.poll();
System.out.println("Processing: " + element);
}
System.out.println("Final queue: " + queue);
}
}

Queue Implementations Comparison

import java.util.*;
public class QueueImplementations {
public static void main(String[] args) {
System.out.println("=== Queue Implementations Comparison ===");
// 1. LinkedList - general purpose FIFO queue
Queue<String> linkedListQueue = new LinkedList<>();
linkedListQueue.offer("A");
linkedListQueue.offer("B");
linkedListQueue.offer("C");
System.out.println("LinkedList Queue: " + linkedListQueue);
// 2. PriorityQueue - elements ordered by priority
Queue<String> priorityQueue = new PriorityQueue<>();
priorityQueue.offer("C");
priorityQueue.offer("A");
priorityQueue.offer("B");
System.out.println("PriorityQueue (natural order): " + getQueueContents(priorityQueue));
// 3. ArrayDeque - resizable array implementation
Queue<String> arrayDeque = new ArrayDeque<>();
arrayDeque.offer("X");
arrayDeque.offer("Y");
arrayDeque.offer("Z");
System.out.println("ArrayDeque: " + arrayDeque);
demonstrateQueueCharacteristics();
}
private static <E> String getQueueContents(Queue<E> queue) {
List<E> elements = new ArrayList<>();
Queue<E> temp = new LinkedList<>();
while (!queue.isEmpty()) {
E element = queue.poll();
elements.add(element);
temp.offer(element);
}
// Restore original queue
while (!temp.isEmpty()) {
queue.offer(temp.poll());
}
return elements.toString();
}
private static void demonstrateQueueCharacteristics() {
System.out.println("\n=== Queue Method Characteristics ===");
Queue<Integer> queue = new LinkedList<>();
// offer() vs add()
System.out.println("Using offer(): " + queue.offer(1)); // true
System.out.println("Using offer(): " + queue.offer(2)); // true
Queue<Integer> boundedQueue = new ArrayDeque<>(2); // Capacity 2
boundedQueue.offer(1);
boundedQueue.offer(2);
System.out.println("Offer to full queue: " + boundedQueue.offer(3)); // false
// peek() vs element()
System.out.println("Peek on empty queue: " + new LinkedList<>().peek()); // null
try {
System.out.println("Element on empty queue: " + new LinkedList<>().element()); // Exception
} catch (NoSuchElementException e) {
System.out.println("element() threw NoSuchElementException on empty queue");
}
// poll() vs remove()
System.out.println("Poll on empty queue: " + new LinkedList<>().poll()); // null
try {
System.out.println("Remove on empty queue: " + new LinkedList<>().remove()); // Exception
} catch (NoSuchElementException e) {
System.out.println("remove() threw NoSuchElementException on empty queue");
}
}
}

2. PriorityQueue Basics

PriorityQueue Natural Ordering

import java.util.*;
public class PriorityQueueBasics {
public static void main(String[] args) {
System.out.println("=== PriorityQueue with Natural Ordering ===");
// PriorityQueue with natural ordering (ascending)
PriorityQueue<Integer> pq = new PriorityQueue<>();
// Add elements in random order
pq.offer(50);
pq.offer(10);
pq.offer(30);
pq.offer(40);
pq.offer(20);
System.out.println("PriorityQueue contents (not necessarily in order): " + pq);
System.out.println("Size: " + pq.size());
// Process elements in priority order (ascending)
System.out.println("\nProcessing elements in priority order:");
while (!pq.isEmpty()) {
System.out.println("Next element: " + pq.poll());
}
// String natural ordering (lexicographical)
PriorityQueue<String> stringPQ = new PriorityQueue<>();
stringPQ.offer("Orange");
stringPQ.offer("Apple");
stringPQ.offer("Banana");
stringPQ.offer("Cherry");
System.out.println("\nString PriorityQueue (natural order):");
while (!stringPQ.isEmpty()) {
System.out.println("Next: " + stringPQ.poll());
}
demonstrateInternalStructure();
}
private static void demonstrateInternalStructure() {
System.out.println("\n=== PriorityQueue Internal Structure ===");
PriorityQueue<Integer> pq = new PriorityQueue<>();
// Add elements and show internal array
for (int i = 1; i <= 7; i++) {
pq.offer(i * 10);
System.out.println("After adding " + (i * 10) + ": " + pq);
// Note: toString doesn't show heap structure
}
System.out.println("\nPolling order demonstrates heap structure:");
while (!pq.isEmpty()) {
System.out.println("Polled: " + pq.poll() + ", Remaining: " + pq);
}
}
}

PriorityQueue with Custom Comparator

import java.util.*;
public class PriorityQueueCustomComparator {
public static void main(String[] args) {
System.out.println("=== PriorityQueue with Custom Comparators ===");
// 1. Reverse order (max-heap)
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
maxHeap.offer(10);
maxHeap.offer(50);
maxHeap.offer(30);
maxHeap.offer(20);
maxHeap.offer(40);
System.out.println("Max-Heap (descending order):");
while (!maxHeap.isEmpty()) {
System.out.println("Next: " + maxHeap.poll());
}
// 2. Custom comparator for strings by length
PriorityQueue<String> lengthPQ = new PriorityQueue<>(
Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder())
);
lengthPQ.offer("Apple");
lengthPQ.offer("Banana");
lengthPQ.offer("Cat");
lengthPQ.offer("Dog");
lengthPQ.offer("Elephant");
System.out.println("\nStrings by length then alphabetically:");
while (!lengthPQ.isEmpty()) {
System.out.println("Next: " + lengthPQ.poll());
}
// 3. Complex custom objects
demonstrateCustomObjects();
}
private static void demonstrateCustomObjects() {
System.out.println("\n=== Custom Objects in PriorityQueue ===");
class Task {
String name;
int priority; // 1 = highest priority
int duration; // minutes
Task(String name, int priority, int duration) {
this.name = name;
this.priority = priority;
this.duration = duration;
}
@Override
public String toString() {
return String.format("Task{name='%s', priority=%d, duration=%d}", 
name, priority, duration);
}
}
// Priority: lower number = higher priority, then shorter duration
Comparator<Task> taskComparator = Comparator
.comparingInt((Task t) -> t.priority)
.thenComparingInt(t -> t.duration);
PriorityQueue<Task> taskQueue = new PriorityQueue<>(taskComparator);
taskQueue.offer(new Task("Write report", 2, 120));
taskQueue.offer(new Task("Fix critical bug", 1, 60));
taskQueue.offer(new Task("Team meeting", 3, 90));
taskQueue.offer(new Task("Code review", 2, 30));
taskQueue.offer(new Task("Update docs", 3, 45));
System.out.println("Tasks in priority order:");
while (!taskQueue.isEmpty()) {
System.out.println("Next task: " + taskQueue.poll());
}
}
}

3. PriorityQueue Internal Working

Min-Heap and Max-Heap Implementation

import java.util.*;
public class PriorityQueueInternal {
public static void main(String[] args) {
System.out.println("=== PriorityQueue Internal Working (Min-Heap) ===");
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// Demonstrate heap structure during insertion
int[] elements = {15, 10, 20, 8, 12, 17, 25};
for (int element : elements) {
minHeap.offer(element);
System.out.printf("After inserting %2d: %s%n", element, minHeap);
printHeapStructure(minHeap);
}
System.out.println("\n=== Polling from Min-Heap ===");
while (!minHeap.isEmpty()) {
int polled = minHeap.poll();
System.out.printf("Polled %2d: %s%n", polled, minHeap);
if (!minHeap.isEmpty()) {
printHeapStructure(minHeap);
}
}
demonstrateMaxHeap();
}
private static void printHeapStructure(Queue<Integer> queue) {
if (queue instanceof PriorityQueue) {
System.out.print("Heap array: ");
// Note: This is for demonstration - actual internal array isn't directly accessible
PriorityQueue<Integer> pq = (PriorityQueue<Integer>) queue;
// We can only see the order through polling
}
System.out.println();
}
private static void demonstrateMaxHeap() {
System.out.println("\n=== Max-Heap Implementation ===");
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
int[] elements = {15, 10, 20, 8, 12, 17, 25};
for (int element : elements) {
maxHeap.offer(element);
System.out.printf("After inserting %2d: %s%n", element, maxHeap);
}
System.out.println("\nPolling from Max-Heap:");
while (!maxHeap.isEmpty()) {
System.out.println("Polled: " + maxHeap.poll() + ", Remaining: " + maxHeap);
}
}
}
// Custom PriorityQueue with logging
class LoggingPriorityQueue<E> extends PriorityQueue<E> {
public LoggingPriorityQueue() {
super();
}
public LoggingPriorityQueue(Comparator<? super E> comparator) {
super(comparator);
}
@Override
public boolean offer(E e) {
System.out.printf("OFFER: Adding element %s%n", e);
boolean result = super.offer(e);
System.out.printf("       Queue after offer: %s%n", this);
return result;
}
@Override
public E poll() {
System.out.println("POLL: Removing head element");
E result = super.poll();
System.out.printf("      Polled: %s, Queue after poll: %s%n", result, this);
return result;
}
@Override
public E peek() {
E result = super.peek();
System.out.printf("PEEK: Head element is %s%n", result);
return result;
}
public static void main(String[] args) {
LoggingPriorityQueue<Integer> pq = new LoggingPriorityQueue<>();
pq.offer(30);
pq.offer(10);
pq.offer(20);
pq.peek();
pq.poll();
pq.offer(5);
pq.poll();
pq.poll();
}
}

4. Real-World Use Cases

Task Scheduler with Priority

import java.util.*;
import java.time.*;
public class TaskScheduler {
static class Task implements Comparable<Task> {
private String id;
private String description;
private Priority priority;
private LocalDateTime scheduledTime;
private int estimatedMinutes;
enum Priority {
HIGH(1), MEDIUM(2), LOW(3);
private final int value;
Priority(int value) {
this.value = value;
}
public int getValue() {
return value;
}
}
public Task(String id, String description, Priority priority, 
LocalDateTime scheduledTime, int estimatedMinutes) {
this.id = id;
this.description = description;
this.priority = priority;
this.scheduledTime = scheduledTime;
this.estimatedMinutes = estimatedMinutes;
}
@Override
public int compareTo(Task other) {
// First by priority (HIGH first), then by scheduled time (earlier first)
int priorityCompare = Integer.compare(this.priority.getValue(), 
other.priority.getValue());
if (priorityCompare != 0) return priorityCompare;
return this.scheduledTime.compareTo(other.scheduledTime);
}
@Override
public String toString() {
return String.format("Task[%s]: %s (Priority: %s, Time: %s, Est: %d min)", 
id, description, priority, 
scheduledTime.format(DateTimeFormatter.ISO_LOCAL_TIME),
estimatedMinutes);
}
}
private PriorityQueue<Task> taskQueue;
public TaskScheduler() {
this.taskQueue = new PriorityQueue<>();
}
public void scheduleTask(Task task) {
taskQueue.offer(task);
System.out.println("Scheduled: " + task);
}
public Task getNextTask() {
return taskQueue.poll();
}
public Task peekNextTask() {
return taskQueue.peek();
}
public boolean hasPendingTasks() {
return !taskQueue.isEmpty();
}
public void processAllTasks() {
System.out.println("\n=== Processing All Tasks ===");
while (hasPendingTasks()) {
Task task = getNextTask();
System.out.println("Processing: " + task);
// Simulate task execution
try {
Thread.sleep(100); // Simulate work
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
break;
}
}
System.out.println("All tasks completed!");
}
public static void main(String[] args) {
TaskScheduler scheduler = new TaskScheduler();
LocalDateTime baseTime = LocalDateTime.now();
// Schedule tasks with different priorities and times
scheduler.scheduleTask(new Task("T1", "Fix critical bug", 
Task.Priority.HIGH, baseTime.plusMinutes(10), 30));
scheduler.scheduleTask(new Task("T2", "Write documentation", 
Task.Priority.LOW, baseTime.plusMinutes(5), 60));
scheduler.scheduleTask(new Task("T3", "Code review", 
Task.Priority.MEDIUM, baseTime.plusMinutes(15), 45));
scheduler.scheduleTask(new Task("T4", "Server maintenance", 
Task.Priority.HIGH, baseTime.plusMinutes(2), 120));
scheduler.scheduleTask(new Task("T5", "Team meeting", 
Task.Priority.MEDIUM, baseTime.plusMinutes(20), 90));
System.out.println("\nNext task to process: " + scheduler.peekNextTask());
// Process all tasks
scheduler.processAllTasks();
}
}

Hospital Emergency Room System

import java.util.*;
public class EmergencyRoom {
static class Patient implements Comparable<Patient> {
private String name;
private int age;
private Severity severity;
private LocalTime arrivalTime;
private String condition;
enum Severity {
CRITICAL(1), SERIOUS(2), MODERATE(3), MINOR(4);
private final int level;
Severity(int level) {
this.level = level;
}
public int getLevel() {
return level;
}
}
public Patient(String name, int age, Severity severity, LocalTime arrivalTime, String condition) {
this.name = name;
this.age = age;
this.severity = severity;
this.arrivalTime = arrivalTime;
this.condition = condition;
}
@Override
public int compareTo(Patient other) {
// First by severity (critical first), then by age (older first), then arrival time
int severityCompare = Integer.compare(this.severity.getLevel(), 
other.severity.getLevel());
if (severityCompare != 0) return severityCompare;
int ageCompare = Integer.compare(other.age, this.age); // Older patients first
if (ageCompare != 0) return ageCompare;
return this.arrivalTime.compareTo(other.arrivalTime);
}
@Override
public String toString() {
return String.format("Patient{name='%s', age=%d, severity=%s, condition='%s', arrived=%s}", 
name, age, severity, condition, arrivalTime);
}
}
private PriorityQueue<Patient> waitingRoom;
public EmergencyRoom() {
this.waitingRoom = new PriorityQueue<>();
}
public void admitPatient(Patient patient) {
waitingRoom.offer(patient);
System.out.println("Admitted: " + patient);
System.out.println("Waiting room size: " + waitingRoom.size());
}
public Patient treatNextPatient() {
Patient patient = waitingRoom.poll();
if (patient != null) {
System.out.println("Treating: " + patient);
}
return patient;
}
public void displayWaitingList() {
System.out.println("\n=== Current Waiting List (Priority Order) ===");
PriorityQueue<Patient> temp = new PriorityQueue<>(waitingRoom);
int position = 1;
while (!temp.isEmpty()) {
System.out.println(position++ + ". " + temp.poll());
}
}
public static void main(String[] args) {
EmergencyRoom er = new EmergencyRoom();
LocalTime baseTime = LocalTime.now();
// Patients arrive at emergency room
er.admitPatient(new Patient("John Doe", 45, Patient.Severity.MODERATE, 
baseTime.plusMinutes(10), "Broken arm"));
er.admitPatient(new Patient("Jane Smith", 70, Patient.Severity.SERIOUS, 
baseTime.plusMinutes(5), "Chest pain"));
er.admitPatient(new Patient("Bob Johnson", 35, Patient.Severity.CRITICAL, 
baseTime.plusMinutes(15), "Severe bleeding"));
er.admitPatient(new Patient("Alice Brown", 25, Patient.Severity.MINOR, 
baseTime.plusMinutes(2), "Minor cut"));
er.admitPatient(new Patient("Charlie Wilson", 80, Patient.Severity.SERIOUS, 
baseTime.plusMinutes(8), "Difficulty breathing"));
er.displayWaitingList();
// Treat patients in priority order
System.out.println("\n=== Treating Patients ===");
while (er.waitingRoom.peek() != null) {
er.treatNextPatient();
er.displayWaitingList();
}
}
}

5. Advanced PriorityQueue Features

PriorityQueue with Custom Heap Implementation

import java.util.*;
public class AdvancedPriorityQueue {
public static void main(String[] args) {
System.out.println("=== Advanced PriorityQueue Features ===");
// 1. PriorityQueue from existing collection
List<Integer> numbers = Arrays.asList(15, 3, 8, 20, 1, 12);
PriorityQueue<Integer> pqFromCollection = new PriorityQueue<>(numbers);
System.out.println("PQ from collection: " + getQueueContents(pqFromCollection));
// 2. PriorityQueue with initial capacity
PriorityQueue<String> pqWithCapacity = new PriorityQueue<>(20, Comparator.reverseOrder());
pqWithCapacity.addAll(Arrays.asList("A", "C", "B", "E", "D"));
System.out.println("PQ with capacity (reverse): " + getQueueContents(pqWithCapacity));
// 3. Bulk operations
demonstrateBulkOperations();
// 4. Iterator behavior
demonstrateIterator();
// 5. Thread safety considerations
demonstrateThreadSafety();
}
private static <E> String getQueueContents(Queue<E> queue) {
List<E> elements = new ArrayList<>();
Queue<E> temp = new LinkedList<>();
while (!queue.isEmpty()) {
E element = queue.poll();
elements.add(element);
temp.offer(element);
}
// Restore original queue
queue.addAll(temp);
return elements.toString();
}
private static void demonstrateBulkOperations() {
System.out.println("\n=== Bulk Operations ===");
PriorityQueue<Integer> pq = new PriorityQueue<>();
// Add multiple elements
pq.addAll(Arrays.asList(25, 10, 35, 5, 15));
System.out.println("After bulk add: " + getQueueContents(pq));
// Remove specific element
pq.remove(15);
System.out.println("After removing 15: " + getQueueContents(pq));
// Remove all elements matching condition
pq.removeIf(n -> n > 20);
System.out.println("After removing >20: " + getQueueContents(pq));
// Clear queue
pq.clear();
System.out.println("After clear, empty: " + pq.isEmpty());
}
private static void demonstrateIterator() {
System.out.println("\n=== Iterator Behavior ===");
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.addAll(Arrays.asList(30, 10, 20, 5, 15));
System.out.println("Queue: " + pq);
// Iterator doesn't guarantee priority order
System.out.println("Iteration order (not necessarily sorted):");
for (Integer num : pq) {
System.out.print(num + " ");
}
System.out.println();
// To process in priority order, must use poll()
System.out.println("Polling order (guaranteed sorted):");
while (!pq.isEmpty()) {
System.out.print(pq.poll() + " ");
}
System.out.println();
}
private static void demonstrateThreadSafety() {
System.out.println("\n=== Thread Safety Considerations ===");
// PriorityQueue is not thread-safe
PriorityQueue<Integer> unsafeQueue = new PriorityQueue<>();
// For thread-safe usage, use PriorityBlockingQueue or external synchronization
Queue<Integer> synchronizedQueue = Collections.synchronizedQueue(new PriorityQueue<>());
System.out.println("Use PriorityBlockingQueue for concurrent access");
System.out.println("Or wrap with Collections.synchronizedQueue()");
}
}
// Custom task with dynamic priority
class DynamicPriorityTask implements Comparable<DynamicPriorityTask> {
private String name;
private int basePriority;
private int waitTime; // minutes waiting
private LocalDateTime createdTime;
public DynamicPriorityTask(String name, int basePriority) {
this.name = name;
this.basePriority = basePriority;
this.waitTime = 0;
this.createdTime = LocalDateTime.now();
}
public void incrementWaitTime() {
this.waitTime++;
}
public int getDynamicPriority() {
// Priority increases with wait time
return basePriority - waitTime;
}
@Override
public int compareTo(DynamicPriorityTask other) {
return Integer.compare(this.getDynamicPriority(), other.getDynamicPriority());
}
@Override
public String toString() {
return String.format("Task{name='%s', basePriority=%d, waitTime=%d, dynamicPriority=%d}", 
name, basePriority, waitTime, getDynamicPriority());
}
public static void main(String[] args) {
PriorityQueue<DynamicPriorityTask> queue = new PriorityQueue<>();
queue.offer(new DynamicPriorityTask("Task A", 10));
queue.offer(new DynamicPriorityTask("Task B", 5));
queue.offer(new DynamicPriorityTask("Task C", 8));
System.out.println("Initial order:");
queue.forEach(System.out::println);
// Simulate waiting time increasing priorities
System.out.println("\nAfter wait time increases:");
for (DynamicPriorityTask task : queue) {
task.incrementWaitTime();
task.incrementWaitTime();
}
// Re-sort the queue (this is a limitation - we need to reinsert)
PriorityQueue<DynamicPriorityTask> newQueue = new PriorityQueue<>();
newQueue.addAll(queue);
newQueue.forEach(System.out::println);
}
}

6. Performance Analysis

Queue and PriorityQueue Performance

import java.util.*;
public class QueuePerformanceAnalysis {
private static final int TEST_SIZE = 100000;
public static void main(String[] args) {
System.out.println("Queue and PriorityQueue Performance Analysis");
System.out.println("Test Size: " + TEST_SIZE + " operations");
System.out.println("============================================");
testQueuePerformance();
testPriorityQueuePerformance();
compareImplementations();
}
public static void testQueuePerformance() {
System.out.println("\n=== Queue Implementations Performance ===");
// LinkedList as Queue
Queue<Integer> linkedListQueue = new LinkedList<>();
long start = System.nanoTime();
for (int i = 0; i < TEST_SIZE; i++) {
linkedListQueue.offer(i);
}
for (int i = 0; i < TEST_SIZE; i++) {
linkedListQueue.poll();
}
long end = System.nanoTime();
System.out.printf("LinkedList Queue: %.2f ms%n", (end - start) / 1_000_000.0);
// ArrayDeque as Queue
Queue<Integer> arrayDeque = new ArrayDeque<>();
start = System.nanoTime();
for (int i = 0; i < TEST_SIZE; i++) {
arrayDeque.offer(i);
}
for (int i = 0; i < TEST_SIZE; i++) {
arrayDeque.poll();
}
end = System.nanoTime();
System.out.printf("ArrayDeque Queue: %.2f ms%n", (end - start) / 1_000_000.0);
}
public static void testPriorityQueuePerformance() {
System.out.println("\n=== PriorityQueue Performance ===");
// PriorityQueue - sequential insertion
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
long start = System.nanoTime();
for (int i = 0; i < TEST_SIZE; i++) {
priorityQueue.offer(i);
}
long insertTime = System.nanoTime() - start;
start = System.nanoTime();
for (int i = 0; i < TEST_SIZE; i++) {
priorityQueue.poll();
}
long pollTime = System.nanoTime() - start;
System.out.printf("PriorityQueue sequential insert: %.2f ms%n", insertTime / 1_000_000.0);
System.out.printf("PriorityQueue sequential poll: %.2f ms%n", pollTime / 1_000_000.0);
// PriorityQueue - random insertion
priorityQueue.clear();
Random random = new Random();
start = System.nanoTime();
for (int i = 0; i < TEST_SIZE; i++) {
priorityQueue.offer(random.nextInt(TEST_SIZE));
}
insertTime = System.nanoTime() - start;
start = System.nanoTime();
while (!priorityQueue.isEmpty()) {
priorityQueue.poll();
}
pollTime = System.nanoTime() - start;
System.out.printf("PriorityQueue random insert: %.2f ms%n", insertTime / 1_000_000.0);
System.out.printf("PriorityQueue random poll: %.2f ms%n", pollTime / 1_000_000.0);
}
public static void compareImplementations() {
System.out.println("\n=== Implementation Comparison ===");
int size = 10000;
List<Integer> data = new ArrayList<>();
Random random = new Random();
for (int i = 0; i < size; i++) {
data.add(random.nextInt(size));
}
// PriorityQueue vs TreeSet (both sorted)
PriorityQueue<Integer> pq = new PriorityQueue<>();
TreeSet<Integer> treeSet = new TreeSet<>();
long start = System.nanoTime();
pq.addAll(data);
long pqInsert = System.nanoTime() - start;
start = System.nanoTime();
treeSet.addAll(data);
long treeSetInsert = System.nanoTime() - start;
start = System.nanoTime();
while (!pq.isEmpty()) {
pq.poll();
}
long pqRemove = System.nanoTime() - start;
start = System.nanoTime();
while (!treeSet.isEmpty()) {
treeSet.pollFirst();
}
long treeSetRemove = System.nanoTime() - start;
System.out.printf("PriorityQueue insert %d elements: %.2f ms%n", 
size, pqInsert / 1_000_000.0);
System.out.printf("TreeSet insert %d elements: %.2f ms%n", 
size, treeSetInsert / 1_000_000.0);
System.out.printf("PriorityQueue remove all: %.2f ms%n", pqRemove / 1_000_000.0);
System.out.printf("TreeSet remove all: %.2f ms%n", treeSetRemove / 1_000_000.0);
}
}

Summary

Queue Interface Key Points:

  1. FIFO Principle: First-In-First-Out data structure
  2. Core Methods:
  • offer()/add() - Add elements
  • poll()/remove() - Remove and return head
  • peek()/element() - Examine head without removal
  1. Implementations: LinkedList, ArrayDeque, PriorityQueue
  2. Thread Safety: Not thread-safe by default

PriorityQueue Key Points:

  1. Heap Implementation: Min-heap by default (natural ordering)
  2. Custom Ordering: Supports comparators for custom sorting
  3. Time Complexity:
  • offer(): O(log n)
  • poll(): O(log n)
  • peek(): O(1)
  • remove(Object): O(n)
  1. No Null Elements: Doesn't allow null elements
  2. Iterator Order: Doesn't guarantee sorted order traversal

Use Cases:

  1. Task Scheduling: Process tasks by priority
  2. Event Systems: Handle events in priority order
  3. Simulations: Process entities by priority
  4. Algorithms: Dijkstra's algorithm, Huffman coding
  5. Resource Management: Allocate resources by priority

Best Practices:

  1. Choose appropriate implementation based on usage patterns
  2. Use custom comparators for complex ordering logic
  3. Consider PriorityBlockingQueue for concurrent access
  4. Avoid modifying elements that affect ordering while in queue
  5. Use for priority-based processing rather than simple FIFO

Queue and PriorityQueue are essential tools for managing ordered data processing in Java applications, with PriorityQueue providing efficient priority-based ordering through its heap implementation.

Category : JAVA

Leave a Reply

Your email address will not be published. Required fields are marked *


Macro Nepal Helper