☕ JavaCollections Framework

Queue Interface

The Queue interface in java.util represents a collection designed for holding elements prior to processing, following a defined ordering policy. Unlike a List which provides random access by index, a Queue exposes only the head element and enforces a particular insertion and removal discipline. The standard Queue contract is FIFO — first in, first out — though subinterfaces and implementations may define alternative orderings such as priority order or LIFO. Understanding the Queue interface means understanding its dual-form API (throwing vs non-throwing methods), its place in the Collections Framework hierarchy, the semantics of each operation, and when a Queue is the appropriate data structure over a List or Deque. This entry covers the Queue contract in depth, the method pairs and when to use each, the major implementations, and the design patterns that queues enable.

The Queue Contract and FIFO Ordering

A Queue is a linear data structure with a defined access discipline: elements are inserted at the tail and removed from the head. This ordering — first in, first out — models real-world queues: tasks waiting to be processed, messages waiting to be delivered, requests waiting for a server thread. The FIFO discipline ensures fairness: the element that waited the longest is processed next. The Queue interface extends Collection and adds six methods that operate on the head and tail of the queue. These six methods form three functional pairs — add/remove/element for operations that throw exceptions, and offer/poll/peek for operations that return special values. The dual-form API exists because some queue implementations have bounded capacity (blocking queues, for example), and attempting to add to a full queue is either a genuine error (throw an exception) or an expected condition handled by the caller (return false). For unbounded queues like LinkedList and ArrayDeque, the two forms behave identically except for exception type. The Queue interface does not mandate FIFO ordering — it only requires a defined ordering. PriorityQueue orders by natural ordering or a Comparator. Deque implementations accessed from one end produce LIFO (stack) behaviour. The FIFO discipline is the convention for plain Queue usage, and callers of code accepting a Queue reference should assume FIFO unless the type narrows to PriorityQueue or an equivalent. This convention is part of the interface's semantic contract even though it is not mechanically enforced.

Java

// ── Queue interface hierarchy ─────────────────────────────────────────
//
//  Iterable
//  └── Collection
//      └── Queue                          ← this interface
//          ├── Deque                      ← double-ended queue
//          │   ├── ArrayDeque             ← resizable array, fast
//          │   └── LinkedList             ← doubly linked list
//          ├── BlockingQueue              ← java.util.concurrent
//          │   ├── LinkedBlockingQueue
//          │   ├── ArrayBlockingQueue
//          │   └── PriorityBlockingQueue
//          └── PriorityQueue              ← heap-based priority ordering

// ── Six Queue methods — three pairs ──────────────────────────────────
//
// Operation    Throws exception    Returns special value
// ─────────────────────────────────────────────────────
// Insert       add(e)              offer(e)  → false if full
// Remove       remove()            poll()    → null if empty
// Examine      element()           peek()    → null if empty
//
// Throws-exception form: use when the condition is a bug
// Returns-value form:    use when the condition is expected/handled

Queue<String> queue = new LinkedList<>();

// ── Insertion ─────────────────────────────────────────────────────────
queue.add("Alice");       // throws IllegalStateException if full
queue.offer("Bob");       // returns false if full (safe for bounded queues)
queue.offer("Carol");

// ── Examination (peek without removal) ───────────────────────────────
String head = queue.peek();      // "Alice" — null if empty (safe)
String head2 = queue.element();  // "Alice" — throws NoSuchElementException if empty

System.out.println(head);   // Alice (still in queue)
System.out.println(queue.size());  // 3 — unaffected

// ── Removal ──────────────────────────────────────────────────────────
String removed = queue.poll();      // "Alice" — null if empty (safe)
String removed2 = queue.remove();   // "Bob"   — throws NoSuchElementException if empty

System.out.println(queue.size());  // 1 — only Carol remains

// ── FIFO ordering demonstrated ────────────────────────────────────────
Queue<Integer> fifo = new LinkedList<>();
fifo.offer(1);
fifo.offer(2);
fifo.offer(3);

while (!fifo.isEmpty()) {
    System.out.print(fifo.poll() + " ");   // 1 2 3 — first in, first out
}

Queue as a Design Pattern — Producer-Consumer

The most important use of a Queue is as the communication channel in the producer-consumer pattern. A producer adds work items to the queue; one or more consumers remove and process items. The queue decouples the producer from the consumer: producers do not wait for consumers to be ready, consumers do not wait for producers to generate work, and neither needs to know about the other. The queue absorbs rate differences between production and consumption. This decoupling is the reason queues are fundamental to concurrent systems. A web server that receives requests faster than it can process them uses a queue to buffer requests. A data pipeline that reads records faster than it can transform them uses a queue between the reader and transformer stages. A build system that compiles files independently uses a work queue to distribute compilation tasks across worker threads. For single-threaded producer-consumer with guaranteed ordering, a simple Queue such as ArrayDeque suffices. For multi-threaded producer-consumer, the java.util.concurrent blocking queues (LinkedBlockingQueue, ArrayBlockingQueue) provide thread-safe bounded queues with blocking take() and put() operations that suspend threads when the queue is empty or full respectively. These are the correct tool for thread-safe concurrent pipelines — rolling your own synchronised queue on top of a plain Queue is error-prone and unnecessary. The Queue interface also enables breadth-first search (BFS) graph traversal. BFS processes nodes level by level, which requires first-in-first-out ordering: the nodes at the current level are added to the queue, and as each is dequeued and processed, its unvisited neighbours are enqueued. The FIFO property of the queue ensures that nodes at depth n are all processed before any node at depth n+1.

