Queue, Deque and Stack
At Brew Bar, customers are served in the order they arrive, while the barista's "undo" button removes the item added most recently. Those are opposite orders: first in, first out versus last in, first out. Java covers both with one flexible class.
The rule
A queue serves the oldest first; a stack serves the newest first.
A queue is FIFO: first in, first out, like the line at the counter. The Queue interface names the operations:
Queue<String> line = new ArrayDeque<>();
line.offer("Asha"); // join the back
line.offer("Ben");
line.offer("Chen");
System.out.println(line.peek()); // Asha: look at the front, keep her
System.out.println(line.poll()); // Asha: serve and remove her
System.out.println(line); // [Ben, Chen]A stack is LIFO: last in, first out, like a pile of clean cups where you take the top one. Undo history works the same way:
Deque<String> undo = new ArrayDeque<>();
undo.push("Latte");
undo.push("Muffin");
undo.push("Scone");
System.out.println(undo.pop()); // Scone: the last thing added
System.out.println(undo.peek()); // Muffin: now on topA Deque (double-ended queue, said "deck") allows adding and removing at both ends, with methods like offerFirst, offerLast, pollFirst and pollLast. That is why one class, ArrayDeque, serves as both a queue and a stack. Java also has an old Stack class, but its own documentation recommends a Deque instead, so prefer ArrayDeque in new code.
On an empty collection, the methods split into two families:
| Action | Returns a special value | Throws an exception |
|---|---|---|
| look at the front | peek() gives null |
element() |
| remove the front | poll() gives null |
remove(), pop() |
ArrayDeque does not accept null elements, so a null from poll always means "empty".
The shortcut
Ask "Who should come out next: the one who waited longest, or the one who arrived last?" Longest waiting → queue: offer and poll. Arrived last → stack: push and pop. Declare either as ArrayDeque.
Customers arriving
Fairness means the longest wait goes first, so a queue:
line.offer(name)when they arrive.
Drills
Answer fast — trust the rule.
A queue receives offer("Asha"), offer("Ben"), offer("Chen"). What does poll() return?
A deque receives push("A"), push("B"), push("C"). What does pop() return?
Deque<String> d = new ArrayDeque<>(); d.offerLast("A"); d.offerFirst("B"); What does d.pollLast() return?
What does poll() do on an empty queue?
Remember
- A queue serves the oldest first (
offer,poll); a stack serves the newest first (push,pop). - Use
ArrayDequefor both, rather than the oldStackclass. - Traps:
popon an empty deque throws, and mixing up which end you are reading.