jd five

Queues and Deques

Learning goals

By the end of this chapter you should be able to:

  • Distinguish Queue (FIFO contract), Deque (both ends), and PriorityQueue (heap order)
  • Use offer/poll/peek vs add/remove/element — soft vs throwing empty/full behavior
  • Pick ArrayDeque for single-threaded queue/stack work
  • Understand blocking queues for producer–consumer back-pressure

Processing work in order

Collections so far focused on storage and lookup. Queues focus on what gets handled next.

Queue<Task> inbox = new ArrayDeque<>();
inbox.offer(new Task("email"));
Task next = inbox.poll();  // FIFO — oldest first

A Deque (ArrayDeque, LinkedList) adds push/pop stack behavior and offerFirst/offerLast.

PriorityQueue breaks strict FIFO: poll always returns the smallest element (natural or comparator order) — essential for schedulers and merge patterns.

A Queue hands elements in FIFO order at head/tail (usual mental model). A Deque adds/removes at both ends (also stack: push / pop). PriorityQueue is not FIFO: poll returns the smallest (or comparator-first) element—a heap.

This guide keeps one-thread fast deque, List+deque when both abstractions matter, heap priority, and blocking FIFO queues for producer–consumer back-pressure. Lock-free ConcurrentLinkedQueue, delay, zero-capacity handoff, and blocking priority queues are omitted—they solve narrower operational patterns.

Read Queue first (FIFO API), then ArrayDeque/LinkedList as Deque (two-ended + stack), then priority and blocking flavours.

Queue (interface) — varies

java.util.Queue is the narrow FIFO contract: insert at the tail, remove from the head (PriorityQueue below is not strict FIFO—see that section). Thread-safety depends on the implementation, not the interface.

Two parallel API styles (same operations; different behaviour when empty or full):

  • offer(e) / poll() / peek() — offer returns false if the queue refuses (capacity-bound); poll and peek return null if empty.
  • add(e) / remove() / element() — throw IllegalStateException / NoSuchElementException instead of failing “softly”.

Declare as Queue when callers only need FIFO (hides Deque extras unless they cast):

Queue<String> fifo = new ArrayDeque<>();
Queue<String> fromList = new LinkedList<>();
Queue<String> byPriority = new PriorityQueue<>();

Concrete classes in this file implement Queue (and often Deque or BlockingQueue). The sections below start with ArrayDeque as the usual non-blocking FIFO/stack implementation.

ArrayDeque — not concurrent

Circular buffer in an array—indices wrap. Fast queue or stack on one thread; grows until memory.

Initialize: Deque<T> dq = new ArrayDeque<>(); — optional new ArrayDeque<>(expectedSize).

Sharing across threads:

Deque<String> dq = Collections.synchronizedDeque(new ArrayDeque<>());

There is no separate Collections.synchronizedQueue—use synchronizedDeque when you need Queue/Deque APIs.

Why / vs alternatives: Default Deque/Queue when you need FIFO or LIFO without List indexing—no node allocation per element (LinkedList does allocate nodes).

Queue end (tail):

  • offer(e) / add(e) — insert at tail (add throws if capacity-bound elsewhere).
  • poll() / remove() — remove head (remove throws if empty).
  • peek() / element() — look at head (element throws if empty).

Deque both ends:

  • offerFirst, offerLast, pollFirst, pollLast, peekFirst, peekLast.
  • push(e) — stack: same as addFirst.
  • pop() — remove head like a stack (throws if empty).

Also: size(), isEmpty(), clear(), iterator(), descendingIterator().

Java 21+: ArrayDeque implements SequencedDeque: getFirst() / getLast() (throw if empty, like element()), reversed() — same two-ended story as Deque, but aligned with List / Sequenced* naming across the library.

LinkedList — not concurrent

Doubly linked nodes; implements List and Deque. Same Deque API as ArrayDeque; get(i) by index is O(n).

Initialize: Deque<T> dq = new LinkedList<>(); — also assignable to List<T>.

Sharing across threads: same as Lists—one wrapper per LinkedList:

Deque<String> dq = Collections.synchronizedDeque(new LinkedList<>());