Java

// ── Producer-consumer pattern ────────────────────────────────────────
Queue<WorkItem> workQueue = new LinkedList<>();

// Producer: generates work items and adds to queue
public void produce(int count) {
    for (int i = 0; i < count; i++) {
        WorkItem item = new WorkItem("task-" + i);
        workQueue.offer(item);
        System.out.println("Produced: " + item.getId());
    }
}

// Consumer: processes items from the queue
public void consume() {
    WorkItem item;
    while ((item = workQueue.poll()) != null) {  // poll returns null when empty
        process(item);
        System.out.println("Consumed: " + item.getId());
    }
}

// ── Breadth-first search using Queue ─────────────────────────────────
public List<Integer> bfs(Map<Integer, List<Integer>> graph,
                          int start) {
    List<Integer>    visited = new ArrayList<>();
    Set<Integer>     seen    = new HashSet<>();
    Queue<Integer>   queue   = new LinkedList<>();

    queue.offer(start);
    seen.add(start);

    while (!queue.isEmpty()) {
        int node = queue.poll();          // dequeue — FIFO ensures level-order
        visited.add(node);

        for (int neighbour : graph.getOrDefault(node, List.of())) {
            if (seen.add(neighbour)) {    // Set.add returns false if already present
                queue.offer(neighbour);   // enqueue unvisited neighbours
            }
        }
    }
    return visited;
}

// ── Thread-safe queue for concurrent producer-consumer ────────────────
// java.util.concurrent.LinkedBlockingQueue provides:
// - Thread-safe offer/poll
// - Blocking put/take (suspend until space/item available)
// - Optional capacity bound
BlockingQueue<String> safeQueue = new LinkedBlockingQueue<>(100);

// Producer thread:
new Thread(() -> {
    try {
        safeQueue.put("item");   // blocks if queue is full
    } catch (InterruptedException e) {
        Thread.currentThread().interrupt();
    }
}).start();

// Consumer thread:
new Thread(() -> {
    try {
        String item = safeQueue.take();  // blocks if queue is empty
        process(item);
    } catch (InterruptedException e) {
        Thread.currentThread().interrupt();
    }
}).start();

Choosing the Right Queue Implementation

Java provides several Queue implementations, each suited to different requirements. The choice depends on thread safety requirements, ordering policy, capacity constraints, and performance characteristics. LinkedList implements both List and Deque (which extends Queue). It is a doubly-linked list that allows O(1) insertion and removal at both ends. It is suitable for queue usage but carries more memory overhead per element than ArrayDeque — each element requires a node object with two reference fields in addition to the element reference. For queue-only usage (no random access), LinkedList is never the best choice; ArrayDeque outperforms it in both speed and memory. ArrayDeque is the recommended general-purpose Queue and Deque implementation. It is backed by a resizable circular array, giving O(1) amortised offer/poll/peek operations with excellent cache behaviour and no per-element object overhead. It is not thread-safe but is faster than LinkedList for queue operations. PriorityQueue provides priority-ordered retrieval — the element with the lowest priority value (by natural ordering or Comparator) is always at the head. It uses a binary heap internally, giving O(log n) offer and poll, O(1) peek. For concurrent use, LinkedBlockingQueue (unbounded or bounded, fair FIFO) and ArrayBlockingQueue (bounded, fair or unfair) are the standard choices. ConcurrentLinkedQueue is a non-blocking lock-free FIFO queue useful when throughput is paramount and blocking is unacceptable.

Java

// ── Implementation comparison ─────────────────────────────────────────
//
// Implementation         Thread-safe   Order      offer   poll   Memory
// ─────────────────────────────────────────────────────────────────────
// LinkedList             NO            FIFO        O(1)   O(1)   High (nodes)
// ArrayDeque             NO            FIFO        O(1)*  O(1)   Low (array)
// PriorityQueue          NO            Priority   O(log n) O(log n) Medium
// LinkedBlockingQueue    YES           FIFO        O(1)   O(1)   High (nodes)
// ArrayBlockingQueue     YES (bounded) FIFO        O(1)   O(1)   Low (array)
// ConcurrentLinkedQueue  YES           FIFO        O(1)   O(1)   High (nodes)
//
// * amortised

// ── WRONG: LinkedList for queue-only use ─────────────────────────────
Queue<Task> badChoice = new LinkedList<>();   // extra memory, slower

