Chapter 14

Queues in Java
Java Data Structures & Algorithms Series

A Queue is a First-In-First-Out (FIFO) data structure — the first element enqueued is the first one
dequeued. It is the backbone of BFS, scheduling, sliding window maximum, and task processing
systems.

1 Queue in Java — Three Ways

// Way 1: LinkedList as Queue

Queue<Integer> queue = new LinkedList<>();
[Link](1); // enqueue — O(1)
[Link](); // dequeue — O(1), returns null if empty
[Link](); // front element — O(1), returns null if empty
[Link]();
[Link]();

// Way 2: ArrayDeque as Queue (PREFERRED — faster than LinkedList)

Queue<Integer> queue = new ArrayDeque<>();
// Same API: offer/poll/peek

// Way 3: PriorityQueue (Min-Heap by default)

Queue<Integer> minHeap = new PriorityQueue<>();
Queue<Integer> maxHeap = new PriorityQueue<>([Link]());
[Link](3); [Link](1); [Link](2);
[Link](); // returns 1 (minimum)

// Deque — Double-Ended Queue (can act as both Stack AND Queue)

Deque<Integer> deque = new ArrayDeque<>();
[Link](1); // add to front
[Link](2); // add to back
[Link](); // remove from front
[Link](); // remove from back
[Link](); // view front
[Link](); // view back

2 Pattern 1 — BFS (Breadth-First Search) on Graph

⭐ BFS is the canonical queue algorithm: explore level by level. Every node at distance d is
visited before any node at distance d+1.

public static int[] bfsGraph(int V, List<List<Integer>> adj, int start) {

int[] dist = new int[V];
[Link](dist, -1);
Queue<Integer> queue = new ArrayDeque<>();

dist[start] = 0;
[Link](start);

while (![Link]()) {
int node = [Link]();

for (int neighbor : [Link](node)) {

if (dist[neighbor] == -1) { // not visited
dist[neighbor] = dist[node] + 1;
[Link](neighbor);
}
}
}
return dist;
}
// Time: O(V+E) | Space: O(V)

BFS Level Order — Track Levels Explicitly

💡 Key Trick: Snapshot [Link]() before the inner loop to process exactly one level at a
time — this is the most important BFS implementation detail.

public static List<List<Integer>> bfsLevels(int V, List<List<Integer>> adj,

int start) {
List<List<Integer>> levels = new ArrayList<>();
boolean[] visited = new boolean[V];
Queue<Integer> queue = new ArrayDeque<>();

visited[start] = true;
[Link](start);

while (![Link]()) {
int size = [Link](); // nodes at current level
List<Integer> level = new ArrayList<>();

for (int i = 0; i < size; i++) { // process exactly this level

int node = [Link]();
 [Link](node);
for (int neighbor : [Link](node))
if (!visited[neighbor]) {
visited[neighbor] = true;
[Link](neighbor);
}
}
[Link](level);
}
return levels;
}

3 Pattern 2 — BFS on Binary Tree

🔑 Level Order Traversal

public static List<List<Integer>> levelOrder(TreeNode root) {

List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;

Queue<TreeNode> queue = new ArrayDeque<>();

[Link](root);

while (![Link]()) {
int size = [Link]();
List<Integer> level = new ArrayList<>();

for (int i = 0; i < size; i++) {

TreeNode node = [Link]();
[Link]([Link]);
if ([Link] != null) [Link]([Link]);
if ([Link] != null) [Link]([Link]);
}
[Link](level);
}
return result;
}
// Time: O(n) | Space: O(n)

🔑 Zigzag Level Order

public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {

List<List<Integer>> result = new ArrayList<>();
 if (root == null) return result;
Queue<TreeNode> queue = new ArrayDeque<>();
[Link](root);
boolean leftToRight = true;

while (![Link]()) {
int size = [Link]();
LinkedList<Integer> level = new LinkedList<>(); // use LinkedList for
addFirst

for (int i = 0; i < size; i++) {

TreeNode node = [Link]();
if (leftToRight) [Link]([Link]);
else [Link]([Link]); // reverse order
if ([Link] != null) [Link]([Link]);
if ([Link] != null) [Link]([Link]);
}
[Link](level);
leftToRight = !leftToRight; // flip direction each level
}
return result;
}

