Java Queue

Java Queue

java.util.Queue<E> is the interface behind every waiting line in Java — task schedulers, BFS graph traversal, print spoolers, rate limiters, and producer-consumer pipelines all model themselves on exactly this contract. Elements enter at the tail and leave from the head. The element that waited longest is always served first.

Three implementations cover every production scenario: ArrayDeque for fast FIFO queues with no per-element allocation overhead, LinkedList when List and Queue interfaces are needed on the same object, and PriorityQueue when processing order depends on urgency rather than arrival sequence.

What Is the Java Queue Interface?

Queue<E> is an interface in java.util that extends Collection<E>. It adds six methods on top of the Collection contract — three that throw exceptions on failure and three that return a sentinel value (null or false). Every standard implementation honours this contract.

QUEUE HIERARCHY:

java.lang.Iterable<E>
    └── java.util.Collection<E>
            └── java.util.Queue<E>            ← FIFO: tail-in, head-out
                    ├── java.util.Deque<E>    ← extends Queue; adds both-end access
                    │       ├── ArrayDeque    ← circular resizable array (RECOMMENDED)
                    │       └── LinkedList    ← doubly-linked nodes (also implements List)
                    ├── java.util.PriorityQueue   ← binary min-heap; priority order, NOT FIFO
                    └── java.util.concurrent.*
                            ├── LinkedBlockingQueue   ← bounded/unbounded, blocking
                            ├── ArrayBlockingQueue    ← bounded, blocking
                            └── ConcurrentLinkedQueue ← unbounded, non-blocking

KEY FACTS:
  Package    : java.util
  Since      : Java 1.5
  Extends    : Collection<E>
  Extended by: Deque<E>, BlockingQueue<E>
  Null       : strongly discouraged — poll() returns null for EMPTY queue;
               null elements make "empty?" and "null element?" indistinguishable
  Thread-safe: NO for ArrayDeque / LinkedList / PriorityQueue
               YES for ConcurrentLinkedQueue, LinkedBlockingQueue, ArrayBlockingQueue

The Six Method Pairs — Basic Overview

Every Queue operation comes in two flavours that differ only in how they signal failure.

 OPERATION        THROWS on failure               RETURNS sentinel on failure
 ---------------  ------------------------------  --------------------------------
 INSERT at tail   add(e)                          offer(e)
                  throws IllegalStateException    returns false
                  (capacity-bounded queues)       (never on unbounded queues)

 REMOVE from head remove()                        poll()
                  throws NoSuchElementException   returns null
                  (when queue is empty)           (when queue is empty)

 INSPECT head     element()                       peek()
                  throws NoSuchElementException   returns null
                  (when queue is empty)           (when queue is empty)

PRODUCTION RULE:
  Always use the null/false-returning group: offer(), poll(), peek()
  An empty queue is a normal operating condition in most processing loops.
  Wrapping remove() or element() in try-catch for NoSuchElementException
  is never the correct pattern for routine processing.

  Use add(), remove(), element() ONLY when empty or full is a genuine
  programming error that should immediately surface as an exception.

FIFO Visualised

QUEUE STATE AFTER: offer("A"), offer("B"), offer("C")

  TAIL                                   HEAD
   ↓                                      ↓
  [ C ] ← [ B ] ← [ A ]     poll() returns "A" first

  offer("D"):  [ D ] ← [ C ] ← [ B ] ← [ A ]
  poll():      returns "A"  →  [ D ] ← [ C ] ← [ B ]
  poll():      returns "B"  →  [ D ] ← [ C ]
  peek():      returns "C"  →  [ D ] ← [ C ]  (unchanged)

  First in, first out. Insertion order drives removal order.

When to Use Queue

Choosing the right Queue implementation — or whether to use a Queue at all — is what interviewers test when they ask about this topic.

USE ArrayDeque (as Queue) WHEN:
  - FIFO processing in single-threaded code is needed
  - Each element should be processed in arrival order
  - No per-element Node allocation overhead is desired
  - Also suitable as a stack (LIFO) via push()/pop()

