Queues — The Complete Visual Reference

// ── Kotlin ArrayDeque as queue ── val queue = ArrayDeque<Int>() queue.addLast(10) // enqueue queue.addLast(20) // enqueue queue.removeFirst() // dequeue → 10 queue.first() // peek → 20 // ── java.util.ArrayDeque as queue ── val jQueue = java.util.ArrayDeque<Int>() jQueue.offer(10) // enqueue (null-safe) jQueue.offer(20) // enqueue jQueue.poll() // dequeue → 10 (null if empty) jQueue.peek() // peek → 20 (null if empty)

// ── Empty queue ── val queue = ArrayDeque<Int>() // ── From a list ── val queue = ArrayDeque(listOf(1, 2, 3)) // 1 is front // ── PriorityQueue (min-heap — default) ── val minHeap = java.util.PriorityQueue<Int>() // ── PriorityQueue (max-heap) ── val maxHeap = java.util.PriorityQueue<Int>(compareByDescending { it }) val maxHeap2 = PriorityQueue<Int>(reverseOrder()) // ── PriorityQueue (custom comparator) ── val pq = java.util.PriorityQueue<IntArray>(compareBy { it[1] })

val queue = ArrayDeque<Int>() // ── Enqueue ── queue.addLast(10) // [10] queue.addLast(20) // [10, 20] queue.addLast(30) // [10, 20, 30] // ── Peek (view front) ── queue.first() // 10 — throws if empty queue.firstOrNull() // 10 — null if empty (safe) // ── Dequeue (remove front) ── queue.removeFirst() // 10 — throws if empty queue.removeFirstOrNull() // 20 — null if empty (safe) // ── Safe patterns ── if (queue.isNotEmpty()) queue.removeFirst() queue.removeFirstOrNull() ?: defaultValue

// ── Drain (dequeue all elements) ── while (queue.isNotEmpty()) { val item = queue.removeFirst() // process item (FIFO order) } // ── Iterate without modifying ── for (item in queue) { } // front → back order // ── Level-based processing (BFS pattern) ── while (queue.isNotEmpty()) { val levelSize = queue.size // snapshot current level repeat(levelSize) { val node = queue.removeFirst() // process node, enqueue children } // entire level processed — move to next }

// ── Circular Array Queue ── class CircularArrayQueue(private val capacity: Int) { private val data = IntArray(capacity) private var front = 0 private var size = 0 fun enqueue(value: Int) { if (size == capacity) throw IllegalStateException("Full") val back = (front + size) % capacity data[back] = value size++ } fun dequeue(): Int { if (size == 0) throw NoSuchElementException() val value = data[front] front = (front + 1) % capacity size-- return value } fun peek(): Int { if (size == 0) throw NoSuchElementException() return data[front] } fun isEmpty() = size == 0 } // ── Linked Queue ── class LinkedQueue<T> { private class Node<T>(val value: T, var next: Node<T>? = null) private var head: Node<T>? = null private var tail: Node<T>? = null fun enqueue(item: T) { val node = Node(item) if (tail != null) tail!!.next = node else head = node tail = node } fun dequeue(): T { val node = head ?: throw NoSuchElementException() head = node.next if (head == null) tail = null return node.value } fun peek(): T = head?.value ?: throw NoSuchElementException() }

// ── ArrayDeque as deque — O(1) at both ends ── val deque = ArrayDeque<Int>() deque.addFirst(10) // push front [10] deque.addLast(20) // push back [10, 20] deque.addFirst(5) // push front [5, 10, 20] deque.removeFirst() // pop front → 5 [10, 20] deque.removeLast() // pop back → 20 [10] deque.first() // peek front → 10 deque.last() // peek back → 10 // ── Use as queue: addLast / removeFirst ── val queue = ArrayDeque<Int>() queue.addLast(1) // enqueue queue.removeFirst() // dequeue // ── Use as stack: addLast / removeLast ── val stack = ArrayDeque<Int>() stack.addLast(1) // push stack.removeLast() // pop

// ── Min-heap (default) ── val minHeap = java.util.PriorityQueue<Int>() minHeap.add(5); minHeap.add(1); minHeap.add(3) minHeap.peek() // 1 — smallest element minHeap.poll() // 1 — removes smallest // ── Max-heap ── val maxHeap = PriorityQueue<Int>(reverseOrder()) maxHeap.add(5); maxHeap.add(1); maxHeap.add(3) maxHeap.peek() // 5 — largest element maxHeap.poll() // 5 — removes largest // ── Custom comparator ── data class Task(val name: String, val priority: Int) val taskPQ = java.util.PriorityQueue<Task>(compareBy { it.priority })