🔑 Right Side View of Binary Tree

public static List<Integer> rightSideView(TreeNode root) {

List<Integer> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new ArrayDeque<>();
[Link](root);

while (![Link]()) {
int size = [Link]();
for (int i = 0; i < size; i++) {
TreeNode node = [Link]();
if (i == size - 1) [Link]([Link]); // last node in level
if ([Link] != null) [Link]([Link]);
if ([Link] != null) [Link]([Link]);
}
}
return result;
}

4 Pattern 3 — Sliding Window Maximum (Monotonic Deque)

Find maximum in every window of size K as it slides.

nums = [1,3,-1,-3,5,3,6,7], k = 3
Windows: [1,3,-1]→3, [3,-1,-3]→3, [-1,-3,5]→5, [-3,5,3]→5, [5,3,6]→6,
[3,6,7]→7
Answer: [3, 3, 5, 5, 6, 7]

💡 Key Insight: Elements smaller than the incoming element can NEVER be the maximum of
any future window, so discard them immediately. The deque stores indices of a decreasing
sequence of values.

public static int[] maxSlidingWindow(int[] nums, int k) {

int n = [Link];
int[] result = new int[n - k + 1];
Deque<Integer> deque = new ArrayDeque<>(); // stores INDICES, decreasing
values

for (int i = 0; i < n; i++) {

// Remove indices outside current window
while (![Link]() && [Link]() < i - k + 1)
[Link]();

// Remove indices whose values are less than current

while (![Link]() && nums[[Link]()] < nums[i])
[Link]();

[Link](i);

// Record result once first window is complete

if (i >= k - 1)
result[i - k + 1] = nums[[Link]()];
}
return result;
}
// Time: O(n) | Space: O(k)

// Trace: [1,3,-1,-3,5,3,6,7], k=3

// i=0: deque=[0(val=1)]
// i=1: 3>1 → remove 0 → deque=[1(val=3)]
// i=2: -1<3 → deque=[1,2] → window complete → result[0]=nums[1]=3
// i=3: -3<-1 → deque=[1,2,3] → front=1 still in window → result[1]=nums[1]=3
// i=4: 5>all → remove all → deque=[4] → result[2]=nums[4]=5 ✅
5 Pattern 4 — Shortest Path in Grid (BFS)

🔑 01 Matrix — Distance to Nearest 0 (Multi-Source BFS)

💡 Multi-Source BFS: Start BFS from ALL source cells (0s) simultaneously. This is more
efficient than running BFS from each cell individually.

public static int[][] updateMatrix(int[][] mat) {

int m = [Link], n = mat[0].length;
int[][] dist = new int[m][n];
Queue<int[]> queue = new ArrayDeque<>();

// Initialize: 0 cells have distance 0, 1 cells = MAX

for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (mat[i][j] == 0) { dist[i][j] = 0; [Link](new int[]{i,
j}); }
else dist[i][j] = Integer.MAX_VALUE;

int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};

while (![Link]()) {
int[] cell = [Link]();
for (int[] d : dirs) {
int nr = cell[0] + d[0], nc = cell[1] + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n
&& dist[nr][nc] > dist[cell[0]][cell[1]] + 1) {
dist[nr][nc] = dist[cell[0]][cell[1]] + 1;
[Link](new int[]{nr, nc});
}
}
}
return dist;
}
// Time: O(m×n) | Space: O(m×n)

🔑 Shortest Path in Binary Matrix (8 directions)

public static int shortestPathBinaryMatrix(int[][] grid) {

int n = [Link];
if (grid[0][0] == 1 || grid[n-1][n-1] == 1) return -1;

Queue<int[]> queue = new ArrayDeque<>();

 [Link](new int[]{0, 0, 1}); // {row, col, path_length}
grid[0][0] = 1; // mark visited

int[][] dirs = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};

while (![Link]()) {
int[] curr = [Link]();
int r = curr[0], c = curr[1], len = curr[2];

if (r == n-1 && c == n-1) return len;

for (int[] d : dirs) {

int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 0) {
grid[nr][nc] = 1; // mark visited
[Link](new int[]{nr, nc, len + 1});
}
}
}
return -1;
}
// Time: O(n²) | Space: O(n²)

