Queue and Deque: Ends, Not Indexes

A picker needs the next order. You stored them in an ArrayList and called remove(0). That compiles. It also slides every remaining order on every pick, and it invites get(17) on a structure whose only honest question was “who is next?”

Queue and Deque are the contracts for the ends, not for indexes. The Collections Roadmap already owns fail-fast, optional operations, and sequenced as a name. This post is the six Queue methods, the Deque pairs at both ends, why null is usually illegal, and which JDK class you actually new. Snippets use a small order helper; the lab writes it out with the series records.

Queue means insert, take, look

Queue shipped in Java 5. Three jobs, two spellings each:

Job	Throws on failure	Special value on failure
Insert	`add(e)` — `IllegalStateException` if no space	`offer(e)` — `false` if no space
Take	`remove()` — `NoSuchElementException` if empty	`poll()` — `null` if empty
Look	`element()` — `NoSuchElementException` if empty	`peek()` — `null` if empty

That table is the interface. There is no get(i). There is no set. A queue is not a list with the first index highlighted.

Queue<Order> picks = new ArrayDeque<>();
picks.offer(order("o-100", "SKU-1", "19.99"));
picks.offer(order("o-101", "SKU-2", "12.00"));

Order next = picks.poll();   // o-100 — FIFO
Order look = picks.peek();   // o-101 — still in the queue

offer / poll / peek are the methods you want in application code. They stay honest when the queue is empty or, on a bounded implementation, full. add / remove / element are the “this must succeed” variants — useful when an empty queue is a bug, noisy when it is a normal state.

On an ArrayDeque both insert columns succeed for a real Order. The interesting split is empty take:

Queue<Order> idle = new ArrayDeque<>();
Order viaPoll = idle.poll();       // null
Order viaPeek = idle.peek();       // null
// idle.remove();                  // NoSuchElementException
// idle.element();                 // NoSuchElementException

Program to Queue, construct ArrayDeque unless a later section names a reason not to.

Exception versus special value

The two columns exist because queues come in two capacities.

On an unbounded queue (ArrayDeque, PriorityQueue, ConcurrentLinkedQueue), offer never returns false for space. add never throws IllegalStateException for space. The only insert failure you will see is NullPointerException if the implementation forbids null.

On a bounded queue (ArrayBlockingQueue with a fixed length), the difference is the whole API:

Queue<Order> lane = new ArrayBlockingQueue<>(1);
lane.offer(order("o-100", "SKU-1", "19.99")); // true
boolean accepted = lane.offer(order("o-101", "SKU-2", "12.00")); // false
lane.add(order("o-102", "SKU-3", "5.00"));    // IllegalStateException

Empty is the other half. poll() and peek() return null. remove() and element() throw NoSuchElementException. Mixing the columns is how people write if (queue.remove() == null) and then never hit the null branch.

Note: offer returning false is not “try again later” on a blocking queue. Waiting for space is put / take on BlockingQueue. offer is the non-blocking probe.

Deque: the same pairs, both ends

Deque shipped in Java 6. It is a Queue. It also names the other end. Java 21’s Sequenced Collections give those ends a shared vocabulary (getFirst, getLast, reversed); Deque already had the full insert / take / look grid.

Job	First (head)	Last (tail)
Insert, or throw	`addFirst`	`addLast`
Insert, or `false`	`offerFirst`	`offerLast`
Take, or throw	`removeFirst`	`removeLast`
Take, or `null`	`pollFirst`	`pollLast`
Look, or throw	`getFirst`	`getLast`
Look, or `null`	`peekFirst`	`peekLast`

Queue methods on a deque map onto one end each, so a Deque used as a Queue stays FIFO:

Queue.add / offer     →  addLast / offerLast
Queue.remove / poll   →  removeFirst / pollFirst
Queue.element / peek  →  getFirst / peekFirst

Insert at the tail, take from the head. That is a queue. Insert and take at the same end and it is a stack. The type did not change. The end you touch did.

Deque<Order> lane = new ArrayDeque<>();
lane.addLast(order("o-100", "SKU-1", "19.99"));
lane.addLast(order("o-101", "SKU-2", "12.00"));
lane.addFirst(order("o-099", "SKU-0", "4.00")); // rush, jump the line

Order first = lane.pollFirst(); // o-099
Order last  = lane.peekLast();  // o-101

Indexes are the wrong primitive. If the hot question is “element 17,” you wanted a List. If the hot question is “the oldest” or “the newest,” you wanted a deque.

Stack-shaped methods sit on Deque

Deque also spells LIFO in textbook names:

Method	Means
`push(e)`	`addFirst(e)`
`pop()`	`removeFirst()` — throws if empty
`peek()`	`peekFirst()` — `null` if empty

Deque<Order> undo = new ArrayDeque<>();
undo.push(order("o-100", "SKU-1", "19.99"));
undo.push(order("o-100-edit", "SKU-1", "17.99"));
Order rolledBack = undo.pop(); // o-100-edit

Same three orders, two disciplines. FIFO takes o-100 first. LIFO takes o-102 first. The collection class did not change.

