Lesson 59 of 164
Queues in Java
A queue is a first in, first out (FIFO) collection: elements leave in the same order they arrived, like a line at a counter. Its main operations are:
- enqueue: add an element at the back
- dequeue: remove and return the element at the front
- peek: look at the front element without removing it
graph LR
in(["enqueue"]) --> back["back: 3"]
back --- mid["2"] --- front["front: 1"]
front --> out(["dequeue returns 1"])ArrayDeque is the queue
Use java.util.ArrayDeque. It is a resizable circular array: the elements live in one array, and the front and back indexes wrap around its ends. That makes adding and removing at both ends O(1) (amortized for adds, because the array occasionally grows). ArrayDeque implements both Queue and Deque. It rejects null elements, because null is the return value that signals "empty" for poll and peek. It is not thread-safe.
Each operation has two forms: one that throws on failure and one that returns a special value.
| Operation | Throws on failure | Returns null / false |
|---|---|---|
| enqueue at the back | addLast(x) / add(x) |
offerLast(x) / offer(x) |
| dequeue from the front | removeFirst() / remove() |
pollFirst() / poll() |
| peek front | getFirst() / element() |
peekFirst() / peek() |
| peek back | getLast() |
peekLast() |
| add at the front | addFirst(x) |
offerFirst(x) |
| remove from the back | removeLast() |
pollLast() |
| size | size(), isEmpty() |
ArrayDeque has no index access such as get(i). Iteration goes from front to back, and toString prints in that order. Because poll and peek return null on an empty queue, assigning the result to a primitive (int x = queue.pollFirst()) throws NullPointerException on an empty queue. Check isEmpty() first.
import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
public static void main(String[] args) {
Deque<String> queue = new ArrayDeque<>();
queue.addLast("a");
queue.addLast("b");
queue.addLast("c");
System.out.println("front = " + queue.peekFirst() + ", back = " + queue.peekLast() + ", size = " + queue.size());
StringBuilder out = new StringBuilder();
while (!queue.isEmpty()) {
out.append(queue.pollFirst()).append(' ');
}
System.out.println(out.toString().trim());
System.out.println("empty poll = " + queue.pollFirst());
}
}front = a, back = c, size = 3
a b c
empty poll = nullWhy not an ArrayList?
An ArrayList is only fast at its end. Removing from the front with list.remove(0) shifts every remaining element one place left, which is O(n). Draining a queue of n elements that way costs O(n²) in total. ArrayDeque.pollFirst only moves the start index, which is O(1). Both loops below return the elements in the same order. The difference is the cost of each removal, which grows with the list length for remove(0).
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
public class Main {
public static void main(String[] args) {
int n = 5;
List<Integer> list = new ArrayList<>();
Deque<Integer> deque = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
list.add(i);
deque.addLast(i);
}
StringBuilder fromList = new StringBuilder();
while (!list.isEmpty()) {
fromList.append(list.remove(0)).append(' '); // shifts every remaining element left
}
StringBuilder fromDeque = new StringBuilder();
while (!deque.isEmpty()) {
fromDeque.append(deque.pollFirst()).append(' '); // moves only the start index
}
System.out.println(fromList.toString().equals(fromDeque.toString()));
System.out.println(fromDeque.toString().trim());
}
}true
0 1 2 3 4Queue patterns
1. Breadth-first search
A queue processes items in the order they were discovered, so a search that adds neighbors to the back visits everything at distance 1 before anything at distance 2. That is breadth-first search (BFS), used for shortest paths in unweighted graphs and for level-order tree traversal.
import java.util.ArrayDeque;
import java.util.HashSet;
import java.util.Queue;
import java.util.Set;
public class Main {
// Minimum number of moves from `start` to `target` where a move is +1 or *2.
// Returns -1 when the target cannot be reached.
static int minMoves(int start, int target) {
Queue<int[]> queue = new ArrayDeque<>();
queue.add(new int[] {start, 0});
Set<Integer> seen = new HashSet<>();
seen.add(start);
while (!queue.isEmpty()) {
int[] item = queue.remove();
int x = item[0];
int moves = item[1];
if (x == target) {
return moves;
}
for (int next : new int[] {x + 1, x * 2}) {
if (next <= target && seen.add(next)) {
queue.add(new int[] {next, moves + 1});
}
}
}
return -1;
}
public static void main(String[] args) {
System.out.println(minMoves(2, 9)); // 2 -> 4 -> 8 -> 9
}
}3Used in: Generate Binary Numbers, Breadth-First Search, Shortest Path.
2. Processing level by level
Record the queue's length at the start of each round and process exactly that many items. Everything added during the round belongs to the next level.
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
// children.get(i) lists the children of node i in a small tree
List<List<Integer>> children = List.of(
List.of(1, 2), List.of(3, 4), List.of(5), List.of(), List.of(), List.of());
Queue<Integer> queue = new ArrayDeque<>();
queue.add(0);
int level = 0;
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> nodes = new ArrayList<>();
for (int i = 0; i < size; i++) {
int v = queue.remove();
nodes.add(v);
queue.addAll(children.get(v));
}
System.out.println("level " + level + ": " + nodes);
level++;
}
}
}level 0: [0]
level 1: [1, 2]
level 2: [3, 4, 5]3. Sliding window with a deque
Push new elements at the back, and drop elements that have left the window from the front. With a deque that keeps its values in decreasing order, you can read the maximum of each window from the front in O(1) (LeetCode 239):
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
public class Main {
static int[] windowMax(int[] nums, int k) {
Deque<Integer> deque = new ArrayDeque<>(); // indices, values decreasing
int[] result = new int[Math.max(0, nums.length - k + 1)];
for (int i = 0; i < nums.length; i++) {
if (!deque.isEmpty() && deque.peekFirst() + k <= i) {
deque.pollFirst(); // left the window
}
while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
deque.pollLast(); // can never be a maximum again
}
deque.addLast(i);
if (i + 1 >= k) {
result[i + 1 - k] = nums[deque.peekFirst()];
}
}
return result;
}
public static void main(String[] args) {
System.out.println(Arrays.toString(windowMax(new int[] {1, 3, -1, -3, 5, 3, 6, 7}, 3)));
}
}[3, 3, 5, 5, 6, 7]Sliding Window Maximum covers this problem in full.
4. Simulation
Anything that is served in order of arrival, such as print jobs, requests, or players taking turns, is a queue. Rotating the queue (pollFirst, then addLast) models going around in a circle.
Reaching into the middle
ArrayDeque offers only end operations, so reversing or sorting part of it needs another structure. One option is to remove the elements from the front into an array and add them back with addFirst, as Reverse the First k Elements does. Another is new ArrayList<>(deque), which copies the elements front to back into a list that supports Collections.reverse and Collections.sort.