USE PriorityQueue WHEN:
  - Processing order depends on urgency, not arrival time
  - "Always serve the most critical item next"
  - Dijkstra's shortest path, A* search, incident management
  - Min-heap natural order: smallest element polled first
  - Custom Comparator: highest-priority polled first

USE LinkedBlockingQueue or ArrayBlockingQueue WHEN:
  - Multiple producer threads + multiple consumer threads
  - Consumers should block when queue is empty (take() blocks)
  - Producers should block when queue is full (bounded, put() blocks)
  - This is the standard Java producer-consumer pattern

USE LinkedList (as Queue) ONLY WHEN:
  - Both the Queue interface AND List index access (get(i)) are needed simultaneously
  - For pure queue operations, ArrayDeque is faster

DO NOT USE Queue WHEN:
  - Random access by index is required — use a List
  - Membership testing is frequent — use a Set or Map
  - Sorted iteration with range queries is needed — use a TreeSet

How Queue Implementations Work Internally

ArrayDeque — Circular Resizable Array

ArrayDeque is the recommended general-purpose Queue. It uses a resizable array with two integer indices — head (next to poll) and tail (next insertion slot) — that wrap around the array boundary using bitwise AND, not modulo.

ARRAYDEQUE INTERNAL STRUCTURE (initial capacity 16):

  After offer("A"), offer("B"), offer("C"), offer("D"):

  elements: [ "A" | "B" | "C" | "D" | null | null | null | null | ... ]
               0     1     2     3     4      5      6      7
  head = 0   (next poll target)
  tail = 4   (next offer slot)

  poll() — removes head:
    result     = elements[0] = "A"
    elements[0] = null         (help GC)
    head       = (0+1) & 15  = 1
    returns "A"

  offer("E"):
    elements[4] = "E"
    tail = (4+1) & 15 = 5

  WRAP-AROUND (head at 14, tail has looped back to 2):
  elements: [ "J" | "K" | null | "C" | "D" | "E" | "F" | "G" | "H" | "I" | ... ]
               0     1     2     3     4     5     6     7     8     9
  head = 3, tail = 2   ← tail is BEHIND head — perfectly valid in circular buffer

  RESIZE when size == capacity:
    New array with double capacity.
    Copy elements from head → end, then 0 → tail, into new[0..size-1].
    head = 0, tail = old size.

WHY ARRAYDEQUE BEATS LINKEDLIST FOR QUEUES:
  - No Node object per element   → lower GC pressure
  - Contiguous array memory      → CPU cache prefetching works
  - Bitwise wrap (& mask)        → faster than modulo (%)
  - Java documentation explicitly recommends ArrayDeque over LinkedList

PriorityQueue — Binary Min-Heap

PriorityQueue breaks FIFO. Every poll() returns the smallest element — or the highest-priority by a custom Comparator. Internally it is a complete binary tree stored in a flat array.

PRIORITYQUEUE BINARY MIN-HEAP (6 elements):

  Elements offered: 40, 15, 60, 25, 10, 50

  HEAP ARRAY after all insertions:
    index: [ 0 | 1 | 2 | 3 | 4 | 5 ]
    value: [10 |15 |50 |25 |40 |60 ]

  TREE REPRESENTATION:
               10          ← always the minimum at root (index 0)
             /    \
           15      50
          /  \    /
         25  40  60

  Parent-child index relationships:
    parent(i)       = (i - 1) / 2
    left_child(i)   = 2*i + 1
    right_child(i)  = 2*i + 2

  peek():
    return elements[0]  →  10   O(1) — root is always the minimum

  poll():   removes root, replaces with last, sifts down  →  O(log n)
    Step 1: save result = 10
    Step 2: elements[0] = elements[5] = 60, size--
    Step 3: sift down 60: compare with children 15 and 50
    Step 4: 15 is smaller → swap 60 and 15
    Step 5: 60 now at index 1: compare with children 25 and 40
    Step 6: 25 is smaller → swap 60 and 25
    Step 7: heap property restored → [15, 25, 50, 60, 40]
    returns 10

  offer(5):   adds to end, sifts up  →  O(log n)
    Step 1: elements[size] = 5
    Step 2: sift up: 5 < parent 50 → swap; 5 < parent 10 → swap
    Step 3: 5 is now root → heap property restored

  CRITICAL: PriorityQueue iterator (for-each) traverses heap ARRAY ORDER.
            This is NOT priority order. Only repeated poll() gives sorted output.