// ── BFS graph traversal ── fun bfs(graph: Map<Int, List<Int>>, start: Int) { val visited = mutableSetOf(start) val queue = ArrayDeque<Int>() queue.addLast(start) while (queue.isNotEmpty()) { val node = queue.removeFirst() // process node for (neighbor in graph[node].orEmpty()) { if (visited.add(neighbor)) { // mark visited when ENQUEUING queue.addLast(neighbor) } } } } // ── BFS with distance tracking ── fun bfsWithDistance(graph: Map<Int, List<Int>>, start: Int): Map<Int, Int> { val dist = mutableMapOf(start to 0) val queue = ArrayDeque<Int>() queue.addLast(start) while (queue.isNotEmpty()) { val node = queue.removeFirst() for (neighbor in graph[node].orEmpty()) { if (neighbor !in dist) { dist[neighbor] = dist[node]!! + 1 queue.addLast(neighbor) } } } return dist }

// ── Level-order traversal (returns list of levels) ── fun levelOrder(root: TreeNode?): List<List<Int>> { if (root == null) return emptyList() val result = mutableListOf<List<Int>>() val queue = ArrayDeque<TreeNode>() queue.addLast(root) while (queue.isNotEmpty()) { val levelSize = queue.size // snapshot! val level = mutableListOf<Int>() repeat(levelSize) { val node = queue.removeFirst() level.add(node.`val`) node.left?.let { queue.addLast(it) } node.right?.let { queue.addLast(it) } } result.add(level) } return result } // ── Zigzag level-order ── fun zigzagLevelOrder(root: TreeNode?): List<List<Int>> { if (root == null) return emptyList() val result = mutableListOf<List<Int>>() val queue = ArrayDeque<TreeNode>() queue.addLast(root) var leftToRight = true while (queue.isNotEmpty()) { val levelSize = queue.size val level = mutableListOf<Int>() repeat(levelSize) { val node = queue.removeFirst() level.add(node.`val`) node.left?.let { queue.addLast(it) } node.right?.let { queue.addLast(it) } } if (!leftToRight) level.reverse() result.add(level) leftToRight = !leftToRight } return result } // ── Right side view ── fun rightSideView(root: TreeNode?): List<Int> { if (root == null) return emptyList() val result = mutableListOf<Int>() val queue = ArrayDeque<TreeNode>() queue.addLast(root) while (queue.isNotEmpty()) { val levelSize = queue.size repeat(levelSize) { i -> val node = queue.removeFirst() if (i == levelSize - 1) result.add(node.`val`) node.left?.let { queue.addLast(it) } node.right?.let { queue.addLast(it) } } } return result }

// ── Rotting Oranges — multi-source BFS ── fun orangesRotting(grid: Array<IntArray>): Int { val rows = grid.size; val cols = grid[0].size val queue = ArrayDeque<IntArray>() var fresh = 0 // Enqueue ALL rotten oranges initially for (r in 0 until rows) for (c in 0 until cols) when (grid[r][c]) { 2 -> queue.addLast(intArrayOf(r, c)) 1 -> fresh++ } val dirs = listOf( -1 to 0, 1 to 0, 0 to -1, 0 to 1 ) var minutes = 0 while (queue.isNotEmpty() && fresh > 0) { val size = queue.size repeat(size) { val (r, c) = queue.removeFirst() for (d in dirs) { val nr = r + d[0]; val nc = c + d[1] if (nr in 0 until rows && nc in 0 until cols && grid[nr][nc] == 1) { grid[nr][nc] = 2 fresh-- queue.addLast(intArrayOf(nr, nc)) } } } minutes++ } return if (fresh == 0) minutes else -1 }

// ── Word Ladder — BFS shortest transformation ── fun ladderLength( beginWord: String, endWord: String, wordList: List<String> ): Int { val wordSet = wordList.toMutableSet() if (endWord !in wordSet) return 0 val queue = ArrayDeque<String>() queue.addLast(beginWord) var steps = 1 while (queue.isNotEmpty()) { val size = queue.size repeat(size) { val word = queue.removeFirst() val chars = word.toCharArray() for (i in chars.indices) { val original = chars[i] for (c in 'a'..'z') { chars[i] = c val newWord = String(chars) if (newWord == endWord) return steps + 1 if (wordSet.remove(newWord)) { queue.addLast(newWord) } } chars[i] = original } } steps++ } return 0 }

// ── Sliding Window Maximum ── fun maxSlidingWindow(nums: IntArray, k: Int): IntArray { val deque = ArrayDeque<Int>() // stores indices val result = IntArray(nums.size - k + 1) for (i in nums.indices) { // Remove expired indices from front while (deque.isNotEmpty() && deque.first() <= i - k) { deque.removeFirst() } // Remove smaller values from back (maintain decreasing order) while (deque.isNotEmpty() && nums[deque.last()] <= nums[i]) { deque.removeLast() } deque.addLast(i) if (i >= k - 1) { result[i - k + 1] = nums[deque.first()] } } return result }

// ── Stack using two queues ── class StackUsingQueues { private var q1 = ArrayDeque<Int>() private var q2 = ArrayDeque<Int>() fun push(x: Int) { q2.addLast(x) while (q1.isNotEmpty()) q2.addLast(q1.removeFirst()) val tmp = q1; q1 = q2; q2 = tmp // swap } fun pop(): Int = q1.removeFirst() fun top(): Int = q1.first() fun empty(): Boolean = q1.isEmpty() } // ── Stack using single queue ── class StackUsingSingleQueue { private val queue = ArrayDeque<Int>() fun push(x: Int) { queue.addLast(x) // Rotate: move all elements before x to the back repeat(queue.size - 1) { queue.addLast(queue.removeFirst()) } } fun pop(): Int = queue.removeFirst() fun top(): Int = queue.first() fun empty(): Boolean = queue.isEmpty() }

// ── Queue using two stacks (amortized O(1)) ── class QueueUsingStacks { private val pushStack = ArrayDeque<Int>() private val popStack = ArrayDeque<Int>() fun push(x: Int) = pushStack.addLast(x) fun pop(): Int { transfer() return popStack.removeLast() } fun peek(): Int { transfer() return popStack.last() } fun empty(): Boolean = pushStack.isEmpty() && popStack.isEmpty() private fun transfer() { if (popStack.isEmpty()) { while (pushStack.isNotEmpty()) { popStack.addLast(pushStack.removeLast()) } } } }

// ── Moving Average with queue + running sum ── class MovingAverage(private val windowSize: Int) { private val queue = ArrayDeque<Int>() private var sum = 0.0 fun next(value: Int): Double { queue.addLast(value) sum += value if (queue.size > windowSize) { sum -= queue.removeFirst() } return sum / queue.size } } // Usage: val ma = MovingAverage(3) ma.next(1) // 1.0 ma.next(10) // 5.5 (1+10)/2 ma.next(3) // 4.666... (1+10+3)/3 ma.next(5) // 6.0 (10+3+5)/3 — 1 evicted

// ── 01-BFS — shortest path with 0/1 weights ── fun shortestPath01BFS( graph: Map<Int, List<Pair<Int, Int>>>, // node → [(neighbor, weight 0 or 1)] start: Int, n: Int ): IntArray { val dist = IntArray(n) { Int.MAX_VALUE } dist[start] = 0 val deque = ArrayDeque<Int>() deque.addFirst(start) while (deque.isNotEmpty()) { val u = deque.removeFirst() for ((v, w) in graph[u].orEmpty()) { val newDist = dist[u] + w if (newDist < dist[v]) { dist[v] = newDist if (w == 0) deque.addFirst(v) // 0-weight → front else deque.addLast(v) // 1-weight → back } } } return dist }

// ── Task Scheduler with max-heap + cooldown queue ── fun leastInterval(tasks: CharArray, n: Int): Int { val freq = IntArray(26) for (t in tasks) freq[t - 'A']++ val maxHeap = PriorityQueue<Int>(reverseOrder()) for (f in freq) if (f > 0) maxHeap.add(f) // (remaining count, available at time) val cooldown = ArrayDeque<Pair<Int, Int>>() var time = 0 while (maxHeap.isNotEmpty() || cooldown.isNotEmpty()) { time++ if (maxHeap.isNotEmpty()) { val count = maxHeap.poll() - 1 if (count > 0) cooldown.addLast(count to time + n) } if (cooldown.isNotEmpty() && cooldown.first().second == time) { maxHeap.add(cooldown.removeFirst().first) } } return time }

// ── Top K Frequent with min-heap of size k ── fun topKFrequent(nums: IntArray, k: Int): IntArray { val freq = mutableMapOf<Int, Int>() for (n in nums) freq[n] = freq.getOrDefault(n, 0) + 1 // Min-heap by frequency — smallest frequency at top val minHeap = java.util.PriorityQueue<Int>(compareBy { freq[it] }) for (num in freq.keys) { minHeap.add(num) if (minHeap.size > k) minHeap.poll() // remove least frequent } return minHeap.toIntArray() }

// ── Kth Largest Element (min-heap of size k) ── fun findKthLargest(nums: IntArray, k: Int): Int { val minHeap = java.util.PriorityQueue<Int>() for (num in nums) { minHeap.add(num) if (minHeap.size > k) minHeap.poll() } return minHeap.peek() // root = kth largest } // ── Merge K Sorted Lists ── fun mergeKLists(lists: Array<ListNode?>): ListNode? { val minHeap = java.util.PriorityQueue<ListNode>(compareBy { it.`val` }) for (head in lists) head?.let { minHeap.add(it) } val dummy = ListNode(0) var tail = dummy while (minHeap.isNotEmpty()) { val node = minHeap.poll() tail.next = node tail = node node.next?.let { minHeap.add(it) } } return dummy.next }