6 Pattern 5 — Rotten Oranges (Multi-Source BFS)

public static int orangesRotting(int[][] grid) {

int m = [Link], n = grid[0].length;
Queue<int[]> queue = new ArrayDeque<>();
int fresh = 0;

// Add ALL rotten oranges to queue simultaneously

for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) [Link](new int[]{i, j});
else if (grid[i][j] == 1) fresh++;
}

if (fresh == 0) return 0;

int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};

int minutes = 0;

while (![Link]() && fresh > 0) {

minutes++;
int size = [Link]();
 for (int i = 0; i < size; i++) {
int[] cell = [Link]();
for (int[] d : dirs) {
int nr = cell[0]+d[0], nc = cell[1]+d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] ==
1) {
grid[nr][nc] = 2; // rot it
fresh--;
[Link](new int[]{nr, nc});
}
}
}
}
return fresh == 0 ? minutes : -1;
}
// Time: O(m×n) | Space: O(m×n)

7 Pattern 6 — Word Ladder (BFS on Strings)

💡 Key Idea: Treat each word as a graph node. Two words are neighbors if they differ by
exactly one character. BFS finds the shortest transformation path.

public static int ladderLength(String beginWord, String endWord,

List<String> wordList) {
Set<String> wordSet = new HashSet<>(wordList);
if () return 0;

Queue<String> queue = new ArrayDeque<>();

[Link](beginWord);
[Link](beginWord);
int steps = 1;

while (![Link]()) {
int size = [Link]();
steps++;

for (int i = 0; i < size; i++) {

char[] word = [Link]().toCharArray();

for (int j = 0; j < [Link]; j++) {

char original = word[j];
for (char c = 'a'; c <= 'z'; c++) {
word[j] = c;
 String next = new String(word);
if ([Link](endWord)) return steps;
if ([Link](next)) {
[Link](next); // mark visited
[Link](next);
}
}
word[j] = original; // restore
}
}
}
return 0;
}
// Time: O(M²×N) M=word length, N=wordList size | Space: O(M²×N)
// hit → hot → dot → dog → cog = 5 steps

8 Pattern 7 — Task Scheduler with Cooldown (Priority Queue)

public static int leastInterval(char[] tasks, int n) {

int[] freq = new int[26];
for (char t : tasks) freq[t - 'A']++;

// Max-heap by frequency
PriorityQueue<Integer> maxHeap =
new PriorityQueue<>([Link]());
for (int f : freq) if (f > 0) [Link](f);

Queue<int[]> cooldown = new ArrayDeque<>(); // [remaining_count,

available_time]
int time = 0;

while (![Link]() || ![Link]()) {

time++;
if (![Link]()) {
int cnt = [Link]() - 1;
if (cnt > 0) [Link](new int[]{cnt, time + n});
}
// Release from cooldown if time has come
if (![Link]() && [Link]()[1] == time)
[Link]([Link]()[0]);
}
return time;
}
// Time: O(n log 26) = O(n) | Space: O(1)
9 Design — Circular Queue

💡 Circular Array Trick: Use (index + 1) % capacity to wrap around. This avoids shifting
elements and keeps all operations O(1).

class MyCircularQueue {
int[] data;
int head, tail, size, capacity;

MyCircularQueue(int k) {
data = new int[k];
capacity = k;
head = tail = size = 0;
}

public boolean enQueue(int value) {

if (isFull()) return false;
data[tail] = value;
tail = (tail + 1) % capacity; // wrap around
size++;
return true;
}

public boolean deQueue() {

if (isEmpty()) return false;
head = (head + 1) % capacity; // wrap around
size--;
return true;
}

public int Front() { return isEmpty() ? -1 : data[head]; }

public int Rear() { return isEmpty() ? -1 : data[(tail-1+capacity)
%capacity]; }
public boolean isEmpty() { return size == 0; }
public boolean isFull() { return size == capacity; }
}
// All operations: O(1) | Space: O(k)

10 Priority Queue Deep Dive