Deque<Order> fifo = new ArrayDeque<>();
Deque<Order> lifo = new ArrayDeque<>();
for (Order o : List.of(
        order("o-100", "SKU-1", "19.99"),
        order("o-101", "SKU-2", "12.00"),
        order("o-102", "SKU-3", "5.00"))) {
    fifo.offerLast(o);
    lifo.push(o);
}
fifo.pollFirst().id(); // o-100
lifo.pop().id();       // o-102

That is the stack. It is not java.util.Stack. Stack extends Vector: a synchronized, indexable list from 1.0. Every push locks the whole vector. You can insertElementAt in the middle and still call it a stack. Legacy Collections is where that family belongs. Here the rule is one line: a stack in 2026 is Deque plus ArrayDeque.

pop() throws. pollFirst() returns null. Pick the column the same way you would on a queue.

Lab: pick lane and undo

Same checkout records as the rest of this series. If the shape is new, Java Records covers it.

public record Order(
        String id,
        String customerEmail,
        List<LineItem> items,
        BigDecimal total,
        boolean active) {}

public record LineItem(String sku, int quantity, BigDecimal unitPrice) {}

A packing station holds a FIFO lane of active orders and a LIFO undo stack of the last pick. Both are deques. The lane is used as a Queue; undo is used as a stack.

static Order order(String id, String sku, String total) {
    BigDecimal price = new BigDecimal(total);
    return new Order(
            id,
            id + "@ex.com",
            List.of(new LineItem(sku, 1, price)),
            price,
            true);
}

Deque<Order> lane = new ArrayDeque<>();
Deque<Order> undo = new ArrayDeque<>();

lane.offer(order("o-100", "SKU-1", "19.99"));
lane.offer(order("o-101", "SKU-2", "12.00"));
lane.offer(order("o-102", "SKU-3", "5.00"));

Order picked = lane.poll();          // o-100
if (picked != null) {
    undo.push(picked);
}

Order stillNext = lane.peek();       // o-101
Order undone = undo.pop();           // o-100
lane.offerFirst(undone);             // back at the head

offerFirst after undo restores FIFO without scanning for an index. poll on an empty lane returns null — the picker waits, you do not catch NoSuchElementException as control flow.

Empty-lane take with the throwing column looks like a bug, because it is:

Order mustExist = lane.remove(); // NoSuchElementException when idle

Use poll at the station. Use remove in a test that just enqueued and must not be empty.

After that undo, the lane is FIFO again and the stack is empty:

lane : o-100, o-101, o-102
undo : (empty)
next poll from lane → o-100

Why most queues refuse null

poll and peek already use null to mean empty. If a payload null were legal, you could not tell “the queue had a null” from “the queue had nothing.” That is not a style preference. It is the special-value column becoming unreadable.

ArrayDeque rejects null with NullPointerException. So do PriorityQueue, ConcurrentLinkedQueue, and the blocking queues. The roadmap matrix lists the same no-nulls rule.

LinkedList allows null. That is a reason to skip it as a queue, not a feature:

Queue<Order> liar = new LinkedList<>();
liar.offer(null);
Order taken = liar.poll(); // null — was it empty, or a null order?

A queue that accepts null makes poll lie. Model absence with an empty queue, an Optional at the boundary, or a sentinel Order you named. Do not store null.

Implementations at a glance

The interface is the job. The class is the delivery. Comparison only — internals of the ring live in the ArrayDeque post; the heap lives in PriorityQueue.

Type	Nulls	Order	Threads	Notes
`ArrayDeque`	no	FIFO as a queue; both ends as a deque	no	Default stack and queue
`LinkedList`	yes	FIFO as a queue	no	Also a `List`. Slow ends vs `ArrayDeque`. Skip as a queue
`PriorityQueue`	no	not FIFO — heap order	no	Next-best, not arrival order
`ConcurrentLinkedQueue`	no	FIFO	lock-free	Concurrent cousin; no blocking
`ArrayBlockingQueue`	no	FIFO	blocking	Bounded hand-off

PriorityQueue implements Queue and will compile anywhere a Queue is required. It will not give you the order you inserted. If the method says Queue and the caller needed FIFO, the signature lied. Use Deque or document “priority, not arrival.”

BlockingQueue is a Queue. put waits for space; take waits for an element. That is the worker hand-off. This post does not walk drainTo or fairness — that is BlockingQueue: Hand Off Work Without a Busy Wait. Wrapping ArrayDeque in Collections.synchronizedDeque does not give you waiting.

When Queue or Deque is the wrong type

Skip these contracts when the hot operation is not an end.

You need index i — picks.get(3), shuffle, binary search, a List parameter. That is List. LinkedList implements both List and Deque and then makes get(i) an O(n) walk. Do not pick it to keep both APIs “just in case.”
You need uniqueness. A queue of SKUs that must not repeat is a Set, or a queue plus a Set of ids. Queue allows duplicates.
You need next-best, not next-arrived. That is PriorityQueue, not a FIFO Deque.
You need another thread to wait. That is BlockingQueue, not a synchronized wrapper around ArrayDeque.
You need a null element. You probably need a better model. If you insist, LinkedList will compile and poll will be ambiguous.

A Queue is not a List. Passing an ArrayDeque to a method that asks for List<Order> should not compile, and that is the point:

void reprint(List<Order> page) { /* indexes, subList, RandomAccess */ }

Deque<Order> lane = new ArrayDeque<>();
// reprint(lane); // does not compile — pick a List if you need a page
reprint(new ArrayList<>(lane)); // snapshot copy, not a live lane

Copying into an ArrayList is a snapshot. The lane can keep moving. Views vs copies are on the roadmap; do not pretend the copy is the queue.

Interview lens

Interviewers want the three pairs, the two columns, and a default class. They do not want you to recite every Deque method.

Complexity they expect without a table. Ends on ArrayDeque: amortized O(1) insert and take. LinkedList ends: O(1) after you pay a node allocation and a pointer chase. PriorityQueue.offer / poll: O(log n). peek on any of them: O(1) (heap root or an end index). Index i on a deque: you left the ADT.

What to draw. A line with two ends. Label head and tail. Write the Queue mapping: offer at tail, poll at head. Draw the 2×3 grid: insert / take / look × throw / special value. Off to the side: “Deque = both ends; stack = same end; PriorityQueue implements Queue but is not FIFO.”

Typical questions:

Question	Honest answer
`offer` vs `add`?	`add` throws `IllegalStateException` when a bounded queue is full. `offer` returns `false`. On `ArrayDeque` both succeed (except `null`).
Why do queues reject `null`?	`poll` / `peek` already return `null` for empty. A payload `null` collides with that signal.
Stack: `Deque` or `java.util.Stack`?	`Deque` + `ArrayDeque`. `Stack` is a synchronized `Vector`.
Is a `Queue` a `List`?	No. No indexes. `LinkedList` is both and that is a trap.
`peek` vs `poll`?	Both look at the head. `peek` leaves it. `poll` removes it. Both return `null` when empty.
Is `PriorityQueue` FIFO?	No. It is a heap. Next-best, not first-in.
Where do you wait for an element?	`BlockingQueue.take`, not `ArrayDeque.poll` in a spin loop.
`remove()` on empty?	`NoSuchElementException`. Not `null`.

Wrong answer: “Queue.remove() returns null when empty.” remove() throws NoSuchElementException. poll() is the method that returns null.

Cheat sheet

Queue     insert / take / look at the head-and-tail contract
          add/remove/element throw     offer/poll/peek special value
Deque     the same pairs at first and last; also a Queue
FIFO      offerLast + pollFirst
LIFO      push/pop = addFirst/removeFirst   (not java.util.Stack)
Nulls     ArrayDeque, PriorityQueue, concurrent queues: forbidden
          LinkedList allows null — skip it as a queue
Default   Deque<Order> q = new ArrayDeque<>();
Not FIFO  PriorityQueue implements Queue anyway
Wait      BlockingQueue — different post
Java 21   Deque is SequencedCollection (getFirst/getLast/reversed)

Do:

Program to Queue or Deque. new ArrayDeque<>() unless the job is priority, blocking, or lock-free concurrent.
Use offer / poll / peek when empty or full is a normal state.
Treat a stack as a Deque. Leave java.util.Stack in the museum.

Don’t:

Call remove(0) on an ArrayList and name it a queue.
Store null so you can “mean missing.”
Assume every Queue is FIFO — ask whether the implementation is a heap.

Wrap-up

Queue is three jobs with two failure styles: throw, or return false / null. Deque is that contract at both ends, which is enough for a FIFO lane and a LIFO undo stack without a List and without java.util.Stack. Most implementations refuse null because the special-value column already spent it. ArrayDeque is the default. PriorityQueue is a Queue that is not FIFO. BlockingQueue is a Queue that can wait.

The next contract in this series is lookup by key, not by end.

Next optional step in the series Keys, values, and the live views that stay in sync with the map. Map: Keys, Values, and the Views That Stay in Sync

Queue and Deque:Ends, Not Indexes

Queue means insert, take, look

Exception versus special value

Deque: the same pairs, both ends

Stack-shaped methods sit on Deque

Lab: pick lane and undo

Why most queues refuse null

Implementations at a glance

When Queue or Deque is the wrong type

Interview lens

Cheat sheet

Wrap-up

Pick the Collection:Nulls, Order, Threads, and the Hot Operation

Sequenced Collections:First, Last, and Reversed Without the Ceremony

Stream Gatherers:Custom Intermediate Ops Without Breaking the Pipeline

Java Streams:Filter, Map, and Collect Without the Nested Loop Soup

Queue means insert, take, look

Exception versus special value

Deque: the same pairs, both ends

Stack-shaped methods sit on Deque

Lab: pick lane and undo

Why most queues refuse null

Implementations at a glance

When Queue or Deque is the wrong type

Interview lens

Cheat sheet

Wrap-up

Related posts

Pick the Collection:Nulls, Order, Threads, and the Hot Operation

Sequenced Collections:First, Last, and Reversed Without the Ceremony

Stream Gatherers:Custom Intermediate Ops Without Breaking the Pipeline

Java Streams:Filter, Map, and Collect Without the Nested Loop Soup