JAVA / COLLECTIONS
Queue, Deque and stack-or-queue discipline
Model FIFO and LIFO as end-choices: use Queue and Deque methods deliberately, pick ArrayDeque over Stack, and know which calls throw and which return null.
What you will learn
- Pick offer/poll/peek where empty is expected, add/remove/element where it is a bug.
- Use one ArrayDeque as a stack (push/pop) or a queue (offer/poll), never as both.
- Read peek() as peekFirst(): the head is the newest in LIFO, the oldest in FIFO.
- Know why ArrayDeque bans null: poll() reserves null to mean the queue is empty.
Understanding Queue, Deque and stack-or-queue discipline
Collection describes what is inside a container; Queue describes which end you are allowed to touch. Every Queue carries two parallel method sets that do the same work and differ only in how they report failure: add, remove and element throw (IllegalStateException, NoSuchElementException), while offer, poll and peek answer with false or null. The duplication is not an accident of history, it is because emptiness and fullness are a normal state in some designs (a worker loop draining until nothing is left, a bounded handoff that must not block) and a programming error in others, and one method cannot serve both without lying about severity.
Deque opens the second end and makes every operation say which end it touches: addFirst and addLast, pollFirst and pollLast, peekFirst and peekLast. On top of that, push, pop and peek are plain aliases for the head trio addFirst, removeFirst and peekFirst, which is why a single ArrayDeque is a stack when insertion and removal hit the same end and a queue when they hit opposite ends. The type enforces nothing here: FIFO and LIFO are disciplines you maintain by consistently choosing one pair of operations, and a stray addLast inside otherwise stack-shaped code produces a structure that is neither.
For both roles the default implementation is ArrayDeque, a circular array with head and tail indices, so both ends are amortised O(1) with no per-element node object and no pointer chasing. It rejects null on purpose: poll() and peek() already use null to mean "nothing there", so a stored null would make the answer ambiguous, which is exactly the trap LinkedList leaves open because it does permit null. Prefer ArrayDeque to java.util.Stack, which extends Vector, synchronises every call whether you need it or not, and iterates bottom-to-top so its toString prints the top of the stack last.
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.NoSuchElementException;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
Queue<String> fifo = new ArrayDeque<>();
fifo.offer("a");
fifo.offer("b");
fifo.offer("c");
System.out.println("fifo view: " + fifo + " head=" + fifo.peek());
Deque<String> lifo = new ArrayDeque<>();
lifo.push("a");
lifo.push("b");
lifo.push("c");
System.out.println("lifo view: " + lifo + " head=" + lifo.peek());
System.out.print("fifo drain:");
while (!fifo.isEmpty()) {
System.out.print(" " + fifo.poll());
}
System.out.println();
System.out.print("lifo drain:");
while (!lifo.isEmpty()) {
System.out.print(" " + lifo.pop());
}
System.out.println();
System.out.println("poll on empty: " + fifo.poll());
try {
fifo.element();
} catch (NoSuchElementException e) {
System.out.println("element on empty: " + e.getClass().getSimpleName());
}
}
}A Queue or Deque only fixes which ends you may touch; FIFO and LIFO are disciplines you create by consistently choosing methods, not guarantees the type hands you.
Worked examples
A capped most-recent list on both ends
Uses one end of a Deque to insert and the other to evict, which is the case where you genuinely need both ends rather than a stack or a queue.
import java.util.ArrayDeque;
import java.util.Deque;
public class RecentFiles {
private static final int MAX = 3;
static void visit(Deque<String> history, String file) {
history.remove(file);
history.addFirst(file);
if (history.size() > MAX) {
history.removeLast();
}
}
public static void main(String[] args) {
Deque<String> history = new ArrayDeque<>();
visit(history, "Main.java");
visit(history, "Util.java");
visit(history, "Test.java");
System.out.println("filled: " + history);
visit(history, "Main.java");
System.out.println("revisit: " + history);
visit(history, "Api.java");
System.out.println("overflow: " + history);
}
}Example explained
Line 1history.remove(file) resolves to remove(Object), a linear scan that deletes the first match; dropping the argument by mistake calls remove() and silently discards the head instead.
Line 2addFirst puts the newest entry at the head, so iteration and toString read most-recent-first without any sorting.
Line 3removeLast evicts at the opposite end in constant time, which is the reason a Deque fits here and an ArrayList does not.
Line 4Passing a null filename would throw NullPointerException at addFirst, because ArrayDeque refuses null outright.
Why ArrayDeque forbids null
Shows that a null element stored in a LinkedList queue makes poll()'s return value ambiguous, and that ArrayDeque prevents the situation instead of coping with it.
import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Queue;
public class NullTrap {
public static void main(String[] args) {
Queue<String> linked = new LinkedList<>();
linked.offer(null);
System.out.println("size after offer(null): " + linked.size());
System.out.println("poll(): " + linked.poll() + ", empty now: " + linked.isEmpty());
Queue<String> array = new ArrayDeque<>();
try {
array.offer(null);
} catch (NullPointerException e) {
System.out.println("ArrayDeque.offer(null): NullPointerException");
}
}
}Example explained
Line 1LinkedList permits null, so offer(null) stores a real element and size becomes 1.
Line 2poll() then returns null from a non-empty queue, the identical signal it gives for an empty one, so the popular loop while ((x = q.poll()) != null) would stop with items still queued.
Line 3String concatenation evaluates left to right, so poll() runs before isEmpty() and the printed true reflects the state after the removal.
Line 4ArrayDeque rejects the null at insertion time, which is what keeps its null returns unambiguous forever after.
PriorityQueue is a Queue but not FIFO
Demonstrates that implementing Queue says nothing about arrival order, and that a heap's iteration order is not its removal order.
import java.util.PriorityQueue;
import java.util.Queue;
public class PriorityIsNotFifo {
public static void main(String[] args) {
Queue<Integer> pq = new PriorityQueue<>();
for (int n : new int[] {3, 1, 4, 2}) {
pq.offer(n);
}
System.out.println("inserted: 3 1 4 2");
System.out.println("peek: " + pq.peek());
System.out.println("toString: " + pq);
System.out.print("poll order:");
while (!pq.isEmpty()) {
System.out.print(" " + pq.poll());
}
System.out.println();
}
}Example explained
Line 1peek() returns 1 rather than the first-inserted 3, because the head of a PriorityQueue is the smallest element, not the oldest.
Line 2toString walks the backing binary heap array in index order, so 4 is printed before 3; the iterator promises no ordering at all.
Line 3Only repeated poll() yields ascending order, and each poll costs O(log n) because the heap has to sift the last element back down.
Important notes
ArrayDeque is unbounded and unsynchronised, so its offer never returns false and its add never throws IllegalStateException; the false return only earns its keep on bounded queues such as ArrayBlockingQueue.
ArrayDeque's iterator detects interference, so calling poll() inside a for-each over the same deque throws ConcurrentModificationException; drain with a while (!d.isEmpty()) loop instead.
Common mistakes
Assuming all the retrieval methods return null when the queue is empty: element() and remove() throw NoSuchElementException, so a guard written with element() blows up on exactly the empty case it was supposed to handle.
Declaring a field as Deque and then calling addFirst in one code path and addLast in another: the structure is neither FIFO nor LIFO, and the wrong-order bug only surfaces once both paths run in the same session.
Reaching for java.util.Stack for LIFO work and then printing it or iterating it: Stack inherits Vector's index order, so it iterates bottom-to-top, the reverse of pop order, while an ArrayDeque used with push/pop iterates top-first.
Try it yourself
Change, predict, then run
Using an ArrayDeque<Character> as a stack, write a matcher that reports true for "([]{})" and false for "([)]": push each opening bracket, pop on each closing one and check the pair, then require the deque to be empty at the end. Now replace push with addLast while leaving pop untouched, and confirm that even "([])" fails, because insertion and removal are hitting opposite ends.
Open the Java workspaceCheck your understanding
A Deque<String> d = new ArrayDeque<>() receives d.push("a"); d.push("b"); d.push("c"); and the next call is d.poll(). What happens?
- It returns "a", because poll() removes from the tail, the end push() never touched.
- It returns "c", because push() is addFirst() and poll() is pollFirst(), so both act on the head.
- It returns "a", because poll() is FIFO and push() appended to the tail the way List.add() does.
- It throws IllegalStateException, because stack and queue methods cannot be mixed on one Deque.
Show answer
push() is specified as addFirst(), so after pushing a, b, c the deque reads [c, b, a] with c at the head, and poll() is pollFirst(), which hands back exactly what pop() would. The third option is tempting because List.add() appends, but Deque.push() deliberately inserts at the head so push/pop/peek form a stack; and nothing throws, because a Deque never enforces a discipline on your behalf.