// ── MedianFinder with two heaps ── class MedianFinder { // maxHeap: smaller half (top = largest of small half) private val maxHeap = PriorityQueue<Int>(reverseOrder()) // minHeap: larger half (top = smallest of large half) private val minHeap = java.util.PriorityQueue<Int>() fun addNum(num: Int) { maxHeap.add(num) minHeap.add(maxHeap.poll()) // balance: move largest of small half if (minHeap.size > maxHeap.size) { maxHeap.add(minHeap.poll()) // keep maxHeap ≥ minHeap in size } } fun findMedian(): Double { return if (maxHeap.size > minHeap.size) maxHeap.peek().toDouble() else (maxHeap.peek() + minHeap.peek()) / 2.0 } }

// ── Dijkstra's with PriorityQueue ── fun dijkstra( graph: Map<Int, List<Pair<Int, Int>>>, // node → [(neighbor, weight)] start: Int, n: Int ): IntArray { val dist = IntArray(n) { Int.MAX_VALUE } dist[start] = 0 // Min-heap of (distance, node) val pq = java.util.PriorityQueue<Pair<Int, Int>>(compareBy { it.first }) pq.add(0 to start) while (pq.isNotEmpty()) { val (d, u) = pq.poll() if (d > dist[u]) continue // skip stale entries for ((v, w) in graph[u].orEmpty()) { val newDist = dist[u] + w if (newDist < dist[v]) { dist[v] = newDist pq.add(newDist to v) } } } return dist }

// ── Reorganize String — no adjacent duplicates ── fun reorganizeString(s: String): String { val freq = IntArray(26) for (c in s) freq[c - 'a']++ // Check impossible case val maxFreq = freq.max() if (maxFreq > (s.length + 1) / 2) return "" // Max-heap of (frequency, char) val maxHeap = PriorityQueue<Pair<Int, Char>>( compareByDescending { it.first } ) for (i in 0..25) { if (freq[i] > 0) maxHeap.add(freq[i] to ('a' + i)) } val sb = StringBuilder() var prev: Pair<Int, Char>? = null while (maxHeap.isNotEmpty()) { val (count, ch) = maxHeap.poll() sb.append(ch) prev?.let { if (it.first > 0) maxHeap.add(it) } prev = (count - 1) to ch } return sb.toString() }

// ── PITFALL 1: Wrong end of ArrayDeque ── val queue = ArrayDeque<Int>() queue.addLast(1); queue.addLast(2); queue.addLast(3) queue.removeLast() // ✗ This is STACK behavior (LIFO), not queue! queue.removeFirst() // ✓ This is QUEUE behavior (FIFO) // ── PITFALL 2: BFS — marking visited at wrong time ── // ✗ WRONG — mark when processing (causes duplicate enqueues) while (queue.isNotEmpty()) { val node = queue.removeFirst() visited.add(node) // ✗ Too late! Node may be enqueued multiple times for (neighbor in graph[node].orEmpty()) { if (neighbor !in visited) queue.addLast(neighbor) } } // ✓ CORRECT — mark when ENQUEUING if (visited.add(neighbor)) queue.addLast(neighbor) // ── PITFALL 3: Iterating PriorityQueue expecting sorted order ── val pq = java.util.PriorityQueue(listOf(3, 1, 2)) for (x in pq) println(x) // ✗ NOT guaranteed sorted! while (pq.isNotEmpty()) // ✓ poll() gives sorted order println(pq.poll()) // ── PITFALL 4: Mutating elements inside PriorityQueue ── data class Item(var priority: Int) val pq2 = java.util.PriorityQueue<Item>(compareBy { it.priority }) val item = Item(5) pq2.add(item) item.priority = 1 // ✗ Heap is now CORRUPTED! No re-heapify happens // ✓ Remove → modify → re-add pq2.remove(item) item.priority = 1 pq2.add(item) // ── PITFALL 5: Forgetting level size snapshot in BFS ── // ✗ WRONG — queue.size changes during iteration for (i in 0 until queue.size) { // size changes as children are added! val node = queue.removeFirst() queue.addLast(child) // increases queue.size mid-loop } // ✓ CORRECT — snapshot before loop val levelSize = queue.size repeat(levelSize) { /* ... */ } // ── PITFALL 6: Using java.util.Stack instead of ArrayDeque ── val bad = java.util.Stack<Int>() // ✗ Legacy, synchronized, extends Vector val good = ArrayDeque<Int>() // ✓ Modern, fast, unsynchronized