Queue Interface

#Introduction

Queue is one of the core Collection interfaces and is heavily used in multithreading, messaging, task processing, BFS, scheduling and producer-consumer systems.

The most important thing to understand is:

Queue normally follows FIFO — First In, First Out — but not every Queue implementation guarantees FIFO ordering.

That exception becomes important when we study PriorityQueue.

#What is Queue?

Queue represents a collection designed primarily for holding elements before they are processed.

Package:

java.util.Queue

Some concurrent implementations (covered later) include BlockingQueue, ArrayBlockingQueue, LinkedBlockingQueue and PriorityBlockingQueue.

#FIFO Principle

The typical Queue behaviour is First In, First Out.

Remove → 10 comes out. Then the queue is 20 → 30 → 40. This is similar to a real-world queue at a counter.

Queue Does NOT Always Mean FIFO

This is an important interview nuance. A normal FIFO Queue processes elements in insertion order, but implementations can use different ordering policies. For example, PriorityQueue orders elements according to their priority/natural ordering rather than insertion order.

#Core Queue Methods

Queue has three important method pairs. This is extremely important for interviews.

Easy memory trick: add ↔ offer, remove ↔ poll, element ↔ peek. The right-hand methods are generally safer when you want to handle failure without exceptions.

add() vs offer()

Both attempt to insert an element:

queue.add(10);
queue.offer(10);

The difference appears when insertion cannot be performed:

For an unbounded Queue such as LinkedList or ArrayDeque, capacity failure normally isn't an issue. The distinction becomes especially useful with bounded queues.

remove() vs poll()

Both remove the head. If the Queue is empty:

element() vs peek()

Both inspect the head without removing it. If empty:

Basic Example

Queue<String> queue = new LinkedList<>();

queue.offer("A");
queue.offer("B");
queue.offer("C");

System.out.println(queue.poll());
System.out.println(queue.peek());

A
B

After poll() the queue is B → C.

Queue Does Not Provide Index-Based Access

Unlike List, Queue doesn't provide get(index). Why? Because Queue focuses on inserting, removing the head and inspecting the head — rather than positional access.

#Queue Implementations

The important implementations for interviews are LinkedList, PriorityQueue and ArrayDeque (and later, BlockingQueue implementations).

LinkedList as Queue

Since LinkedList implements Queue:

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

You can use offer(), poll() and peek(). Internally, LinkedList can efficiently add/remove at its ends.

ArrayDeque as Queue

ArrayDeque is usually a better general-purpose Queue than LinkedList.

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

Advantages:

• Array-based
• Efficient
• No node allocation per element
• Good cache locality
• No synchronization overhead

For ordinary single-threaded FIFO queues, ArrayDeque is often the preferred choice.

ArrayDeque vs LinkedList

PriorityQueue

PriorityQueue is where many candidates make a mistake. It is a Queue, but it is not FIFO.

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

queue.offer(30);
queue.offer(10);
queue.offer(20);

The head is 10, because the smallest element has the highest priority under natural ordering.

PriorityQueue uses a binary heap — by default a min-heap:

We'll cover PriorityQueue in detail in its own chapter.

Queue Ordering Comparison

Queue with Custom Objects

class Task {
    int priority;
    String name;
}

A priority-based Queue can use:

Queue<Task> tasks = new PriorityQueue<>(Comparator.comparingInt(t -> t.priority));

Now tasks are processed according to the comparator. This is a common real-world pattern.

#Queue Use Cases

Queue is ideal when work must be processed progressively.

Producer-Consumer Pattern

A classic interview scenario: Producer → Queue → Consumer.

// Producer
queue.offer(task);

// Consumer
Task task = queue.poll();

#BlockingQueue

BlockingQueue is part of java.util.concurrent. It extends Queue and adds blocking behaviour.

BlockingQueue<Task> queue = new ArrayBlockingQueue<>(100);

// Producer
queue.put(task);

// Consumer
Task task = queue.take();

This makes BlockingQueue particularly useful for producer-consumer architectures.

Method Families in Concurrent Queues

With bounded queues, the method choice becomes especially meaningful:

This distinction is very useful in concurrency interviews.

#Queue vs Stack vs Deque vs List

Queue vs Stack

Interview favourite.

Modern Java generally uses Deque for stack behaviour rather than the legacy Stack class.

Queue vs Deque

Queue normally focuses on inserting at the tail and removing from the head. Deque supports both ends (front and rear), so it can behave as a Queue + Stack.

Deque<Integer> deque = new ArrayDeque<>();

// Queue
deque.offerLast(10);
deque.pollFirst();

// Stack
deque.push(10);
deque.pop();

Queue vs List

#Null Elements and Programming to the Interface

Null Elements

This depends on the implementation:

Queue<String> q = new LinkedList<>();
q.offer(null);   // allowed

Important reason: for methods such as poll() and peek(), null is used to indicate that the queue is empty.

Queue is an Interface

Prefer programming to the interface:

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

rather than:

ArrayDeque<Task> queue = new ArrayDeque<>();

unless you specifically need ArrayDeque-only operations. This makes the implementation easier to replace.

#Time Complexity

PriorityQueue has O(log n) insertion/removal because the heap may need reordering.

#Decision Framework

Final Mental Model

For modern Java: