Queue & Deque Interview Questions & Answers

Queue<E> is a Collection that models a FIFO (first-in, first-out) order: elements are added at the tail and removed from the head. It extends Collection and is implemented by LinkedList, ArrayDeque, PriorityQueue, and the concurrent/blocking queues.

Queue<String> q = new LinkedList<>();
q.offer("a");           // enqueue at tail
q.offer("b");
String head = q.poll(); // dequeue from head -> "a"
String next = q.peek(); // look without removing -> "b"

Note that not every Queue is FIFO: PriorityQueue orders by priority and a Deque used as a stack is LIFO. The interface only guarantees the head is the element returned by peek/poll — the ordering policy is the implementation's job.

Every core Queue operation comes in two flavours: one that throws an exception on failure and one that returns a special value (false or null). Use the throwing form when failure is a bug; use the returning form when emptiness/fullness is expected control flow.

Operation	Throws on failure	Returns special value
Insert	add(e) (throws IllegalStateException if full)	offer(e) (returns false)
Remove head	remove() (throws NoSuchElementException if empty)	poll() (returns null)
Examine head	element() (throws NoSuchElementException if empty)	peek() (returns null)

Queue<Integer> q = new ArrayDeque<>();
q.poll();      // null  — empty, no exception
q.remove();    // NoSuchElementException

The returning forms (offer/poll/peek) are the safer default for bounded/concurrent queues where failure is normal.

Deque<E> ("double-ended queue", pronounced "deck") lets you insert, remove, and examine at both ends. It extends Queue, so it can act as a plain FIFO queue, but it adds a full set of *First/*Last methods.

Deque<Integer> d = new ArrayDeque<>();
d.addFirst(1);   // [1]
d.addLast(2);    // [1, 2]
d.peekFirst();   // 1
d.peekLast();    // 2
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 — which is exactly why modern code uses it in place of the legacy Stack class.

Each end has the same throwing-vs-returning split as Queue, doubled for first and last:

	First (head) throws	First returns	Last (tail) throws	Last returns
Insert	addFirst(e)	offerFirst(e)	addLast(e)	offerLast(e)
Remove	removeFirst()	pollFirst()	removeLast()	pollLast()
Examine	getFirst()	peekFirst()	getLast()	peekLast()

Deque<String> d = new ArrayDeque<>();
d.offerFirst("x");   // returns boolean, no throw
d.peekLast();        // null if empty, no throw
d.getFirst();        // NoSuchElementException if empty

The throwing forms (getFirst, removeLast) fail loudly on an empty deque; the returning forms (peekFirst, pollLast) give null. The inherited Queue methods map to the first end for removal and the last for insertion.

Deque provides push, pop, and peek, which operate on the head as a LIFO stack: push is addFirst, pop is removeFirst, peek is peekFirst.

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]

Both ends are O(1), so this is a fast, clean stack. Note pop/peek here throw NoSuchElementException on an empty deque (unlike poll/peekFirst, which return null).

java.util.Stack extends Vector, which makes it synchronized on every operation (slow, and pointless for single-threaded use) and, worse, it exposes Vector's index methods so you can get(i)/insertElementAt into the middle — breaking the stack abstraction. It also iterates bottom-to-top, the opposite of pop order.

// legacy — avoid
Stack<Integer> old = new Stack<>();

// modern stack — fast, clean LIFO
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.pop();

The Javadoc itself recommends ArrayDeque for stack use. It's unsynchronized (faster), has a tight contract (no random access), and iterates in the correct order.

Both implement Deque, but the data structure underneath differs:

	ArrayDeque	LinkedList
Backing store	resizable circular array	doubly-linked nodes
Memory	one compact array	a node object + 2 pointers per element
Cache locality	excellent (contiguous)	poor (scattered nodes)
Allows null	no	yes
Also implements	Queue, Deque	List, Queue, Deque

Deque<Integer> fast = new ArrayDeque<>();   // prefer this
Deque<Integer> list = new LinkedList<>();    // only if you need List ops

For pure queue/stack/deque use, ArrayDeque is faster thanks to contiguous memory and no per-element node allocation. Pick LinkedList only when you also need List behavior (indexing, ListIterator) or must store null.

ArrayDeque (and most queues) reject null because null is the sentinel value returned by poll/peek to mean "the queue is empty." If a real null element were allowed, you couldn't tell an empty queue from a queue whose head is null.

Deque<String> d = new ArrayDeque<>();
d.offer(null);   // NullPointerException
d.poll();        // null only ever means "empty"

So the no-null rule keeps the returning-value method family unambiguous. LinkedList predates this design and permits null, which is one more reason to avoid it as a queue.

PriorityQueue is a Queue whose head is always the smallest element by the ordering — not FIFO. It's backed by a binary heap, so peek/poll return the minimum and offer/poll are O(log n).

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(1);
pq.offer(3);
pq.poll();   // 1  — smallest first
pq.poll();   // 3

Ordering comes from the elements' Comparable (natural order) or a Comparator passed to the constructor. It allows duplicates but, like other queues, not null, and elements must be mutually comparable or you get a ClassCastException.

By default a PriorityQueue is a min-heap (natural order). Pass a Comparator to change the policy — reverseOrder() makes a max-heap, and a key extractor orders by a field.

// max-heap: largest first
PriorityQueue<Integer> max = new PriorityQueue<>(Comparator.reverseOrder());
max.offer(1); max.offer(9); max.offer(5);
max.poll();   // 9

// order tasks by priority field
PriorityQueue<Task> tasks =
    new PriorityQueue<>(Comparator.comparingInt(Task::priority));

The comparator is fixed at construction. For objects, supplying a Comparator (or implementing Comparable) is mandatory — without an ordering the heap can't decide the head and throws ClassCastException on the first offer.

No. A PriorityQueue's iterator (and toString) traverses the internal heap array, which is only partially ordered — the heap invariant guarantees a parent precedes its children, not a fully sorted sequence. Only poll returns elements in 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 draining

To get a sorted view you must repeatedly poll (which empties the queue) or copy into a list and sort it. This "the queue prints unsorted" surprise is a classic interview trap.

The binary heap gives:

Operation	Complexity
offer / add (insert)	O(log n) — sift up
poll / remove() (poll head)	O(log n) — sift down
peek / element (head)	O(1)
remove(Object) / contains	O(n) — linear scan

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(7);     // O(log n)
pq.peek();       // O(1)
pq.remove(7);    // O(n) — must search first

Building a heap from a known collection (the constructor that takes one) is O(n), better than n inserts. The O(n) contains/arbitrary-remove is the cost to remember: heaps are great at "give me the min," weak at "find this element."

An unbounded queue grows as needed (limited only by memory) — LinkedList, ArrayDeque, PriorityQueue, ConcurrentLinkedQueue, LinkedBlockingQueue (default). A bounded queue has a fixed maximum capacity set at construction — ArrayBlockingQueue, or LinkedBlockingQueue given a capacity.

Queue<Integer> unbounded = new ArrayDeque<>();          // grows freely
BlockingQueue<Integer> bounded = new ArrayBlockingQueue<>(2); // cap 2
bounded.offer(1); bounded.offer(2);
bounded.offer(3);   // false — full, rejected (offer form)

Bounds matter for back-pressure: a bounded queue between a producer and consumer prevents a fast producer from exhausting memory. On a full bounded queue, add throws, offer returns false, and put (blocking) waits.

BlockingQueue<E> (in java.util.concurrent) is a thread-safe queue that adds operations which block instead of failing: put(e) waits while the queue is full, and take() waits while it's empty. This is the foundation of the producer-consumer pattern.

BlockingQueue<Task> q = new LinkedBlockingQueue<>();

// producer thread
q.put(task);     // blocks if full

// consumer thread
Task t = q.take(); // blocks until an element is available

It also offers timed offer(e, timeout, unit) / poll(timeout, unit). Because blocking handles the waiting and the queue handles the locking, you rarely need manual wait/notify for hand-off between threads.

The commonly used ones:

Implementation	Notes
ArrayBlockingQueue	bounded, array-backed, single lock, optional fairness
LinkedBlockingQueue	optionally bounded, linked nodes, separate put/take locks (higher throughput)
PriorityBlockingQueue	unbounded, priority-ordered, take blocks when empty
SynchronousQueue	zero capacity — each put waits for a matching take
DelayQueue	elements become available only after a delay expires

BlockingQueue<Runnable> work = new LinkedBlockingQueue<>();
// exactly what a ThreadPoolExecutor uses to hold queued tasks

ArrayBlockingQueue and LinkedBlockingQueue are the workhorses for bounded back-pressure; SynchronousQueue is a direct hand-off used by cached thread pools.

Producers put work into a shared BlockingQueue; consumers take from it. The queue handles all synchronization and waiting, so neither side touches locks directly — producers block when it's full, consumers block when it's empty, decoupling their speeds.

BlockingQueue<Integer> q = new ArrayBlockingQueue<>(10);

Runnable producer = () -> { while (true) q.put(produce()); };
Runnable consumer = () -> { while (true) consume(q.take()); };

A bounded queue gives back-pressure: if consumers fall behind, the queue fills and producers naturally slow down rather than exhausting memory. A common shutdown trick is a "poison pill" — a sentinel element that tells a consumer to stop.

ConcurrentLinkedQueue is an unbounded, thread-safe, non-blocking FIFO queue. It uses lock-free CAS (compare-and-swap) algorithms instead of locks, so it scales well under high contention — but it never blocks: poll returns null immediately when empty rather than waiting.

Queue<Event> q = new ConcurrentLinkedQueue<>();
q.offer(event);          // always succeeds (unbounded)
Event e = q.poll();      // null if empty — no waiting

Use it when many threads enqueue/dequeue and you don't need blocking hand-off or capacity bounds. If consumers must wait for work, use a BlockingQueue instead. Note size() is O(n) and only approximate under concurrency.

Both are thread-safe FIFO queues; the deciding factor is whether consumers need to wait for elements.

	BlockingQueue (e.g. LinkedBlockingQueue)	ConcurrentLinkedQueue
Blocks when empty/full	yes (take/put)	no (poll returns null)
Capacity bound	available (back-pressure)	always unbounded
Mechanism	locks + condition waits	lock-free CAS
Use case	producer-consumer hand-off	high-throughput non-blocking buffer

// consumer must wait for work -> BlockingQueue
Task t = blockingQueue.take();

// poll-and-move-on, never wait -> ConcurrentLinkedQueue
Task t2 = concurrentQueue.poll();

Choose BlockingQueue for classic producer-consumer with back-pressure, and ConcurrentLinkedQueue when threads should drain available work without ever blocking.

Because null is overloaded as the "queue is empty" signal: poll() and peek() return null when there's nothing to return. Allowing a real null element would make that signal ambiguous — you couldn't distinguish "empty" from "the head happens to be null."

Queue<String> q = new ArrayDeque<>();
q.offer(null);   // NullPointerException
// if null were allowed, q.poll() == null would be ambiguous

ArrayDeque, PriorityQueue, ConcurrentLinkedQueue, and the blocking queues all reject null. The lone exception is LinkedList (a pre-Queue class), which is one more reason not to use it as a queue.

A normal iterator (or for-each) goes head to tail. Deque adds descendingIterator(), which walks tail to head — handy when a deque is used as a stack and you want top-to-bottom order, or to reverse without copying.

Deque<Integer> d = new ArrayDeque<>(List.of(1, 2, 3));

for (int x : d) System.out.print(x);          // 123 (head -> tail)

var it = d.descendingIterator();
while (it.hasNext()) System.out.print(it.next()); // 321 (tail -> head)

There's no random access on a Deque (no get(i)), so these two iterators are how you traverse it. Structurally modifying the deque during iteration throws ConcurrentModificationException.

It depends on which method family you call. The returning family yields null; the throwing family raises NoSuchElementException.

Queue<Integer> q = new ArrayDeque<>();   // empty

q.poll();      // null   (returning form)
q.peek();      // null   (returning form)
q.remove();    // NoSuchElementException (throwing form)
q.element();   // NoSuchElementException (throwing form)

So check with isEmpty() or use poll/peek when emptiness is expected, and reserve remove/element for cases where an empty queue means a programming error you want surfaced loudly.