These are the notes for Java episode 33. Lists, sets and maps don't care who came first, but a ticket counter, an undo button and a hospital emergency room do, each in a different way. We serve a long line with ArrayList.remove(0) and watch it crawl, then invent the queue (first in, first out) on a circular array, the stack (last in, first out) for undo, the deque (both ends), and the priority queue (most important first) with the heap inside it. Every example was run with javac 21.
The problem: serving a line with a list
At a railway ticket counter, the front person is served, then everyone steps forward. With an ArrayList, that's remove(0):
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
List<Integer> line = new ArrayList<>();
for (int i = 0; i < 150_000; i++) line.add(i);
long t = System.nanoTime();
while (!line.isEmpty()) line.remove(0); // serve the first person
System.out.println("ArrayList remove(0): " + (System.nanoTime() - t) / 1_000_000 + " ms");
ArrayDeque<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < 150_000; i++) queue.offer(i);
t = System.nanoTime();
while (!queue.isEmpty()) queue.poll();
System.out.println("ArrayDeque poll(): " + (System.nanoTime() - t) / 1_000_000 + " ms");
}
}
Output:
ArrayList remove(0): 889 ms
ArrayDeque poll(): 3 ms
(Times vary by machine; the gap does not.) An ArrayList is an array: removing index 0 shifts every other item one place left. n removals × n shifts = O(n²).
The fix: a circular array (ArrayDeque)
| At a bank with a token display | In Java |
|---|---|
| People sit in numbered seats; nobody moves | items stay where they are in an array |
| "Now serving seat 7": only the display changes | a head index moves forward |
| Freed seats at the start are reused | the array wraps around: a circular array |
| Serving is instant, however long the line | ArrayDeque: O(1) at both ends |
Queue: first in, first out (FIFO)
Queue<E> is the interface; ArrayDeque is the class to use.
import java.util.ArrayDeque;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
Queue<String> counter = new ArrayDeque<>();
counter.offer("Asha");
counter.offer("Ravi");
counter.offer("Meena");
System.out.println(counter.peek() + " is next, line: " + counter);
System.out.println("Served: " + counter.poll());
System.out.println("Served: " + counter.poll());
System.out.println("Left: " + counter + ", size " + counter.size());
}
}
Output:
Asha is next, line: [Asha, Ravi, Meena]
Served: Asha
Served: Ravi
Left: [Meena], size 1
Two flavours of every operation
import java.util.ArrayDeque;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
Queue<String> counter = new ArrayDeque<>();
System.out.println(counter.poll()); // empty: null
System.out.println(counter.peek()); // empty: null
System.out.println(counter.remove()); // empty: ?
}
}
Output:
null
null
Exception in thread "main" java.util.NoSuchElementException
at java.base/java.util.ArrayDeque.removeFirst(ArrayDeque.java:361)
at java.base/java.util.ArrayDeque.remove(ArrayDeque.java:522)
at Main.main(Main.java:9)
| Action | Returns a special value | Throws an exception |
|---|---|---|
| add at the back | offer(e) → false if full |
add(e) |
| remove the front | poll() → null if empty |
remove() → NoSuchElementException |
| look at the front | peek() → null if empty |
element() → NoSuchElementException |
Pick one style and check isEmpty() before taking.
Stack: last in, first out (LIFO)
A pile of plates: you push a plate on top and pop the top one. Undo works the same way: the last change is undone first.
Why not the old Stack class?
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Stack<String> undo = new Stack<>();
undo.push("type Hello");
undo.push("bold");
undo.push("delete line");
System.out.println("Undo: " + undo.pop());
undo.add(0, "sneaky"); // Stack is a Vector: any index works
System.out.println(undo + " " + undo.get(0));
undo.clear();
undo.pop();
}
}
Output:
Undo: delete line
[sneaky, type Hello, bold] sneaky
Exception in thread "main" java.util.EmptyStackException
at java.base/java.util.Stack.peek(Stack.java:103)
at java.base/java.util.Stack.pop(Stack.java:85)
at Main.main(Main.java:13)
java.util.Stack (1996) extends Vector, so it also has add(index, e), get(index) and more: anyone can break LIFO. Its methods are synchronized (slower), and an empty pop() throws EmptyStackException. The Java documentation recommends Deque instead.
A stack with ArrayDeque
import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
public static void main(String[] args) {
Deque<String> undo = new ArrayDeque<>();
undo.push("type Hello");
undo.push("bold");
undo.push("delete line");
System.out.println(undo + " top: " + undo.peek());
System.out.println("Undo: " + undo.pop());
System.out.println("Undo: " + undo.pop());
System.out.println("Left: " + undo);
}
}
Output:
[delete line, bold, type Hello] top: delete line
Undo: delete line
Undo: bold
Left: [type Hello]
| Stack method | Meaning |
|---|---|
push(e) |
add on top |
pop() |
remove the top (throws NoSuchElementException if empty) |
peek() |
look at the top (null if empty) |
A real use: checking brackets
Every opening bracket is pushed; every closing bracket must match the one popped from the top; at the end the stack must be empty. Compilers and editors do exactly this.
import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
static boolean balanced(String s) {
Deque<Character> st = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') st.push(c);
else if (c == ')' || c == ']' || c == '}') {
if (st.isEmpty()) return false;
char open = st.pop();
if ((c == ')' && open != '(') || (c == ']' && open != '[')
|| (c == '}' && open != '{')) return false;
}
}
return st.isEmpty();
}
public static void main(String[] args) {
for (String s : new String[] { "{a[i] = (b + c);}", "(a + b]", "((x)" }) {
System.out.println(s + " -> " + balanced(s));
}
}
}
Output:
{a[i] = (b + c);} -> true
(a + b] -> false
((x) -> false
Deque: a double-ended queue
ArrayDeque was a queue and a stack because it implements Deque: add and remove at both ends.
import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
public static void main(String[] args) {
Deque<String> coach = new ArrayDeque<>();
coach.offerLast("Ravi");
coach.offerLast("Meena");
coach.offerFirst("Asha"); // senior citizen: front of the line
coach.offerLast("Kabir");
System.out.println(coach);
System.out.println(coach.pollFirst() + " boards, " + coach.pollLast() + " leaves");
System.out.println(coach.peekFirst() + " " + coach.peekLast() + " " + coach);
}
}
Output:
[Asha, Ravi, Meena, Kabir]
Asha boards, Kabir leaves
Ravi Meena [Ravi, Meena]
| Front | Back |
|---|---|
offerFirst(e) / addFirst(e) / push(e) |
offerLast(e) / addLast(e) / offer(e) |
pollFirst() / removeFirst() / pop() / poll() |
pollLast() / removeLast() |
peekFirst() / peek() |
peekLast() |
PriorityQueue: most important first
In an emergency room, arrival order is the wrong rule:
import java.util.ArrayDeque;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
Queue<Integer> er = new ArrayDeque<>(); // severity: 1 = most serious
er.offer(4); // sprained ankle
er.offer(1); // heart attack
er.offer(3); // high fever
er.offer(2); // broken arm
while (!er.isEmpty()) System.out.print(er.poll() + " ");
System.out.println();
}
}
Output:
4 1 3 2
A heart attack (severity 1) waits behind a sprained ankle (4). A PriorityQueue always hands out the smallest item first:
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) {
PriorityQueue<Integer> er = new PriorityQueue<>(); // severity: 1 = most serious
er.offer(4); // sprained ankle
er.offer(2); // broken arm
er.offer(5); // small cut
er.offer(1); // heart attack
er.offer(3); // high fever
System.out.println("Inside: " + er + ", next: " + er.peek());
while (!er.isEmpty()) System.out.print(er.poll() + " ");
System.out.println();
}
}
Output:
Inside: [1, 2, 5, 4, 3], next: 1
1 2 3 4 5
poll gives 1, 2, 3, 4, 5, but printing the queue shows [1, 2, 5, 4, 3]: it is not sorted. Only the front is guaranteed.
The heap inside
A PriorityQueue is a binary min-heap stored in an array:
1 index 0
/ \
2 5 index 1, 2
/ \
4 3 index 3, 4 array: [1, 2, 5, 4, 3]
- Heap rule: every parent ≤ its children, so the smallest is at the top. Siblings are in no particular order.
- No pointers: the children of index
iare at2i + 1and2i + 2; the parent is at(i - 1) / 2. - poll: take the root, move the last item to the top, then sift down (swap with the smaller child until the rule holds).
[1, 2, 5, 4, 3]→[2, 3, 5, 4]. - offer: add at the end, then sift up (swap with the parent while smaller).
- The tree is log n levels tall:
offerandpollare O(log n),peekis O(1).
Largest first: a max-heap
import java.util.Collections;
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) {
PriorityQueue<Integer> bids = new PriorityQueue<>(Collections.reverseOrder());
for (int b : new int[] { 500, 1200, 800, 1500, 300 }) bids.offer(b);
System.out.print("Highest bids: ");
for (int i = 0; i < 3; i++) System.out.print(bids.poll() + " ");
System.out.println();
}
}
Output:
Highest bids: 1500 1200 800
Objects need an order
import java.util.PriorityQueue;
class Patient {
String name;
int severity;
Patient(String name, int severity) { this.name = name; this.severity = severity; }
}
public class Main {
public static void main(String[] args) {
PriorityQueue<Patient> er = new PriorityQueue<>();
er.offer(new Patient("Ravi", 4));
er.offer(new Patient("Asha", 1));
System.out.println(er.poll().name);
}
}
Output:
Exception in thread "main" java.lang.ClassCastException: class Patient cannot be cast to class java.lang.Comparable (Patient is in unnamed module of loader 'app'; java.lang.Comparable is in module java.base of loader 'bootstrap')
at java.base/java.util.PriorityQueue.siftUpComparable(PriorityQueue.java:643)
at java.base/java.util.PriorityQueue.siftUp(PriorityQueue.java:639)
at java.base/java.util.PriorityQueue.offer(PriorityQueue.java:330)
at Main.main(Main.java:12)
The heap must compare items. Patient has no natural order, so offering one throws ClassCastException (the same error TreeSet gave in episode 31). Episode 34 fixes it with Comparable or a Comparator passed to the constructor.
ArrayDeque refuses null
import java.util.ArrayDeque;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
Queue<String> counter = new ArrayDeque<>();
counter.offer("Asha");
counter.offer(null);
System.out.println(counter);
}
}
Output:
Exception in thread "main" java.lang.NullPointerException
at java.base/java.util.ArrayDeque.addLast(ArrayDeque.java:302)
at java.base/java.util.ArrayDeque.offerLast(ArrayDeque.java:351)
at java.base/java.util.ArrayDeque.offer(ArrayDeque.java:507)
at Main.main(Main.java:8)
poll() uses null to mean "empty", so ArrayDeque (and PriorityQueue) reject null elements.
Which one?
| Need | Use | Methods | Cost |
|---|---|---|---|
| First in, first out | Queue<E> q = new ArrayDeque<>() |
offer, poll, peek |
O(1) |
| Last in, first out | Deque<E> s = new ArrayDeque<>() |
push, pop, peek |
O(1) |
| Both ends | Deque<E> d = new ArrayDeque<>() |
offerFirst, pollLast, ... |
O(1) |
| Most important first | PriorityQueue<E> |
offer, poll, peek |
O(log n) / O(1) peek |
LinkedList also implements Queue and Deque (and allows null), but ArrayDeque is faster and uses less memory.
Common mistakes (and the real error messages)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
list.remove(0) as a queue |
no error; 150,000 removals are slow | every item shifts | ArrayDeque.poll() |
queue.remove() on an empty queue |
java.util.NoSuchElementException |
remove throws when empty |
poll() + null check, or isEmpty() |
new Stack<>() and pop() when empty |
java.util.EmptyStackException |
old Vector-based class | ArrayDeque + isEmpty() |
printing a PriorityQueue to see its order |
no error; [1, 2, 5, 4, 3] |
a heap, not a sorted list | poll in a loop |
new PriorityQueue<Patient>() then offer |
ClassCastException: class Patient cannot be cast to class java.lang.Comparable |
can't compare Patients | Comparable / Comparator (episode 34) |
queue.offer(null) on an ArrayDeque |
java.lang.NullPointerException |
null means "empty" | don't store null |
Mini project: browser back and forward
Two stacks: visiting a page pushes the current one onto back and clears forward; Back moves the current page to forward.
import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
static Deque<String> back = new ArrayDeque<>(), forward = new ArrayDeque<>();
static String current = "home";
static void visit(String page) { back.push(current); current = page; forward.clear(); }
static void goBack() { if (!back.isEmpty()) { forward.push(current); current = back.pop(); } }
static void goForward() { if (!forward.isEmpty()) { back.push(current); current = forward.pop(); } }
public static void main(String[] args) {
visit("java"); visit("collections"); visit("queues");
goBack(); goBack();
System.out.println("Now: " + current + ", back " + back + ", forward " + forward);
goForward();
visit("heaps");
System.out.println("Now: " + current + ", back " + back + ", forward " + forward);
}
}
Output:
Now: java, back [home], forward [collections, queues]
Now: heaps, back [collections, java, home], forward []
Practice
- Reverse the word
"syntax"using a stack. - Simulate a printer queue of 5 jobs, printing each as it's served.
- Find the 3 largest numbers in
{4, 19, 7, 42, 15, 8}with a PriorityQueue. - Check whether
"([]{()})"and"(]"are balanced (reuse the bracket checker).
Solutions
import java.util.*;
public class Main {
public static void main(String[] args) {
Deque<Character> st = new ArrayDeque<>();
for (char c : "syntax".toCharArray()) st.push(c);
StringBuilder sb = new StringBuilder();
while (!st.isEmpty()) sb.append(st.pop());
System.out.println(sb);
Queue<String> printer = new ArrayDeque<>(List.of("job1", "job2", "job3", "job4", "job5"));
while (!printer.isEmpty()) System.out.print("printing " + printer.poll() + "; ");
System.out.println();
PriorityQueue<Integer> top = new PriorityQueue<>(Collections.reverseOrder());
for (int x : new int[] { 4, 19, 7, 42, 15, 8 }) top.offer(x);
System.out.println(top.poll() + " " + top.poll() + " " + top.poll());
}
}
Output:
xatnys
printing job1; printing job2; printing job3; printing job4; printing job5;
42 19 15
4. "([]{()})" → true, "(]" → false.
Quick quiz
Deque<Integer> d = new ArrayDeque<>();
d.push(1);
d.push(2);
d.offer(3);
System.out.println(d.pop() + " " + d.pollLast() + " " + d);
A) 1 3 [2] B) 2 3 [1] C) 3 1 [2] D) 2 1 [3]
Answer
B. push adds at the front, offer at the back: [2, 1, 3]. pop takes the front (2), pollLast the back (3).
2 3 [1]
Interview questions
- Queue vs Stack? FIFO (first in, first out) vs LIFO (last in, first out).
- Why prefer ArrayDeque over Stack?
StackextendsVector: synchronized, exposes index access that breaks LIFO, and is legacy.ArrayDequeis faster and does only what a deque should. - ArrayDeque vs LinkedList as a queue? ArrayDeque: a circular array, better cache use, less memory, no nulls. LinkedList: node per element, allows null.
- poll vs remove? On an empty queue
pollreturnsnull;removethrowsNoSuchElementException. - How is PriorityQueue implemented? A binary heap in an array; children of
iat2i + 1,2i + 2; offer/poll O(log n), peek O(1). - Is a PriorityQueue sorted? No. Only the head is guaranteed to be the smallest; iteration order is heap order.
- How do you make a max-heap?
new PriorityQueue<>(Collections.reverseOrder())or a reversedComparator. - Give real uses of a stack. Undo, browser back, bracket matching, function call stack, expression evaluation, DFS.
- Give real uses of a priority queue. Scheduling, Dijkstra's shortest path, top-k problems, merging sorted lists.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Queue | A line: first in, first out | ticket counter |
| FIFO | First in, first out | offer then poll |
| offer / poll / peek | Join the back / take the front / look at the front | q.poll() |
| NoSuchElementException | Thrown by remove/element on an empty queue |
q.remove() |
| Circular array | An array whose end wraps around to its start | inside ArrayDeque |
| Head index | The position of the front item | "now serving seat 7" |
| ArrayDeque | A resizable circular-array deque | new ArrayDeque<>() |
| Stack | A pile: last in, first out | undo history |
| LIFO | Last in, first out | plates |
| push / pop | Add on top / remove the top | s.push("bold") |
java.util.Stack |
Legacy Vector-based stack; avoid | EmptyStackException |
| Deque | Double-ended queue: add/remove at both ends | offerFirst, pollLast |
| PriorityQueue | Hands out the smallest (highest-priority) item first | emergency room |
| Heap (binary min-heap) | A tree where every parent ≤ its children, stored in an array | [1, 2, 5, 4, 3] |
| Sift down / sift up | Swapping an item down/up until the heap rule holds | after poll / offer |
| Max-heap | Largest on top | Collections.reverseOrder() |
| O(log n) | Grows by one step each time n doubles | heap height |
| Balanced brackets | Every opener closed by the matching closer, in order | {a[i]} |
Summary
ArrayList.remove(0)shifts every item: O(n) per removal.- ArrayDeque is a circular array, O(1) at both ends: a queue (
offer,poll,peek), a stack (push,pop,peek) and a deque. - Empty queue:
poll/peek→null;remove/element→NoSuchElementException. Nonullelements. - Avoid the legacy
Stackclass. - PriorityQueue is a binary heap:
pollgives the smallest, O(log n); its printed order is not sorted;Collections.reverseOrder()for largest first. - Objects in a PriorityQueue need an order: Comparable vs Comparator (episode 34).