Queue Basics

1. Introduction: Wait Your Turn

Have you ever waited in line at a grocery store, or submitted a print job to a busy office printer? The first person to enter the line is the first person to check out. The first document sent to the printer is the first one printed.

This is exactly what a Queue models. It is a linear data structure that follows the First-In, First-Out (FIFO) principle. In computer science, queues are the backbone of any system that requires fair scheduling: CPU task management, asynchronous message brokers (like Kafka or RabbitMQ), and algorithmic traversals like Breadth-First Search (BFS).

2. Core Concept: FIFO Operations

A Queue enforces strict rules about where data can be added and removed. You cannot insert or delete elements from the middle.

1. Enqueue (offer / add): Insert an element at the back (tail) of the queue.
2. Dequeue (poll / remove): Remove and return the element at the front (head) of the queue.
3. Peek (peek / element): Look at the element at the front without removing it.

Java Implementation Choice

In Java, Queue is an interface. You must instantiate it using a concrete class. The two most common are:

• LinkedList: Uses nodes and pointers. $O(1)$ additions and removals.
• ArrayDeque: Uses a resizable circular array. Often faster than LinkedList because of CPU cache locality and zero node-allocation overhead.

Best Practice: Almost always use new ArrayDeque<>() unless you specifically need null elements (which LinkedList permits, but ArrayDeque explicitly bans).

3. Beginner Code Example: Using Java's Queue

Problem Statement: (LeetCode 933) Number of Recent Calls. Implement a RecentCounter class that counts the number of recent requests within a certain time frame. ping(int t) adds a new request at time t and returns the number of requests that have happened in the past 3000 milliseconds (including t).

The Insight: As time progresses, old pings expire. A Queue is perfectly suited for this. When a new ping comes in, we add it to the back. Then, we look at the front of the queue (the oldest ping). If it is older than $t - 3000$, we dequeue it! We repeat this until the front ping is valid. The size of the queue is our answer.

import java.util.ArrayDeque;
import java.util.Queue;

public class RecentCounter {
    private Queue<Integer> queue;

    public RecentCounter() {
        queue = new ArrayDeque<>();
    }
    
    public int ping(int t) {
        // 1. Enqueue the new request
        queue.offer(t);
        
        // 2. Dequeue all requests that fall outside the [t - 3000, t] window
        while (!queue.isEmpty() && queue.peek() < t - 3000) {
            queue.poll(); 
        }
        
        // 3. The remaining size represents the valid recent requests
        return queue.size();
    }
}

Complexity Analysis:

• Time Complexity: $O(1)$ amortized per ping. Every element is enqueued once and dequeued at most once.
• Space Complexity: $O(W)$ where $W$ is the maximum number of pings that can happen in a 3000ms window.

4. Intermediate Code Example: Design a Circular Queue

In embedded systems or highly optimized frameworks, dynamic allocation (like ArrayDeque resizing) is too slow. You must use a fixed-size array.

Problem Statement: (LeetCode 622) Design your implementation of the circular queue. A circular queue uses a single fixed-size array and two pointers (head and tail). When the tail reaches the end of the array, it wraps around to index 0 using modulo math.

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

    public MyCircularQueue(int k) {
        data = new int[k];
        capacity = k;
        head = 0;
        tail = -1; // -1 because we pre-increment during insertion
        size = 0;
    }
    
    public boolean enQueue(int value) {
        if (isFull()) return false;
        
        // Wrap around using modulo arithmetic
        tail = (tail + 1) % capacity;
        data[tail] = value;
        size++;
        return true;
    }
    
    public boolean deQueue() {
        if (isEmpty()) return false;
        
        // Wrap around using modulo arithmetic
        head = (head + 1) % capacity;
        size--;
        return true;
    }
    
    public int Front() {
        if (isEmpty()) return -1;
        return data[head];
    }
    
    public int Rear() {
        if (isEmpty()) return -1;
        return data[tail];
    }
    
    public boolean isEmpty() { return size == 0; }
    public boolean isFull() { return size == capacity; }
}

5. Advanced Code Example: Implement Stack using Queues