Core Operations with Examples

offer(), poll(), peek() — The Essential Trio

Output:
=== Enqueue with offer() ===
offer(Report.pdf)    : true
offer(Invoice.pdf)   : true
offer(Payslip.pdf)   : true
offer(Contract.pdf)  : true
Queue                : [Report.pdf, Invoice.pdf, Payslip.pdf, Contract.pdf]
Size                 : 4

=== peek() — reads head, queue unchanged ===
peek()  : Report.pdf
Queue   : [Report.pdf, Invoice.pdf, Payslip.pdf, Contract.pdf]

=== poll() — FIFO dequeue ===
poll()  : Report.pdf
poll()  : Invoice.pdf
Queue   : [Payslip.pdf, Contract.pdf]

=== Safe behaviour on empty queue ===
isEmpty()      : true
poll() empty   : null
peek() empty   : null
remove() empty : throws NoSuchElementException

PriorityQueue — Priority Order vs Insertion Order

Output:
=== Natural ordering — min first ===
Inserted: [47, 12, 83, 5, 34, 61]
peek()   : 5
Heap array (NOT sorted): [5, 12, 61, 47, 34, 83]
poll() order: 5 12 34 47 61 83

=== Custom order — highest urgency first ===
Ticket       Urg  Summary
-------------------------------------------------------
TKT-002        5  Production API is down
TKT-004        4  Checkout timeout for all users
TKT-005        3  Slow dashboard load
TKT-001        2  Password reset request
TKT-003        1  Font rendering issue

BFS Graph Traversal — The Canonical Queue Algorithm

Breadth-first search requires a Queue because FIFO guarantees nodes are visited level by level — all distance-1 neighbours before any distance-2 neighbour. Swapping Queue for a Deque-as-stack turns BFS into DFS.

Output:
BFS from Mumbai (city connectivity):
[Mumbai, Pune, Nashik, Surat, Hyderabad, Bengaluru, Aurangabad, Ahmedabad, Chennai]

Level 0 (distance 0): Mumbai
Level 1 (distance 1): Pune, Nashik, Surat
Level 2 (distance 2): Hyderabad, Bengaluru, Aurangabad, Ahmedabad
Level 3 (distance 3): Chennai

Basic Example

Output

peek(): Alice
poll(): Alice
poll(): Bob
Remaining: [Charlie]

How it works:

1. ›offer() adds each name to the tail of the queue — "Alice" first, then "Bob", then "Charlie".
2. ›peek() inspects the head without removing it, returning "Alice" — the first element ever offered.
3. ›Each poll() call removes and returns the current head, so "Alice" comes out before "Bob" — first in, first out.
4. ›After two poll() calls, only "Charlie" remains, confirming that a Queue always serves elements in the exact order they arrived.

Performance Considerations

ArrayDeque vs LinkedList: ArrayDeque wins on every axis for pure queue use. No per-element Node allocation means far less GC pressure. Contiguous array memory means CPU caches stay warm. The Java documentation explicitly recommends ArrayDeque over LinkedList for both queue and stack use. LinkedList earns its place only when List-interface methods (get(index), set(index, value)) are needed alongside queue operations.

PriorityQueue heap cost: Every offer() and poll() triggers a sift-up or sift-down operation — O(log n) guaranteed. For n elements, building the heap by inserting one at a time is O(n log n). The PriorityQueue(Collection) constructor uses Floyd's algorithm to build the heap in O(n) — prefer it when initialising from an existing collection.

Thread safety: None of the three main implementations are thread-safe. For concurrent queues: LinkedBlockingQueue for blocking producer-consumer, ArrayBlockingQueue for bounded blocking, ConcurrentLinkedQueue for non-blocking high-throughput. Never share ArrayDeque or PriorityQueue across threads without external synchronisation.

Best Practices

