Queue

Q: Binary tree level-order traversal

Binary tree level-order traversal - A Medium difficulty question commonly asked at Amazon. Study Queue patterns and Java implementation to solve this.

Q: Sliding window maximum

Sliding window maximum - A Hard difficulty question commonly asked at Google. Study Queue patterns and Java implementation to solve this.

Q: Top K frequent elements

Top K frequent elements - A Medium difficulty question commonly asked at Facebook. Study Queue patterns and Java implementation to solve this.

Q: Design a circular queue

Design a circular queue - A Medium difficulty question commonly asked at Microsoft. Study Queue patterns and Java implementation to solve this.

Q: Rotting oranges — BFS multi-source

Rotting oranges — BFS multi-source - A Medium difficulty question commonly asked at Amazon. Study Queue patterns and Java implementation to solve this.

Beginner

FIFO structure essential for BFS, level-order traversal, and sliding window maximum.

Think of it this way

Think of the queue outside a cinema. The first person to arrive is the first to get a ticket. Nobody skips the line. First In, First Out. BFS uses this exact idea — explore everyone at the current distance before moving to people who are farther away, level by level.

In code, it looks like thisJava

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

queue.offer(1);   // [1]           — joins the back of the line
queue.offer(2);   // [1, 2]
queue.offer(3);   // [1, 2, 3]

System.out.println(queue.poll());  // 1 — first in, first out
System.out.println(queue.peek());  // 2 — look at front without removing

Overview

A queue is a First-In-First-Out (FIFO) data structure. Elements are added at the rear and removed from the front. Java's ArrayDeque is the preferred implementation. A deque (double-ended queue) supports insertion and deletion at both ends. Priority queues (min/max heaps) are a crucial variant used heavily in graph algorithms like Dijkstra's and in "top K" problems.

Time & Space Complexity

Operation	Time	Space
Enqueue (offer)	`O(1)`	`O(1)`
Dequeue (poll)	`O(1)`	`O(1)`
Peek (front)	`O(1)`	`O(1)`
Search	`O(n)`	`O(1)`
PriorityQueue poll	`O(log n)`	`O(1)`

Java Implementation

Java

import java.util.*;

public class QueuePatterns {

    // BFS on a graph — O(V + E)
    public static void bfs(Map<Integer, List<Integer>> graph, int start) {
        Queue<Integer> queue = new ArrayDeque<>();
        Set<Integer> visited = new HashSet<>();
        queue.offer(start);
        visited.add(start);
        while (!queue.isEmpty()) {
            int node = queue.poll();
            System.out.print(node + " ");
            for (int neighbor : graph.getOrDefault(node, List.of())) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
    }

    // Sliding window maximum using monotonic deque — O(n)
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new ArrayDeque<>(); // stores indices
        for (int i = 0; i < n; i++) {
            // remove elements outside window
            while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) deque.pollFirst();
            // remove smaller elements from back
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) deque.pollLast();
            deque.offerLast(i);
            if (i >= k - 1) result[i - k + 1] = nums[deque.peekFirst()];
        }
        return result;
    }

    // Top K frequent elements using min-heap — O(n log k)
    public static int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int n : nums) freq.merge(n, 1, Integer::sum);
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(Comparator.comparingInt(freq::get));
        for (int num : freq.keySet()) {
            minHeap.offer(num);
            if (minHeap.size() > k) minHeap.poll();
        }
        return minHeap.stream().mapToInt(Integer::intValue).toArray();
    }
}

Key Points to Remember

BFS always uses a queue — this is how you explore level by level in a tree/graph

Queue<Integer> q = new ArrayDeque<>();
q.offer(start);
while (!q.isEmpty()) {
    int node = q.poll();          // process current level
    for (int nb : graph.get(node)) q.offer(nb); // enqueue next level
}

PriorityQueue in Java is a min-heap by default; use Collections.reverseOrder() for max-heap

PriorityQueue<Integer> minHeap = new PriorityQueue<>();               // min at top
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); // max at top

Sliding window maximum uses a monotonic deque — O(n) solution

Deque<Integer> deque = new ArrayDeque<>(); // stores indices, not values
// deque front always holds index of current window maximum

Two queues can implement a stack — push to one, rotate elements to keep LIFO order

For "top K frequent elements", use a min-heap of size K

PriorityQueue<Integer> minHeap = new PriorityQueue<>(Comparator.comparingInt(freq::get));
for (int num : freq.keySet()) {
    minHeap.offer(num);
    if (minHeap.size() > k) minHeap.poll(); // evict least frequent
}

Interview Questions

Binary tree level-order traversal

MediumAmazonSolve it

Sliding window maximum

HardGoogleSolve it

Top K frequent elements

MediumFacebookSolve it

Design a circular queue

MediumMicrosoftSolve it

Rotting oranges — BFS multi-source

MediumAmazonSolve it

Ask Aria about Queue

Your personal AI tutor — ask anything about this concept

Stack

Trees & Binary Search Trees