Topic 40 of 79

Queue

Q: How would you implement a Queue using only Stacks?

Use two stacks: `inStack` and `outStack`. For `enqueue(x)`, push `x` onto `inStack`. For `dequeue()`, if `outStack` is empty, pop every element from `inStack` and push them into `outStack` (reversing their order). Then pop from `outStack`. This achieves amortized O(1) time complexity per operation.

Q: What is the difference between `ArrayDeque` and `LinkedList` when used as a Queue?

Both implement the Queue interface. `ArrayDeque` is backed by a resizable circular array, making it extremely cache-friendly and faster in most scenarios. `LinkedList` is backed by doubly-linked nodes, meaning it creates a new Object on the heap for every single insertion, generating garbage collection overhead. Default to `ArrayDeque`.

Overview

A Queue is a linear data structure that strictly follows the FIFO (First-In, First-Out) principle. Think of it like a line of people waiting at a grocery store checkout: the first person to enter the line is the first person to be served and leave the line.

The core operations are Enqueue/Offer (add to the back of the line) and Dequeue/Poll (remove from the front of the line). Like a stack, these operations must execute in O(1) time.

Queues are essential for fairness and order. They are the backbone of Breadth-First Search (BFS) algorithms, task scheduling, asynchronous messaging (like RabbitMQ or Kafka), and handling requests in web servers where requests must be processed in the exact order they were received.

Syntax

Always use offer(), poll(), and peek(). The alternatives (add(), remove(), element()) throw exceptions if the queue is full or empty, which usually requires unnecessary try-catch blocks.

Using the Java Queue Interface

java

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        // Queue is an Interface. LinkedList and ArrayDeque implement it.
        Queue<String> queue = new LinkedList<>();
        
        // 1. Enqueue (Add to the back) - O(1)
        // offer() is preferred over add() as it returns false if full (in bounded queues)
        queue.offer("Alice");
        queue.offer("Bob");
        queue.offer("Charlie");
        
        // 2. Peek (Look at the front without removing) - O(1)
        System.out.println("Next to be served: " + queue.peek()); // "Alice"
        
        // 3. Dequeue (Remove from the front) - O(1)
        // poll() is preferred over remove() as it returns null if empty instead of throwing
        String served = queue.poll();
        System.out.println("Served: " + served); // "Alice"
        
        // 4. Process the rest of the queue
        while (!queue.isEmpty()) {
            System.out.println("Processing: " + queue.poll());
        }
        // Output: "Bob", then "Charlie"
    }
}

Common Pitfalls

Instantiating a Queue directly. Queue is an interface in Java, not a class. You cannot do new Queue<>(). You must instantiate a concrete implementation like new LinkedList<>() or new ArrayDeque<>().
Using an ArrayList to build a Queue. If you put items at the end of an ArrayList and remove them from index 0, every single removal triggers an O(N) shift of all remaining elements. This will cripple performance on large datasets. Always use LinkedList or ArrayDeque for queues.
Confusing poll() and remove(). If a queue is empty, poll() gracefully returns null, allowing you to write clean while (item = q.poll() != null) loops. remove() throws a NoSuchElementException, which crashes the thread if unhandled.

Interview Questions

How would you implement a Queue using only Stacks?

Use two stacks: inStack and outStack. For enqueue(x), push x onto inStack. For dequeue(), if outStack is empty, pop every element from inStack and push them into outStack (reversing their order). Then pop from outStack. This achieves amortized O(1) time complexity per operation.

What is the difference between ArrayDeque and LinkedList when used as a Queue?

Both implement the Queue interface. ArrayDeque is backed by a resizable circular array, making it extremely cache-friendly and faster in most scenarios. LinkedList is backed by doubly-linked nodes, meaning it creates a new Object on the heap for every single insertion, generating garbage collection overhead. Default to ArrayDeque.

What is a Double-Ended Queue (Deque)?

A Deque (pronounced 'deck') allows insertions and deletions from BOTH ends in O(1) time. It can function as a pure Stack, a pure Queue, or both simultaneously. It is the most versatile linear data structure.

Real-World Example

A printer spooler uses a Queue. Multiple computers on a network might send print jobs simultaneously. The printer can only print one at a time, so it places incoming jobs into a Queue. The jobs are processed in strict FIFO order, ensuring fairness.

example

java

Queue<PrintJob> printQueue = new LinkedList<>();

// Called by network threads receiving jobs
public void submitJob(PrintJob job) {
    printQueue.offer(job);
    System.out.println("Job queued: " + job.getDocumentName());
}

// Run by the physical printer hardware thread
public void processQueue() {
    while (!printQueue.isEmpty()) {
        PrintJob currentJob = printQueue.poll();
        hardwarePrinter.print(currentJob); // Takes time
    }
}

Check Your Knowledge

Test your understanding of Queue with these quick questions.

Which principle governs how a Queue operates?

Why should you avoid using an ArrayList to implement a Queue?

Which method safely removes and returns the front element, returning `null` if the queue is empty?

Take Java Quiz

Overview

The core operations are Enqueue/Offer (add to the back of the line) and Dequeue/Poll (remove from the front of the line). Like a stack, these operations must execute in O(1) time.

Syntax

Always use offer(), poll(), and peek(). The alternatives (add(), remove(), element()) throw exceptions if the queue is full or empty, which usually requires unnecessary try-catch blocks.

Using the Java Queue Interface

java

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        // Queue is an Interface. LinkedList and ArrayDeque implement it.
        Queue<String> queue = new LinkedList<>();
        
        // 1. Enqueue (Add to the back) - O(1)
        // offer() is preferred over add() as it returns false if full (in bounded queues)
        queue.offer("Alice");
        queue.offer("Bob");
        queue.offer("Charlie");
        
        // 2. Peek (Look at the front without removing) - O(1)
        System.out.println("Next to be served: " + queue.peek()); // "Alice"
        
        // 3. Dequeue (Remove from the front) - O(1)
        // poll() is preferred over remove() as it returns null if empty instead of throwing
        String served = queue.poll();
        System.out.println("Served: " + served); // "Alice"
        
        // 4. Process the rest of the queue
        while (!queue.isEmpty()) {
            System.out.println("Processing: " + queue.poll());
        }
        // Output: "Bob", then "Charlie"
    }
}

Common Pitfalls

Instantiating a Queue directly. Queue is an interface in Java, not a class. You cannot do new Queue<>(). You must instantiate a concrete implementation like new LinkedList<>() or new ArrayDeque<>().
Using an ArrayList to build a Queue. If you put items at the end of an ArrayList and remove them from index 0, every single removal triggers an O(N) shift of all remaining elements. This will cripple performance on large datasets. Always use LinkedList or ArrayDeque for queues.
Confusing poll() and remove(). If a queue is empty, poll() gracefully returns null, allowing you to write clean while (item = q.poll() != null) loops. remove() throws a NoSuchElementException, which crashes the thread if unhandled.

Interview Questions

How would you implement a Queue using only Stacks?

What is the difference between ArrayDeque and LinkedList when used as a Queue?

What is a Double-Ended Queue (Deque)?

Real-World Example

example

java

Queue<PrintJob> printQueue = new LinkedList<>();

// Called by network threads receiving jobs
public void submitJob(PrintJob job) {
    printQueue.offer(job);
    System.out.println("Job queued: " + job.getDocumentName());
}

// Run by the physical printer hardware thread
public void processQueue() {
    while (!printQueue.isEmpty()) {
        PrintJob currentJob = printQueue.poll();
        hardwarePrinter.print(currentJob); // Takes time
    }
}

Check Your Knowledge

Test your understanding of Queue with these quick questions.