Why / vs alternatives: One object that is both List (indexed sequence, iterator edits) and Deque. Use ArrayDeque instead when you only need queue/stack behaviour without List.

PriorityQueue — not concurrent

Binary min-heap: peek/poll expose the least element by Comparable or Comparator. poll is O(log n). Iterator order ≠ sorted order.

Initialize: Queue<T> pq = new PriorityQueue<>(); — or new PriorityQueue<>(comparator) / new PriorityQueue<>(collection).

Sharing across threads: JDK has no Collections.synchronizedPriorityQueue. Do not use Collections.synchronizedCollection on a PriorityQueue—you lose Queue methods. Prefer external synchronized{} / Lock around offer/poll/peek, or a java.util.concurrent type:

BlockingQueue<String> q = new PriorityBlockingQueue<>();

Why / vs alternatives: ArrayDeque is strict FIFO; PriorityQueue solves “always process smallest job next” (scheduling, merging streams). Not a replacement for TreeSet—different API (queue vs set).

  • offer(e) / add(e) — insert.
  • poll() — remove smallest; null if empty.
  • remove() — removes one occurrence of given object if present (linear search).
  • peek() — smallest without removing; null if empty.
  • element() — smallest; throws if empty.
  • size(), isEmpty(), clear(), iterator(), comparator().

LinkedBlockingQueue — concurrent · blocking

Blocking FIFO queue; optionally bounded. put waits when full, take when empty—classic producer–consumer.

Initialize: BlockingQueue<T> q = new LinkedBlockingQueue<>(); — unbounded Integer.MAX_VALUE style capacity unless you pass capacity.

Bounded buffer: pass capacity so put blocks when full:

BlockingQueue<String> bounded = new LinkedBlockingQueue<>(1000);

Why / vs alternatives: ArrayDeque does not block threads—you busy-wait or poll yourself. Blocking queues coordinate rate: producers slow down when the buffer is full. ArrayBlockingQueue (below) fixes capacity with a single ring buffer instead of linked nodes.

  • put(e) — blocks until space exists.
  • take() — blocks until an element exists.
  • offer(e, timeout, unit) / poll(timeout, unit) — timed wait.
  • Non-blocking offer / poll with immediate failure when full/empty.

Also remainingCapacity(), size().

ArrayBlockingQueue — concurrent · blocking

Fixed-capacity ring buffer; producer blocks when full, consumer when empty.

Initialize: BlockingQueue<T> q = new ArrayBlockingQueue<>(capacity); — capacity required.

Fairness (optional): second constructor arg true ≈ FIFO wait order for blocked producers/consumers (fair):

BlockingQueue<String> fair = new ArrayBlockingQueue<>(100, true);

Why / vs alternatives: Same blocking FIFO role as LinkedBlockingQueue, but memory is bounded by one array—predictable footprint when you must cap outstanding work.

Same blocking surface: put, take, timed offer/poll, remainingCapacity.

Non-blocking vs blocking (Queue) — concept

Without blocking: offer returns false if full, poll returns null if empty, peek inspects. Blocking queues add put/take that wait—use them when threads must pause instead of spinning.

Practice checkpoint

  1. BFS on a graph — which queue implementation on one thread? Answer: ArrayDeque — FIFO with offer/poll; no priority needed.

  2. Always process highest-priority job first — which queue? Answer: PriorityQueue (or PriorityBlockingQueue if threads block).

  3. Producer threads must wait when buffer full — which type? Answer: bounded LinkedBlockingQueue or ArrayBlockingQueue with put/take.

  4. Why prefer ArrayDeque over Stack class? Answer: Stack extends legacy Vector; ArrayDeque is faster, modern, and implements Deque.

Interview angles

  • PriorityQueue iterator: does not traverse in sorted order — only poll/peek guarantee heap head.
  • Blocking vs non-blocking: offer fails immediately when full; put blocks — design for back-pressure.
  • ArrayDeque vs LinkedList: array ring buffer vs linked nodes — deque-only workloads favor ArrayDeque.
  • Fairness: ArrayBlockingQueue(fair=true) — threads acquire in FIFO order under contention.

Next: /java/learn/modern-java/streams/