Queue and Deque Interfaces in Java - Quiz

Queue (Java 5, extends Collection) is a queue with one entrance and one exit: elements are inserted at the tail and removed from the head, usually in FIFO order (“first in, first out”). The interface does not require FIFO: a PriorityQueue hands out the smallest element first.

Deque (double-ended queue, pronounced “deck”, Java 6) extends Queue: you can insert, remove and examine elements at both ends (offerFirst/Last(), pollFirst/Last(), peekFirst/Last(), descendingIterator()), so one object works both as a FIFO queue and as a LIFO stack (push(), pop(), peek()).

Every Deque is a Queue, but not the other way round: PriorityQueue implements only Queue. A practical rule: declare the variable as Queue if the code needs only a queue, and as Deque if it needs a stack or access to both ends.

Queue defines three operations, each in two forms: one throws an exception, the other returns a special value.

• Insert at the tail: add(e) — IllegalStateException if a capacity-restricted queue is full; offer(e) — returns false.
• Remove the head: remove() — NoSuchElementException on an empty queue; poll() — returns null.
• Examine the head without removing it: element() — NoSuchElementException; peek() — returns null.

poll() and peek() both return the head, but poll() removes it and peek() does not. Do not confuse remove() without arguments (takes the head) with remove(Object o) inherited from Collection (searches for a specific element). The size is returned by size(), and isEmpty() checks for emptiness.

Most implementations reject null: ArrayDeque, PriorityQueue and the queues in java.util.concurrent throw NullPointerException on offer(null). The reason is that poll() and peek() use null as the “queue is empty” signal.

LinkedList is the exception: it accepts null, and the signal becomes ambiguous. Put "A", null, "B" into it and drain it with while ((s = queue.poll()) != null) — only A is printed: the second poll() returns the null element, the loop ends, and "B" stays in the queue.

If null is possible, check for emptiness explicitly:

while (!queue.isEmpty()) {
    System.out.println(queue.poll()); // A, null, B
}

The safer habit is not to put null into queues at all.

A stack (LIFO) works only with the head: push(e) = addFirst(e), pop() = removeFirst(), peek() = peekFirst(). A queue (FIFO) inserts at the tail and takes from the head: offer(e) = offerLast(e), poll() = pollFirst(), peek() = peekFirst().

The top of the stack and the head of the queue are the same end, so the operations can be mixed:

Deque<Integer> deque = new ArrayDeque<>();
deque.offer(1);
deque.offer(2);
deque.push(0);
System.out.println(deque);       // [0, 1, 2]
System.out.println(deque.pop()); // 0

On an empty deque peek() returns null, while pop() throws NoSuchElementException, just like removeFirst().

Queue has no pop(): push() and pop() are declared in Deque. The code Queue<String> q = new ArrayDeque<>(); q.pop(); does not compile (cannot find symbol), even though the ArrayDeque object has the method. For a queue use poll() or remove(); for a stack declare the variable as Deque.

For an ordinary queue or stack in single-threaded code — ArrayDeque; LinkedList — when the same collection must also be a list (the only one of these that accepts null); PriorityQueue — when elements must come out by priority. Fixed-size queues (ArrayBlockingQueue, LinkedBlockingDeque with a capacity) and thread-safe queues live in java.util.concurrent.

The difference between add() and offer() (and between addFirst() and offerFirst()) only shows up in capacity-restricted queues:

Queue<String> queue = new ArrayBlockingQueue<>(2);
queue.offer("A");                     // true
queue.offer("B");                     // true
System.out.println(queue.offer("C")); // false - no room
queue.add("C");                       // IllegalStateException: Queue full

ArrayDeque, LinkedList and PriorityQueue have no capacity limit, so their offer() always returns true and add() never throws IllegalStateException.

To iterate without removal, use a for-each loop or iterator(): the elements stay in the queue. ArrayDeque and LinkedList are traversed from head to tail, and descendingIterator() walks a Deque the other way (since Java 21 there is also reversed(), a reverse-ordered view). PriorityQueue is the odd one out: its iterator does not follow priority order; elements come out sorted only through poll().

By index — no: Queue and Deque have no get(int) or add(int, E), only the ends are accessible. You can check for an element with contains() and remove one from the middle with remove(Object) or removeFirstOccurrence(). If you really need indexes, use a LinkedList through the List interface, or an ArrayList.