// Custom comparator — sort by second element of array

PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
// K closest points to origin (min-heap on distance)
public static int[][] kClosest(int[][] points, int k) {
PriorityQueue<int[]> heap = new PriorityQueue<>(
(a, b) -> (a[0]*a[0] + a[1]*a[1]) - (b[0]*b[0] + b[1]*b[1])
);
for (int[] p : points) [Link](p);
int[][] result = new int[k][];
for (int i = 0; i < k; i++) result[i] = [Link]();
return result;
}

// Kth largest element (min-heap of size k)

public static int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : nums) {
[Link](num);
if ([Link]() > k) [Link](); // keep only k largest
}
return [Link](); // kth largest = smallest in heap of size k
}
// Time: O(n log k) | Space: O(k)

11 Queue vs Deque vs PriorityQueue

Queue Deque PriorityQueue

Order FIFO Both ends By priority

Access Front only Front & Back Min/Max

Push/Pop O(1) O(1) O(log n)

Peek O(1) O(1) O(1)

Use for BFS, scheduling Sliding window max Dijkstra, Top-K

12 Full Runnable Java Program

import [Link].*;

public class Chapter14Queues {

static class TreeNode {

int val; TreeNode left, right;
TreeNode(int v) { val = v; }
}
 public static void main(String[] args) {
// Sliding Window Maximum
[Link]("Sliding max k=3: " + [Link](
maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7}, 3))); //
[3,3,5,5,6,7]

// Rotten Oranges
[Link]("Rotten oranges: " +
orangesRotting(new int[][]{{2,1,1},{1,1,0},{0,1,1}})); // 4

// 01 Matrix
int[][] dist = updateMatrix(new int[][]{{0,0,0},{0,1,0},{0,0,0}});
[Link]("01 Matrix dist[1][1]: " + dist[1][1]); // 1

// Word Ladder
[Link]("Word Ladder: " +
ladderLength("hit", "cog",
[Link]("hot","dot","dog","lot","log","cog"))); // 5

// Kth Largest
[Link]("3rd largest: " +
findKthLargest(new int[]{3,2,1,5,6,4}, 3)); // 4

// K Closest Points
[Link]("K closest: " + [Link](
kClosest(new int[][]{{1,3},{-2,2},{5,8},{0,1}}, 2)));

// Circular Queue
MyCircularQueue cq = new MyCircularQueue(3);
[Link]("Enqueue 1: " + [Link](1)); // true
[Link]("Enqueue 2: " + [Link](2)); // true
[Link]("Enqueue 3: " + [Link](3)); // true
[Link]("Enqueue 4: " + [Link](4)); // false — full
[Link]("Rear: " + [Link]()); // 3
[Link]("Dequeue: " + [Link]()); // true
[Link]("Enqueue 4: " + [Link](4)); // true
[Link]("Rear: " + [Link]()); // 4
}

static int[] maxSlidingWindow(int[] nums, int k) {

int n = [Link]; int[] res = new int[n-k+1];
Deque<Integer> dq = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (![Link]() && [Link]() < i-k+1) [Link]();
while (![Link]() && nums[[Link]()] < nums[i])
[Link]();
[Link](i);
 if (i >= k-1) res[i-k+1] = nums[[Link]()];
}
return res;
}

static int orangesRotting(int[][] grid) {

int m=[Link], n=grid[0].length, fresh=0;
Queue<int[]> q = new ArrayDeque<>();
for (int i=0;i<m;i++) for (int j=0;j<n;j++) {
if (grid[i][j]==2) [Link](new int[]{i,j});
else if (grid[i][j]==1) fresh++;
}
if (fresh==0) return 0;
int[][]dirs={{0,1},{0,-1},{1,0},{-1,0}}; int mins=0;
while (![Link]() && fresh>0) {
mins++; int sz=[Link]();
for (int i=0;i<sz;i++) {
int[]c=[Link]();
for (int[]d:dirs) {
int nr=c[0]+d[0], nc=c[1]+d[1];
if (nr>=0&&nr<m&&nc>=0&&nc<n&&grid[nr][nc]==1) {
grid[nr][nc]=2; fresh--; [Link](new int[]{nr,nc});
}
}
}
}
return fresh==0 ? mins : -1;
}

