Queues are about ends, not indexing
A List lets you reach any position; a queue deliberately gives that up. The whole
point of the Queue family is to constrain access to the ends of a collection so the
data structure underneath can be fast and the intent of your code is obvious. Queue
models FIFO (first-in, first-out): you add at the tail and take from the head.
But "queue" is really a contract about which element comes out next, not a promise of
FIFO — PriorityQueue hands you the smallest element, and a Deque used as a stack hands
you the most recent. This guide walks the interface hierarchy and the implementations that
back it, with an eye on the design judgment interviewers actually probe.
The two method families
The single most important thing to internalize about Queue is that every core operation
ships in two flavours: one that throws on failure and one that returns a special
value (false or null). This is not redundancy — it encodes intent. The throwing form
says "failure here is a bug, surface it loudly." The returning form says "emptiness or
fullness is normal control flow I will check."
Queue<Integer> q = new ArrayDeque<>();
q.add(1); // throws IllegalStateException if a bounded queue is full
q.offer(1); // returns false instead of throwing
q.remove(); // throws NoSuchElementException when empty
q.poll(); // returns null when empty
q.element(); // throws NoSuchElementException when empty
q.peek(); // returns null when empty
Pick offer/poll/peek as your default for bounded or concurrent queues where running
empty or full is expected. Reserve add/remove/element for the cases where an empty
queue genuinely means a programming error you want to crash on.
Deque: both ends in play
Deque<E> ("double-ended queue", said "deck") extends Queue and lets you insert, remove,
and examine at both the head and the tail. Each operation gains a First and a Last
variant, and each of those keeps the throwing-vs-returning split — so the API doubles into a
tidy grid: addFirst/offerFirst, removeLast/pollLast, getFirst/peekFirst, and so
on.
Deque<Integer> d = new ArrayDeque<>();
d.addFirst(1); // [1]
d.addLast(2); // [1, 2]
d.peekFirst(); // 1 (returns null if empty)
d.getLast(); // 2 (throws if empty)
d.pollFirst(); // removes 1 -> [2]
Because both ends are O(1), a Deque is the one structure that can serve as either a
FIFO queue or a LIFO stack. The inherited plain-Queue methods simply map insertion to the
tail and removal to the head, giving you FIFO for free.
Deque as a stack — and goodbye, legacy Stack
Deque also exposes push, pop, and peek, which all operate on the head as a LIFO
stack: push is addFirst, pop is removeFirst, peek is peekFirst. This is the
recommended modern stack, and the reason is worth knowing. The old java.util.Stack
extends Vector, which makes every operation synchronized (slow, and pointless single
-threaded) and — worse — leaks Vector's index methods, so callers can get(i) or insert
into the middle, shattering the stack abstraction. It even iterates bottom-to-top, the
opposite of pop order.
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); // [1]
stack.push(2); // [2, 1] — head is the top
stack.peek(); // 2
stack.pop(); // 2 -> [1] (push/pop/peek THROW on empty)
ArrayDeque as a stack is unsynchronized, tight-contracted, and iterates in the right
order. One subtlety: the stack-named pop/peek throw NoSuchElementException on an
empty deque, unlike pollFirst/peekFirst, which return null.
ArrayDeque vs LinkedList
Both implement Deque, but the storage underneath drives the choice. ArrayDeque is a
resizable circular array — contiguous memory, excellent cache locality, no per-element
node object. LinkedList is doubly-linked nodes, each costing an object plus two
pointers, scattered across the heap.
Deque<Integer> fast = new ArrayDeque<>(); // prefer this for queue/stack/deque use
Deque<Integer> list = new LinkedList<>(); // only when you also need List behaviour
For pure queue, stack, or deque work, ArrayDeque wins on speed and memory. Reach for
LinkedList only when you genuinely need List operations (indexing, ListIterator) on
the same object, or — the rare case — you must store null, which ArrayDeque forbids.
PriorityQueue: a heap, not a line
PriorityQueue breaks the FIFO assumption: its head is always the smallest element by
the ordering, not the oldest. It is backed by a binary heap, so offer and poll run
in O(log n) while peek is O(1). Ordering comes either from the elements' natural
Comparable order or from a Comparator you pass at construction.
// default: min-heap by natural order
PriorityQueue<Integer> min = new PriorityQueue<>();
min.offer(5); min.offer(1); min.offer(3);
min.poll(); // 1 — smallest first
// max-heap, and ordering by a field
PriorityQueue<Integer> max = new PriorityQueue<>(Comparator.reverseOrder());
PriorityQueue<Task> byPriority =
new PriorityQueue<>(Comparator.comparingInt(Task::priority));
The comparator is fixed at construction. For your own objects, supplying a Comparator
or implementing Comparable is mandatory — without an ordering the heap can't decide its
head and throws ClassCastException on the first offer. Building a heap from a known
collection (the constructor taking one) is O(n), cheaper than n separate inserts.
The PriorityQueue iteration trap
Here is the classic interview surprise: iterating a PriorityQueue does not yield sorted
order. Its iterator and toString walk the internal heap array, which is only
partially ordered — the heap invariant guarantees a parent precedes its children, nothing
more. Only draining via poll produces priority order.
PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(5, 1, 3, 2, 4));
System.out.println(pq); // e.g. [1, 2, 3, 5, 4] — NOT sorted
while (!pq.isEmpty())
System.out.print(pq.poll()); // 12345 — sorted, by emptying
If you need a sorted snapshot without destroying the queue, copy into a list and sort it.
Remember the heap's complexity profile too: offer/poll are O(log n) and peek is O(1),
but contains and arbitrary remove(Object) are O(n) linear scans — heaps are great at
"give me the minimum," weak at "find this element."
BlockingQueue and producer-consumer
When threads share a queue, the BlockingQueue<E> interface in java.util.concurrent adds
operations that wait instead of failing: put(e) blocks while the queue is full, and
take() blocks while it is empty. That is the entire foundation of the producer-consumer
pattern — the queue owns the locking and the waiting, so neither side touches wait/notify.
BlockingQueue<Integer> q = new ArrayBlockingQueue<>(10); // bounded -> back-pressure
Runnable producer = () -> { while (true) q.put(produce()); }; // blocks if full
Runnable consumer = () -> { while (true) consume(q.take()); }; // blocks if empty
A bounded queue gives back-pressure: if consumers fall behind, the queue fills and
producers naturally throttle rather than exhausting memory. ArrayBlockingQueue (bounded,
single lock) and LinkedBlockingQueue (separate put/take locks, higher throughput) are the
workhorses; SynchronousQueue (zero capacity, direct hand-off) and PriorityBlockingQueue
round out the set. When threads should drain available work but never wait, a non
-blocking ConcurrentLinkedQueue (lock-free CAS, poll returns null immediately) fits
better.
The no-nulls rule
Almost every queue — ArrayDeque, PriorityQueue, ConcurrentLinkedQueue, the blocking
queues — rejects null, and the reason ties the whole family together. null is the
sentinel the returning method family uses to mean "the queue is empty." If a real null
element were allowed, poll() == null would be ambiguous: empty queue, or a head that
happens to be null?
Queue<String> q = new ArrayDeque<>();
q.offer(null); // NullPointerException — by design
q.poll(); // null can therefore ONLY ever mean "empty"
The lone holdout is LinkedList, which predates the Queue interface and permits null —
one more reason not to use it as a queue.
Recap
Queue constrains access to the ends so implementations stay fast and intent stays
clear. Master the two method families — throwing add/remove/element for "this is a
bug" versus returning offer/poll/peek for expected emptiness. Deque doubles that into
both-ends access, giving you a FIFO queue or, via push/pop, a fast LIFO stack that
retires the synchronized, leaky legacy Stack. Prefer ArrayDeque over LinkedList
for raw queue/stack/deque work thanks to its contiguous backing array. PriorityQueue is a
binary heap ordered by Comparable/Comparator, with the famous "iteration isn't
sorted" trap. For concurrency, BlockingQueue powers producer-consumer with
back-pressure. And the no-nulls rule across the family exists to keep null meaning
exactly one thing: empty.