Queue

Queue Fundamentals

A queue is a First In First Out (FIFO) data structure. Think of a line at a grocery store - first person in line is first to be served.

Core Operations

Operation	Description	Time
enqueue/add	Add element to rear	O(1)
dequeue/remove	Remove element from front	O(1)
peek/front	View front element	O(1)
isEmpty	Check if empty	O(1)

Visual Example

enqueue(1) → [1]
enqueue(2) → [1, 2]
enqueue(3) → [1, 2, 3]
peek()     → returns 1
dequeue()  → returns 1, queue becomes [2, 3]

Java Queue Implementation

// Using Queue interface
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);  // or queue.add(1)
queue.offer(2);
int front = queue.peek();  // 1
int val = queue.poll();    // 1

// Using ArrayDeque (preferred)
Deque<Integer> deque = new ArrayDeque<>();
deque.offer(1);  // or deque.addLast(1)
deque.offer(2);
int front = deque.peek();  // 1
int val = deque.poll();    // 1

Queue Variants

1. Deque (Double-Ended Queue) - add/remove from both ends
2. Priority Queue - elements served by priority
3. Circular Queue - wraps around array

When to Use Queue

1. BFS traversal - level-order traversal
2. Scheduling - CPU, disk scheduling
3. Buffering - print queue, IO buffer
4. Sliding window - max in window
5. Process management - OS process queues

Queue Applications

1. BFS Traversal (Level Order)

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        result.add(level);
    }
    return result;
}

2. Sliding Window Maximum (LeetCode 239)

public int[] maxSlidingWindow(int[] nums, int k) {
    Deque<Integer> deque = new ArrayDeque<>();
    int[] result = new int[nums.length - k + 1];
    
    for (int i = 0; i < nums.length; i++) {
        while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
            deque.pollFirst();
        }
        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;
}

3. Number of Islands (LeetCode 200)

public int numIslands(char[][] grid) {
    int count = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == '1') {
                bfs(grid, i, j);
                count++;
            }
        }
    }
    return count;
}

private void bfs(char[][] grid, int row, int col) {
    Queue<int[]> queue = new LinkedList<>();
    queue.offer(new int[]{row, col});
    grid[row][col] = '0';
    
    int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
    while (!queue.isEmpty()) {
        int[] cell = queue.poll();
        for (int[] dir : dirs) {
            int r = cell[0] + dir[0], c = cell[1] + dir[1];
            if (r >= 0 && r < grid.length && c >= 0 && c < grid[0].length && grid[r][c] == '1') {
                queue.offer(new int[]{r, c});
                grid[r][c] = '0';
            }
        }
    }
}

Queue vs Stack

Feature	Queue	Stack
Principle	FIFO	LIFO
Access	Front and Rear	Top only
Use Case	BFS	DFS
Real World	Line at store	Stack of plates