Problem Statement: (LeetCode 225) Implement a Last-In-First-Out (LIFO) stack using only two queues (or one queue!). The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

The Insight: A Queue is FIFO. A Stack is LIFO. If we put [1, 2, 3] into a queue, they come out 1, 2, 3. We want 3 to come out first! To fix this using a SINGLE queue, every time we push a new element, we enqueue it to the back. Then, we take all the other elements in front of it, dequeue them, and immediately re-enqueue them behind the new element!

import java.util.ArrayDeque;
import java.util.Queue;

public class MyStack {
    private Queue<Integer> q;

    public MyStack() {
        q = new ArrayDeque<>();
    }
    
    // O(N) Push operation
    public void push(int x) {
        q.offer(x); // Add to the back
        int size = q.size();
        
        // Rotate the queue!
        // Move all previously existing elements behind the newly added one.
        for (int i = 0; i < size - 1; i++) {
            q.offer(q.poll());
        }
    }
    
    // O(1) Pop operation
    public int pop() {
        return q.poll(); // Since we rotated on push, the newest is right at the front!
    }
    
    public int top() {
        return q.peek();
    }
    
    public boolean empty() {
        return q.isEmpty();
    }
}

6. Common Mistakes Beginners Make

1. Using .add() instead of .offer()

   • The Mistake: Using .add() and .remove() on a bounded Queue.
   • Why it's wrong: In Java, .add() throws an IllegalStateException if a capacity-restricted queue is full. .remove() throws a NoSuchElementException if the queue is empty.
   • The Fix: Use .offer() (returns false if full) and .poll() (returns null if empty). They are safe, exception-free methods perfect for algorithms.

2. Confusing Deque with Queue

   • The Mistake: Calling deque.pollLast() when implementing a standard algorithm.
   • Why it's wrong: A Deque (Double Ended Queue) allows insertion and removal at BOTH ends. If an interviewer asks you to use a Queue, using pollLast() violates the strict FIFO requirement. Stick to offer() and poll().

3. Memory Leaks in Array implementations

   • The Mistake: In a manual array queue, doing head++ on dequeue, but forgetting to overwrite or nullify the old value at data[head-1].
   • Why it's wrong: In Java, if data holds Objects (like String or TreeNode), leaving the reference in the array prevents the Garbage Collector from freeing the memory, causing a massive memory leak in production. Always do data[oldHead] = null;.

7. Interview Q&A

Q1: What is a PriorityQueue and how does it relate to a normal Queue? Answer: While a normal Queue strictly enforces FIFO based on arrival time, a PriorityQueue completely ignores arrival time. It orders elements based on a defined priority (using a Min-Heap or Max-Heap). The highest priority element is always returned by poll().

Q2: How are Queues used in Graph Traversals? Answer: Breadth-First Search (BFS) inherently relies on a Queue. You enqueue a starting node. You dequeue it, process it, and enqueue all of its unvisited neighbors. Because of FIFO, the queue perfectly processes all nodes at Distance 1 before moving to nodes at Distance 2.

Q3: Can a Queue be implemented using a Stack? Answer: Yes! (LeetCode 232). You need TWO Stacks. You push all incoming elements onto Stack1. When a dequeue is requested, you pop everything from Stack1 and push it onto Stack2 (which reverses the order!). Then you pop the top of Stack2. This yields an amortized $O(1)$ dequeue operation.

8. Practice Problems

1. Number of Recent Calls (LeetCode 933)
   • Goal: Basic Queue usage with a time window.
2. Design Circular Queue (LeetCode 622)
   • Goal: Master modulo arithmetic array manipulation.
3. Implement Queue using Stacks (LeetCode 232)
   • Hint: Use the Two-Stack inversion pattern.

9. Summary

• FIFO: First-In, First-Out.
• Java Syntax: Always use Queue<Integer> q = new ArrayDeque<>();.
• Safe Methods: Use offer() to add, poll() to remove, peek() to look.
• Circular Queues: Use (index + 1) % capacity to wrap array pointers dynamically without allocating new memory.