Queue Interface and PriorityQueue in Java

The Queue interface in Java represents a collection that holds elements waiting to be processed. Most queues work in first-in, first-out (FIFO) order, like people standing in a line at a ticket counter. PriorityQueue is a special queue that always hands out the element with the highest priority first (by default, the smallest), no matter when it was added. In this lesson, you will learn the methods of Queue and how to use PriorityQueue.

Declaration

public interface Queue<E> extends Collection<E>
public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable

Methods of Queue

Each queue operation comes in two forms: one that throws an exception when it fails, and one that returns a special value instead.

In practice, offer, poll and peek are used most, because an empty queue is a normal situation, not an error.

Example: A FIFO Queue

Let's see an example of a ticket counter line.

import java.util.ArrayDeque;
import java.util.Queue;
 
public class TicketLine {
    public static void main(String[] args) {
        Queue<String> line = new ArrayDeque<>();
        line.offer("Navika");
        line.offer("Srihitha");
        line.offer("Advitha");
        System.out.println("Line: " + line);
        System.out.println("Next: " + line.peek());
 
        while (!line.isEmpty()) {
            System.out.println("Serving " + line.poll());
        }
        System.out.println("poll on empty: " + line.poll());
    }
}

Line: [Navika, Srihitha, Advitha]
Next: Navika
Serving Navika
Serving Srihitha
Serving Advitha
poll on empty: null

Explanation: offer adds each person to the tail. peek shows who is next without removing them. poll removes from the head, so people are served in the order they arrived. On an empty queue, poll returns null instead of throwing.

PriorityQueue

A PriorityQueue doesn't serve in arrival order. It always gives out the smallest element according to natural order, or the first according to a comparator. Inside, it uses a binary heap: a tree stored in an array where every parent is smaller than its children.

Features of PriorityQueue

• Serves the smallest first (or the highest priority, using a comparator).
• offer and poll take O(log n); peek takes O(1).
• No null elements.
• Printing or iterating doesn't show sorted order. Only poll returns elements in priority order.
• Not synchronized.

Example: Hospital Triage with a Comparator

import java.util.Comparator;
import java.util.PriorityQueue;
 
public class Triage {
    record Patient(String name, int severity) { }
 
    public static void main(String[] args) {
        PriorityQueue<Patient> queue = new PriorityQueue<>(
            Comparator.comparingInt(Patient::severity).reversed());
 
        queue.offer(new Patient("Navika", 2));
        queue.offer(new Patient("Srihitha", 5));
        queue.offer(new Patient("Advitha", 3));
 
        while (!queue.isEmpty()) {
            Patient p = queue.poll();
            System.out.println(p.name() + " (severity " + p.severity() + ")");
        }
    }
}

Srihitha (severity 5)
Advitha (severity 3)
Navika (severity 2)

Explanation: The comparator orders patients by severity from highest to lowest, so the most serious case is always polled first, even though Srihitha arrived second.

Example: The Three Smallest Numbers

import java.util.List;
import java.util.PriorityQueue;
 
public class Smallest {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(
            List.of(40, 10, 30, 20, 50));
        System.out.println("Printed: " + pq);
        System.out.print("Polled:  ");
        for (int i = 0; i < 3; i++) {
            System.out.print(pq.poll() + (i < 2 ? ", " : "\n"));
        }
    }
}

Printed: [10, 20, 30, 40, 50]
Polled:  10, 20, 30

Explanation: poll returns the numbers from smallest up. The printed form happens to look sorted here, but in general it shows the internal heap array, which is not guaranteed to be sorted.

Common Mistakes

Expecting PriorityQueue to be FIFO. It serves by priority, not arrival.

Printing a PriorityQueue to check its order. The heap layout isn't sorted.

Using remove() or element() on a queue that may be empty. They throw NoSuchElementException; use poll and peek.

Interview Corner

Practice

1. Easy: Simulate a printer queue with an ArrayDeque: add five jobs, print three, and show what's left.
2. Harder: Use a PriorityQueue to find the 3 largest numbers in a list of 10, keeping at most 3 elements in the queue at any time.

Key Takeaways