Queue Interface

A queue holds elements waiting to be processed. Elements are added at one end and taken from the other, usually in first-in, first-out (FIFO) order, like people standing in line. The java.util.Queue interface defines the operations every queue supports, and Java provides several implementations: ArrayDeque and LinkedList for ordinary FIFO queues, PriorityQueue for processing elements by priority, and thread-safe queues for passing work between threads.

The Queue Concept

           offer (add to tail)
                  │
                  ▼
 head ◄── [ job1 | job2 | job3 | job4 ] ◄── tail
   │
   ▼
 poll (remove from head)

• New elements join at the tail.
• Elements leave from the head.
• The element that has waited longest is processed next.

Real systems use queues everywhere: print jobs, customer support tickets, tasks in a thread pool, messages between services, and breadth-first traversal of trees and graphs.

Creating a Queue

Queue is an interface, so you choose an implementation:

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

Queue<String> jobs = new ArrayDeque<>();
jobs.offer("print report.pdf");
jobs.offer("print invoice.pdf");
jobs.offer("print photo.png");

System.out.println(jobs.poll());   // print report.pdf  (first in, first out)
System.out.println(jobs.peek());   // print invoice.pdf (look without removing)
System.out.println(jobs);          // [print invoice.pdf, print photo.png]

ArrayDeque is the recommended general-purpose FIFO queue. It stores elements in a resizable circular array, so adding at the tail and removing at the head are both constant-time, with less memory overhead than LinkedList.

The Six Core Methods

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

Queue<String> q = new ArrayDeque<>();
System.out.println(q.poll());   // null
System.out.println(q.peek());   // null
q.remove();                     // NoSuchElementException

Which form to use

• Use offer, poll, and peek when an empty or full queue is a normal situation, such as a worker loop that drains whatever is waiting:

String job;
while ((job = jobs.poll()) != null) {
    process(job);
}

• Use add, remove, and element when the queue should never be empty or full at that point; an exception then signals a bug.

Because poll and peek use null to mean "empty," most queue implementations reject null elements. ArrayDeque and PriorityQueue throw NullPointerException if you try to add one.

Bounded queues

ArrayDeque, LinkedList, and PriorityQueue grow as needed, so offer always succeeds for them. Bounded queues, such as ArrayBlockingQueue with a fixed capacity, can be full; there offer returns false and add throws IllegalStateException. Bounded queues are used to apply back-pressure, preventing a fast producer from overwhelming a slow consumer.

Queue Is Also a Collection

Queue extends Collection, so size(), isEmpty(), contains(), iteration, and clear() are all available:

System.out.println(jobs.size());          // 2
System.out.println(jobs.isEmpty());       // false
for (String j : jobs) {                   // iterates head to tail, without removing
    System.out.println(j);
}

Iterating does not remove elements. Use poll to consume them.

PriorityQueue: Processing by Priority

A PriorityQueue does not process elements in arrival order. Instead, poll always returns the smallest element according to its ordering: natural ordering, or a Comparator supplied to the constructor.

Queue<Integer> pq = new PriorityQueue<>(List.of(5, 1, 4, 2, 3));

System.out.println(pq.peek());            // 1: the smallest
while (!pq.isEmpty()) {
    System.out.print(pq.poll() + " ");    // 1 2 3 4 5
}

For the largest element first, reverse the order:

Queue<Integer> maxFirst = new PriorityQueue<>(Comparator.reverseOrder());

Internal structure: a binary heap

PriorityQueue is implemented as a binary heap stored in an array. The smallest element is always at the root (index 0), but the rest of the array is only partially ordered:

Queue<Integer> pq = new PriorityQueue<>(List.of(5, 1, 4, 2, 3));
System.out.println(pq);    // [1, 2, 4, 5, 3]   not sorted!

Printing or iterating a PriorityQueue does not give sorted order. Only repeated poll calls produce elements in priority order.

Ties

When two elements compare as equal, a PriorityQueue makes no promise about which comes out first. If arrival order should break ties, include it in the comparator, for example with a sequence number or timestamp. The practical example below does this with ticket IDs.

Other Queue Implementations

The blocking queues add put (wait while full) and take (wait while empty) for coordinating threads. They are covered in the concurrency section.

Queues in Algorithms: Breadth-First Search

A FIFO queue processes items level by level, which is the basis of breadth-first search (BFS):

Map<String, List<String>> prerequisites = Map.of(
    "Spring", List.of("Java", "SQL"),
    "Java", List.of("Basics"),
    "SQL", List.of("Basics"),
    "Basics", List.of()
);

Queue<String> toVisit = new ArrayDeque<>(List.of("Spring"));
Set<String> seen = new LinkedHashSet<>(List.of("Spring"));

while (!toVisit.isEmpty()) {
    String course = toVisit.poll();
    for (String pre : prerequisites.get(course)) {
        if (seen.add(pre)) {
            toVisit.offer(pre);
        }
    }
}
System.out.println(seen);   // [Spring, Java, SQL, Basics]

Each course's direct prerequisites are queued before anything further away, so courses are discovered in order of distance from the starting point. The seen set prevents visiting Basics twice.

Practical Example: Support Ticket Desk

Support tickets have a priority. The desk always handles the most urgent ticket first, and among tickets with the same priority, the oldest one first.

import java.util.*;

public class SupportDesk {
    enum Priority { CRITICAL, HIGH, NORMAL }

    record Ticket(int id, String customer, Priority priority) { }

    public static void main(String[] args) {
        Comparator<Ticket> order = Comparator
                .comparing(Ticket::priority)          // enum order: CRITICAL first
                .thenComparingInt(Ticket::id);        // older tickets first within a priority

        Queue<Ticket> queue = new PriorityQueue<>(order);
        queue.offer(new Ticket(101, "ada", Priority.NORMAL));
        queue.offer(new Ticket(102, "linus", Priority.HIGH));
        queue.offer(new Ticket(103, "grace", Priority.CRITICAL));
        queue.offer(new Ticket(104, "alan", Priority.NORMAL));
        queue.offer(new Ticket(105, "margaret", Priority.HIGH));

        System.out.println("Next up: " + queue.peek());
        System.out.println("Waiting: " + queue.size());

        int handled = 0;
        while (!queue.isEmpty() && handled < 3) {
            Ticket t = queue.poll();
            System.out.println("Handling #" + t.id() + " (" + t.priority() + ") for " + t.customer());
            handled++;
        }
        System.out.println("Still waiting: " + queue.size());
    }
}

Output:

Next up: Ticket[id=103, customer=grace, priority=CRITICAL]
Waiting: 5
Handling #103 (CRITICAL) for grace
Handling #102 (HIGH) for linus
Handling #105 (HIGH) for margaret
Still waiting: 2

Enum constants compare by their declaration order, so listing CRITICAL first makes it the "smallest" priority and therefore the first to be polled. The secondary comparison on id makes the order fully deterministic: tickets 102 and 105 are both HIGH, and 102, the older one, is handled first. peek shows the next ticket without removing it, and the loop uses poll to take tickets one at a time, stopping after three. The two NORMAL tickets remain in the queue for later. Replacing PriorityQueue with ArrayDeque would turn this into a plain first-come, first-served desk without changing any other line.