Declare the variable type as Queue<E>, not the concrete implementation. Queue<String> tasks = new ArrayDeque<>() lets you change to LinkedBlockingQueue for thread safety or PriorityQueue for prioritisation by changing one line. ArrayDeque<String> tasks = new ArrayDeque<>() locks every method signature to one class unnecessarily. The sole exception: use PriorityQueue<E> directly when navigation methods beyond the Queue interface are needed.

Always prefer offer(), poll(), and peek() over add(), remove(), and element(). An empty queue is a routine operational condition — the processing loop has simply drained its input. Throwing NoSuchElementException for an empty queue and catching it in a loop is the wrong pattern. String next; while ((next = queue.poll()) != null) is the clean idiom.

Never insert null into a Queue. poll() returning null signals "queue is empty." If null elements were stored, poll() returning null is ambiguous — it could mean empty or it could mean the head was null. Both ArrayDeque and PriorityQueue throw NullPointerException on offer(null). If a "no value" sentinel is needed, use Optional<E> as the element type or a dedicated sentinel constant.

For PriorityQueue, always use poll() to process in priority order — never for-each. The for-each iterator on PriorityQueue traverses the internal heap array, which is not sorted. Only the root (index 0) is guaranteed to be the minimum. Processing in priority order requires draining with poll(). If you need to inspect all elements in priority order while keeping the queue intact, copy it first: new PriorityQueue<>(original).

Common Mistakes

Mistake 1 — Iterating PriorityQueue and Expecting Priority Order

Output:
for-each: [5, 10, 20, 30, 40]
poll() order: 5 10 20 30 40

Mistake 2 — Inserting null Into ArrayDeque

Mistake 3 — Using LinkedList When ArrayDeque Is Sufficient

Mistake 4 — Forgetting That PriorityQueue Needs a Tiebreaker

Interview Questions

Q1. What is the Queue interface in Java and what does FIFO mean?

Queue<E> is an interface in java.util that extends Collection and models a First-In, First-Out container. FIFO means the element inserted earliest is always removed first — like a physical queue at a service counter. The interface defines six methods in two parallel groups: add/offer for insertion, remove/poll for head-retrieval-and-removal, element/peek for head-inspection. The null-returning group (offer, poll, peek) is preferred for routine processing code, reserving the exception-throwing group for cases where an empty queue represents a programming error.

Q2. What is the difference between offer() and add() in Queue?

Both insert an element at the tail. add() throws IllegalStateException if the queue has a capacity limit and is full. offer() returns false instead. For unbounded queues like ArrayDeque and LinkedList, neither ever reaches capacity — both behave identically. For bounded queues like ArrayBlockingQueue, the distinction matters. In production code, offer() is the standard choice because it expresses intent clearly: "attempt to insert, handle failure explicitly." add() is appropriate when insertion failure is a genuine programming error that should propagate immediately.

Q3. Why is ArrayDeque preferred over LinkedList as a Queue implementation?

ArrayDeque uses a resizable circular array — elements are stored contiguously, which is friendly to CPU caches. No per-element Node object is allocated; every offer() simply writes to an array slot, and every poll() nulls an array slot and advances an index. LinkedList allocates a new Node object per element — higher GC pressure, scattered heap allocations, and cache misses on every node traversal. The Java documentation explicitly recommends ArrayDeque over LinkedList for both queue and stack use cases. LinkedList as a queue is only justified when List interface methods (index-based get, set, subList) are also needed on the same object.

Q4. How does PriorityQueue differ from a regular FIFO Queue?

PriorityQueue ignores insertion order. Every poll() returns the element with the highest priority — for natural ordering, the smallest element; for a custom Comparator, whichever the comparator ranks first. Internally it uses a binary min-heap stored in a flat array, where the root is always the minimum. offer() and poll() are O(log n) due to sift-up and sift-down operations. Unlike ArrayDeque, PriorityQueue iteration does not traverse in priority order — the heap array is not sorted. Only repeated poll() calls consume elements in priority order.

Q5. How is Queue used in BFS graph traversal?

BFS explores a graph layer by layer — all nodes at distance 1 from the source before any at distance 2. A Queue enforces this because FIFO means nodes are processed in the exact order they were discovered: the source is enqueued first, its unvisited neighbours are enqueued next, and when those are processed their unvisited neighbours join the tail. Every poll() always returns the longest-waiting node, which is the closest to the source among all remaining nodes. Replacing Queue with a stack (LIFO) changes the traversal to DFS.