// CORRECT: ArrayDeque for single-threaded queue ────────────────────────
Queue<Task> goodChoice = new ArrayDeque<>();  // fastest, least memory

// ── Choosing by requirements ──────────────────────────────────────────

// Single-threaded, FIFO, fast:
Queue<Task> queue1 = new ArrayDeque<>();

// Single-threaded, priority order:
Queue<Task> queue2 = new PriorityQueue<>(
    Comparator.comparingInt(Task::getPriority));

// Multi-threaded, unbounded, blocking:
BlockingQueue<Task> queue3 = new LinkedBlockingQueue<>();

// Multi-threaded, bounded (backpressure), blocking:
BlockingQueue<Task> queue4 = new ArrayBlockingQueue<>(1000);

// Multi-threaded, non-blocking, high throughput:
Queue<Task> queue5 = new ConcurrentLinkedQueue<>();

// ── Polymorphism — program to the interface ───────────────────────────
// Method accepts any Queue — works with all implementations
public static <T> void drainQueue(Queue<T> source,
                                   List<T>  destination) {
    T item;
    while ((item = source.poll()) != null) {
        destination.add(item);
    }
}

// Can pass any Queue implementation:
drainQueue(new ArrayDeque<>(List.of("a","b","c")), result);
drainQueue(new PriorityQueue<>(List.of(3,1,2)), numbers);
drainQueue(new LinkedBlockingQueue<>(taskList), processed);

Queue Operations — Edge Cases and Iteration

Several edge cases and behaviours of Queue require attention. Null elements are prohibited by most Queue implementations — LinkedList is an exception, but passing null to a queue that follows this contract makes poll() ambiguous (does null mean empty or was null the stored value?). The contract recommends not inserting null elements even into implementations that technically permit it. Iteration over a Queue does not remove elements — it is purely observational. The Iterator traverses elements in queue order (FIFO for standard queues, priority order for PriorityQueue) without removing them. To process and remove all elements, use poll() in a loop rather than an iterator. The enhanced for-each loop similarly iterates without removing. The size() and isEmpty() methods work as expected. isEmpty() is preferred over size() == 0 for clarity and potential performance (some implementations can check emptiness in O(1) while size() requires counting). The contains(Object) method performs a linear search and is O(n) — queues are not designed for membership testing, and if frequent contains() checks are needed, a Set should be used alongside the queue. Transferring all elements from one collection into a Queue uses addAll(), which respects the queue's ordering policy. Creating a Queue with initial contents from a Collection uses the constructor that accepts a Collection argument, which adds all elements in the collection's iteration order.

Java

// ── Null element restriction ──────────────────────────────────────────
Queue<String> queue = new ArrayDeque<>();
// queue.offer(null);  // throws NullPointerException
// Null makes poll() ambiguous: null means empty? or stored value?
// Convention: never store null in a Queue

// ── Iteration without removal ─────────────────────────────────────────
Queue<String> q = new ArrayDeque<>(List.of("first", "second", "third"));

// FOR-EACH: observes without removing
for (String s : q) {
    System.out.print(s + " ");   // first second third
}
System.out.println(q.size());    // still 3 — nothing removed

// POLL LOOP: removes while processing
while (!q.isEmpty()) {
    System.out.print(q.poll() + " ");  // first second third
}
System.out.println(q.size());    // 0 — all removed

// ── Batch operations ──────────────────────────────────────────────────
Queue<Integer> from = new ArrayDeque<>(List.of(1, 2, 3, 4, 5));
Queue<Integer> to   = new ArrayDeque<>();

// Transfer all: addAll preserves ordering
to.addAll(from);       // from still has all elements
System.out.println(to.size());   // 5

// Drain: removes from source while adding to destination
while (!from.isEmpty()) {
    to.offer(from.poll());
}
System.out.println(from.isEmpty());  // true — drained

// ── Contains check — linear scan ─────────────────────────────────────
Queue<String> names = new ArrayDeque<>(
    List.of("Alice", "Bob", "Carol"));
System.out.println(names.contains("Bob"));    // true — O(n) scan
System.out.println(names.contains("Dave"));   // false

// For frequent membership testing, maintain a parallel Set:
Set<String> nameSet = new HashSet<>(names);
System.out.println(nameSet.contains("Bob"));  // true — O(1) lookup

// ── Creating a Queue from existing collection ─────────────────────────
List<String> source = List.of("task1", "task2", "task3");
Queue<String> workQueue = new ArrayDeque<>(source);  // constructor with Collection

// Initial capacity hint for ArrayDeque:
Queue<String> sized = new ArrayDeque<>(1000);  // preallocate for 1000 elements

Queue Interface

The Queue Contract and FIFO Ordering

Queue as a Design Pattern — Producer-Consumer

Choosing the Right Queue Implementation

Queue Operations — Edge Cases and Iteration

Related Topics in Collections Framework