Queue & PriorityQueue

A Queue models a line: elements enter at the back and leave from the front — just like a checkout queue at a store. Java’s PriorityQueue adds a twist: elements leave in priority order rather than arrival order, making it the ideal structure for scheduling tasks, Dijkstra’s algorithm, and any “process the most important thing first” scenario.

The Queue Interface

Queue<E> lives in java.util and extends the Collection interface. It declares a small, carefully designed API split into two flavour pairs: methods that throw an exception on failure, and methods that return a special value instead.

Operation	Throws on failure	Returns value
Insert	add(e)	offer(e) → false
Remove head	remove()	poll() → null
Inspect head	element()	peek() → null

Tip: Prefer offer, poll, and peek in production code. They never throw NoSuchElementException, so your code stays predictable when the queue is empty.

Common Queue Implementations

Class	Ordering	Thread-safe?
LinkedList	FIFO	No
ArrayDeque	FIFO (faster)	No
PriorityQueue	Natural / Comparator	No
LinkedBlockingQueue	FIFO	Yes
PriorityBlockingQueue	Priority	Yes

Using LinkedList as a Queue

LinkedList implements both List and Deque, so it works as a plain FIFO queue out of the box.

import java.util.LinkedList;
import java.util.Queue;

public class SimpleQueue {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();

        queue.offer("Alice");
        queue.offer("Bob");
        queue.offer("Charlie");

        System.out.println("Head: " + queue.peek());   // look without removing
        System.out.println("Removed: " + queue.poll()); // remove head
        System.out.println("Queue now: " + queue);
    }
}

Output:

Head: Alice
Removed: Alice
Queue now: [Bob, Charlie]

PriorityQueue

PriorityQueue<E> stores elements in a heap so the smallest (by natural ordering) or highest-priority element is always at the head. It does not guarantee FIFO ordering among elements of equal priority.

Natural Ordering

import java.util.PriorityQueue;

public class NaturalOrder {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.offer(40);
        pq.offer(10);
        pq.offer(30);
        pq.offer(20);

        while (!pq.isEmpty()) {
            System.out.print(pq.poll() + " ");
        }
    }
}

Output:

10 20 30 40 

Even though you inserted 40 first, poll() always returns the smallest element. That is the min-heap behaviour.

Custom Ordering with a Comparator

Pass a Comparator to reverse the order or compare by any field:

import java.util.PriorityQueue;
import java.util.Comparator;

public class MaxHeap {
    public static void main(String[] args) {
        // max-heap: largest element at the head
        PriorityQueue<Integer> maxPQ =
            new PriorityQueue<>(Comparator.reverseOrder());

        maxPQ.offer(40);
        maxPQ.offer(10);
        maxPQ.offer(30);

        while (!maxPQ.isEmpty()) {
            System.out.print(maxPQ.poll() + " ");
        }
    }
}

Output:

40 30 10 

Priority Queue with Custom Objects

import java.util.PriorityQueue;

public class TaskScheduler {
    record Task(String name, int priority) {}

    public static void main(String[] args) {
        PriorityQueue<Task> tasks = new PriorityQueue<>(
            (a, b) -> Integer.compare(a.priority(), b.priority())
        );

        tasks.offer(new Task("Send email",   3));
        tasks.offer(new Task("Fix bug",      1));  // highest priority
        tasks.offer(new Task("Code review",  2));

        while (!tasks.isEmpty()) {
            Task t = tasks.poll();
            System.out.println("Processing: " + t.name() + " (priority " + t.priority() + ")");
        }
    }
}

Output:

Processing: Fix bug (priority 1)
Processing: Code review (priority 2)
Processing: Send email (priority 3)

Note: record was introduced in Java 16. If you’re on an older version, replace it with a regular class implementing the same fields.

Key PriorityQueue Methods

Method	Description
offer(e)	Inserts element; returns false if not possible
poll()	Removes and returns the head; null if empty
peek()	Returns (not removes) the head; null if empty
size()	Number of elements
contains(o)	O(n) linear scan
toArray()	Snapshot array; order is not sorted
clear()	Removes all elements

Warning: Iterating over a PriorityQueue with a for-each loop does not yield elements in priority order. Always use poll() in a loop to drain in priority order.

import java.util.PriorityQueue;

public class IterationDemo {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.offer(5); pq.offer(1); pq.offer(3);

        // NOT guaranteed sorted order:
        System.out.println("forEach: " + pq);  // e.g. [1, 5, 3]

        // Sorted order via poll():
        System.out.print("poll order: ");
        while (!pq.isEmpty()) System.out.print(pq.poll() + " ");
    }
}

Output:

forEach: [1, 5, 3]
poll order: 1 3 5 

ArrayDeque as a Queue

For pure FIFO needs without priority, ArrayDeque is faster than LinkedList because it avoids node allocation overhead. It implements the Deque interface (double-ended queue), which extends Queue.

import java.util.ArrayDeque;
import java.util.Queue;

public class ArrayDequeQueue {
    public static void main(String[] args) {
        Queue<String> queue = new ArrayDeque<>();
        queue.offer("first");
        queue.offer("second");
        queue.offer("third");

        System.out.println(queue.poll()); // first
        System.out.println(queue.poll()); // second
    }
}

Output:

first
second

Under the Hood

PriorityQueue’s Binary Heap

PriorityQueue internally stores elements in a resizable Object[] array that represents a binary min-heap:

• The root (index 0) is always the smallest element.
• For a node at index i, its children are at 2i+1 and 2i+2.
• offer(e) appends to the end then sifts up — O(log n).
• poll() swaps the root with the last element, shrinks the array, then sifts down — O(log n).
• peek() just reads index 0 — O(1).
• contains() is O(n) because the heap makes no guarantee about sibling ordering.

The default initial capacity is 11. Like ArrayList, capacity doubles when the array is full — amortised O(1) for the resize portion.

Why Not Use a Sorted List?

Inserting into a sorted list costs O(n) (shift elements). A heap achieves O(log n) insertion while still giving O(1) access to the minimum. For k extractions from n elements, a heap is O(n + k log n) vs O(n²) for a sorted list approach.

Thread Safety

Neither LinkedList, ArrayDeque, nor PriorityQueue is thread-safe. For concurrent use, reach for java.util.concurrent alternatives like LinkedBlockingQueue or PriorityBlockingQueue — covered in the Concurrent Collections page.

Choosing the Right Queue

Need	Use
Simple FIFO	ArrayDeque
Doubly-linked FIFO	LinkedList
Priority-based retrieval	PriorityQueue
Bounded blocking FIFO	LinkedBlockingQueue
Blocking priority queue	PriorityBlockingQueue
Thread-safe non-blocking	ConcurrentLinkedQueue

Related Topics

• Deque & ArrayDeque — double-ended queue that extends Queue for stack and deque operations
• LinkedList — the doubly-linked node structure that also implements Queue
• Collections Utility Class — sort, shuffle, and manipulate any Collection including queues
• Comparator — define custom ordering for PriorityQueue elements
• Concurrent Collections — thread-safe queue variants for multithreaded code
• Iterator — safely iterate over queue elements without structural mutation issues