static int[][] updateMatrix(int[][] mat) {

int m=[Link], n=mat[0].length;
int[][]dist=new int[m][n]; Queue<int[]>q=new ArrayDeque<>();
for (int i=0;i<m;i++) for (int j=0;j<n;j++) {
if (mat[i][j]==0){dist[i][j]=0;[Link](new int[]{i,j});}
else dist[i][j]=Integer.MAX_VALUE;
}
int[][]dirs={{0,1},{0,-1},{1,0},{-1,0}};
while (![Link]()) {
int[]c=[Link]();
for (int[]d:dirs) {
int nr=c[0]+d[0], nc=c[1]+d[1];
if (nr>=0&&nr<m&&nc>=0&&nc<n&&dist[nr][nc]>dist[c[0]][c[1]]+1)
{
dist[nr][nc]=dist[c[0]][c[1]]+1; [Link](new int[]
{nr,nc});
}
}
}
 return dist;
}

static int ladderLength(String begin, String end, List<String> wordList) {

Set<String> ws=new HashSet<>(wordList); if() return
0;
Queue<String> q=new ArrayDeque<>(); [Link](begin); [Link](begin);
int steps=1;
while (![Link]()) {
int sz=[Link](); steps++;
for (int i=0;i<sz;i++) {
char[]w=[Link]().toCharArray();
for (int j=0;j<[Link];j++) {
char o=w[j];
for (char c='a';c<='z';c++) {
w[j]=c; String nx=new String(w);
if ([Link](end)) return steps;
if ([Link](nx)){[Link](nx);[Link](nx);}
}
w[j]=o;
}
}
}
return 0;
}

static int findKthLargest(int[] nums, int k) {

PriorityQueue<Integer> pq=new PriorityQueue<>();
for (int n:nums){[Link](n);if([Link]()>k)[Link]();}
return [Link]();
}

static int[][] kClosest(int[][] pts, int k) {

PriorityQueue<int[]>pq=new PriorityQueue<>(
(a,b)->(a[0]*a[0]+a[1]*a[1])-(b[0]*b[0]+b[1]*b[1]));
for (int[]p:pts) [Link](p);
int[][]res=new int[k][];
for (int i=0;i<k;i++) res[i]=[Link]();
return res;
}
}

class MyCircularQueue {
int[]data; int head,tail,size,cap;
MyCircularQueue(int k){data=new int[k];cap=k;}
public boolean enQueue(int v){if(isFull())return
false;data[tail]=v;tail=(tail+1)%cap;size++;return true;}
public boolean deQueue(){if(isEmpty())return
 false;head=(head+1)%cap;size--;return true;}
public int Front(){return isEmpty()?-1:data[head];}
public int Rear(){return isEmpty()?-1:data[(tail-1+cap)%cap];}
public boolean isEmpty(){return size==0;}
public boolean isFull(){return size==cap;}
}

13 Practice Problems for Chapter 14

Solve in this order:

Easy Number of islands (LeetCode #200)

Easy Implement queue using stacks (LeetCode #232)
Medium Binary tree level order traversal (LeetCode #102)
Medium Binary tree zigzag level order (LeetCode #103)
Medium Binary tree right side view (LeetCode #199)
Medium Sliding window maximum (LeetCode #239)
Medium Rotten oranges (LeetCode #994)
Medium 01 Matrix (LeetCode #542)
Medium Word ladder (LeetCode #127)
Medium K closest points to origin (LeetCode #973)
Hard Design circular queue (LeetCode #622)
Hard Shortest path in binary matrix (LeetCode #1091)

💡 Key Insight: The snapshot-size trick (int size = [Link]() before the inner loop) is the
most important BFS implementation detail — it lets you process exactly one level at a time
without extra tracking. For sliding window maximum, the monotonic deque is the key: discard
elements smaller than the incoming element immediately, as they can never be the maximum of
any future window. Next up is Chapter 15 — Trees (Binary Trees)! 🚀

Prepared using Claude Sonnet 4.6 Thinking • Java Data Structures & Algorithms Series