AdvancedJava Programming · Lesson 25 of 29 · Updated ·
Queue, Deque and PriorityQueue in Java — ArrayDeque, Heaps and Top-K
A queue is a line: the first person to join is the first to be served. This rule is called FIFO (first in, first out). A stack is a pile of plates: the last plate put on top is the first taken off, called LIFO (last in, first out). A priority queue serves the most important item first, like an emergency room. The collections lesson named these in one line each; here you learn to use them properly, because they appear in almost every coding round (BFS, bracket matching, top-K, scheduling).
1. Queue: two sets of methods
The Queue interface has two versions of each operation. One throws an exception when it cannot work; the other returns a special value (false or null).
| Operation | Throws exception | Returns special value |
|---|---|---|
| add at the back | add(e) | offer(e) → false if full |
| remove from the front | remove() | poll() → null if empty |
| look at the front | element() | peek() → null if empty |
In everyday code, use offer, poll and peek. An empty queue is normal (for example, no customers left), so returning null is easier to handle than catching an exception.
import java.util.*;
public class Main {
public static void main(String[] args) {
Queue<String> counter = new ArrayDeque<>();
counter.offer("Asha");
counter.offer("Ravi");
counter.offer("Neha");
System.out.println("next: " + counter.peek());
while (!counter.isEmpty()) {
System.out.println("served " + counter.poll());
}
System.out.println(counter.poll());
try {
counter.remove();
} catch (NoSuchElementException e) {
System.out.println("remove() on empty queue throws");
}
}
}
next: Asha
served Asha
served Ravi
served Neha
null
remove() on empty queue throws
2. Deque: a queue open at both ends
A Deque (said "deck", short for double-ended queue) lets you add and remove at both the front (head) and the back (tail). That makes it a queue and a stack in one class.
ArrayDeque is the usual choice. It stores elements in a growing circular array, so both ends are fast. The old Stack class is synchronized (slower) and extends Vector, so the Java documentation itself recommends Deque for stacks.
As a stack, push and pop both work at the head. A classic use is checking balanced brackets:
import java.util.*;
public class Main {
static boolean balanced(String s) {
Deque<Character> stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else {
if (stack.isEmpty()) return false;
char open = stack.pop();
if ((c == ')' && open != '(') || (c == ']' && open != '[') || (c == '}' && open != '{')) return false;
}
}
return stack.isEmpty();
}
public static void main(String[] args) {
for (String s : List.of("{[()]}", "([)]", "((", "()[]{}")) {
System.out.println(s + " -> " + balanced(s));
}
Deque<Integer> d = new ArrayDeque<>();
d.offerLast(2); d.offerLast(3); d.offerFirst(1);
System.out.println(d + " first=" + d.peekFirst() + " last=" + d.peekLast());
}
}
{[()]} -> true
([)] -> false
(( -> false
()[]{} -> true
[1, 2, 3] first=1 last=3
One limit: ArrayDeque does not accept null, because poll uses null to mean "empty".
3. PriorityQueue: smallest first, using a heap
A PriorityQueue always gives you the smallest element (by natural order or a Comparator) from peek and poll. Inside, it is a binary min-heap stored in an array: every parent is smaller than or equal to its children. The smallest element is always at index 0, but the rest of the array is not fully sorted.
import java.util.*;
public class Main {
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int x : new int[]{40, 10, 30, 5, 20}) pq.offer(x);
System.out.println("printed: " + pq);
System.out.println("peek: " + pq.peek());
StringBuilder out = new StringBuilder();
while (!pq.isEmpty()) out.append(pq.poll()).append(' ');
System.out.println("polled: " + out.toString().trim());
PriorityQueue<Integer> max = new PriorityQueue<>(Comparator.reverseOrder());
max.addAll(List.of(40, 10, 30, 5, 20));
System.out.println("max first: " + max.poll() + ", then " + max.poll());
}
}
printed: [5, 10, 30, 40, 20]
peek: 5
polled: 5 10 20 30 40
max first: 40, then 30
Notice: printing a PriorityQueue (or looping over it with for-each) shows the heap array, not sorted order. Only repeated poll() gives sorted order. This is a favourite trick question.
| PriorityQueue operation | Time |
|---|---|
offer, poll | O(log n) — the element moves up or down the tree |
peek | O(1) — it is always at index 0 |
contains, remove(Object) | O(n) — must search the array |
Ordering your own objects
Pass a Comparator. A hospital serves the most serious patient first; for equal severity, the one who came earlier.
import java.util.*;
record Patient(String name, int severity, int arrival) { }
public class Main {
public static void main(String[] args) {
PriorityQueue<Patient> er = new PriorityQueue<>(
Comparator.comparingInt(Patient::severity).reversed().thenComparingInt(Patient::arrival));
er.offer(new Patient("Om", 2, 1));
er.offer(new Patient("Isha", 5, 2));
er.offer(new Patient("Ravi", 5, 3));
er.offer(new Patient("Neha", 3, 4));
while (!er.isEmpty()) System.out.print(er.poll().name() + " ");
System.out.println();
}
}
Isha Ravi Neha Om
4. The top-K problem
"Find the 3 highest marks out of a million" is asked often. Sorting everything costs O(n log n). A better way: keep a min-heap of size k. For each mark, add it; if the heap grows beyond k, remove the smallest. At the end, the heap holds the k largest. This costs O(n log k), and memory is only k elements.
import java.util.*;
public class Main {
public static void main(String[] args) {
int[] marks = {67, 92, 45, 88, 73, 99, 58, 81};
int k = 3;
PriorityQueue<Integer> heap = new PriorityQueue<>();
for (int m : marks) {
heap.offer(m);
if (heap.size() > k) heap.poll(); // drop the smallest
}
List<Integer> top = new ArrayList<>(heap);
top.sort(Comparator.reverseOrder());
System.out.println("top " + k + ": " + top);
System.out.println("3rd highest: " + heap.peek());
}
}
top 3: [99, 92, 88]
3rd highest: 88
The root of the heap is the smallest of the top k, which is exactly the k-th largest — another common question.
5. Choosing the right class
| Need | Use |
|---|---|
| FIFO queue (BFS, tasks in order) | ArrayDeque |
| Stack (undo, brackets, DFS) | ArrayDeque with push / pop |
| Smallest or largest first | PriorityQueue |
| Queue shared between threads | ArrayBlockingQueue / LinkedBlockingQueue |
Need null elements or a List too | LinkedList (slower, more memory) |
Common mistakes
- Using
remove()orelement()on a queue that may be empty, and gettingNoSuchElementException. Usepoll()/peek(). - Printing or iterating a PriorityQueue and expecting sorted order.
- Forgetting that
PriorityQueueis a min-heap by default; for the largest first, passComparator.reverseOrder(). - Using the old
Stackclass in new code instead ofArrayDeque. - Adding
nullto anArrayDequeorPriorityQueue(both throwNullPointerException). - Sorting the whole array for top-K when a size-k heap is enough.
Quick recap
- Queue = FIFO; prefer
offer,poll,peek(they returnfalse/nullinstead of throwing). - Deque works at both ends;
ArrayDequeis the best queue and the best stack. PriorityQueueis a binary min-heap:peekO(1),offer/pollO(log n), printed order is not sorted.- Max-heap:
new PriorityQueue<>(Comparator.reverseOrder()). - Top-K largest: min-heap of size k, O(n log k).