Q6. How do you implement a thread-safe Queue in Java?

Three standard options from java.util.concurrent. LinkedBlockingQueue — optionally bounded; take() blocks consumers when empty, put() blocks producers when full (if bounded); the standard choice for producer-consumer pipelines. ArrayBlockingQueue — bounded with a fixed array; slightly more memory-efficient than LinkedBlockingQueue when capacity is fixed. ConcurrentLinkedQueue — unbounded, non-blocking; offer() and poll() use CAS operations and never block; weakly consistent iteration; preferred for high-throughput scenarios where blocking is unacceptable. Never use Collections.synchronizedCollection() on a Queue — it synchronises individual calls but not compound operations like check-then-act patterns.

FAQs

What is the default Queue implementation in Java?

There is no default — Queue is an interface. The Java documentation recommends ArrayDeque as the general-purpose implementation for all single-threaded queue and stack use cases. For priority-based processing use PriorityQueue. For blocking multi-threaded queues use LinkedBlockingQueue or ArrayBlockingQueue from java.util.concurrent.

What is the difference between Queue and Deque in Java?

Queue is a single-ended interface — elements enter at the tail and leave from the head. Deque (Double-Ended Queue) extends Queue and adds symmetric operations on both ends: addFirst/addLast, removeFirst/removeLast, peekFirst/peekLast. A Deque can serve as a FIFO queue (tail-in, head-out) or a LIFO stack (head-in, head-out) or a sliding window buffer. ArrayDeque implements Deque and is the recommended implementation for both patterns.

Can PriorityQueue have duplicate elements?

Yes. PriorityQueue allows multiple elements with equal priority — it never rejects duplicates. Unlike TreeSet, PriorityQueue does not treat compare == 0 as "same element." Two elements that compare as equal are both stored and both available for successive poll() calls. Their relative order when both are at the head is not guaranteed unless a tiebreaker is included in the Comparator.

What happens if no Comparator is given to PriorityQueue for a custom class?

The first offer() succeeds because there is nothing to compare against. The second offer() calls compareTo() on the first element to find the heap position. If the element class does not implement Comparable, Java throws ClassCastException at runtime. The compiler does not catch this — generics allow PriorityQueue<MyClass> even without Comparable. Always either implement Comparable on the element class or pass a Comparator to the constructor.

Is PriorityQueue sorted at all times?

No. The internal array satisfies the heap property — every parent is smaller than its children — but the full array is not sorted. toString() and for-each reflect heap-array order, which looks partially sorted but is not guaranteed to be fully sorted. Only the root (index 0) is guaranteed to be the current minimum. Building a sorted view requires draining with poll().

How do you process all elements in a Queue without destroying it?

Iterate with for-each: for (String item : queue) traverses all elements without removing them. For ArrayDeque and LinkedList this traverses in FIFO order. For PriorityQueue this traverses heap-array order, which is NOT priority order. To inspect all elements in priority order while preserving the original queue, copy it: PriorityQueue<T> copy = new PriorityQueue<>(original); while (!copy.isEmpty()) process(copy.poll());.

Summary

Queue<E> models FIFO processing — first offered, first polled. Its six methods pair into two groups: the exception-throwing add/remove/element for when failure is a programming error, and the null-returning offer/poll/peek for routine processing loops. The null-returning trio is the correct default for almost all production code.

ArrayDeque is the right Queue for single-threaded FIFO work — no per-element allocation, cache-friendly, and explicitly recommended over LinkedList by the Java documentation. PriorityQueue breaks FIFO for priority-based dispatch — poll() always returns the heap root, and for-each iteration does not follow priority order. For multi-threaded queues, reach for LinkedBlockingQueue or ArrayBlockingQueue.

For interviews: know the six method pairs and which group to use in which scenario, explain the ArrayDeque circular-array structure and why it beats LinkedList, describe the binary min-heap mechanics of PriorityQueue, demonstrate BFS using a Queue, and explain why PriorityQueue for-each does not iterate in priority order. These cover every level from campus recruitment to senior engineering rounds.

What to Read Next