Queue Interface

The Queue interface models a collection where elements are inserted at one end and removed from the other — typically FIFO (First-In-First-Out). The Deque (double-ended queue) interface extends it to support insertion and removal at both ends.

Queue Hierarchy

Queue<E>
├── PriorityQueue<E>          — heap-based, ordered by priority
├── Deque<E> (interface)       — double-ended queue
│   ├── ArrayDeque<E>          — resizable array (recommended for most uses)
│   └── LinkedList<E>          — also implements List
└── BlockingQueue<E>           — thread-safe, producer-consumer pattern
    ├── ArrayBlockingQueue     — bounded
    ├── LinkedBlockingQueue    — optionally bounded
    ├── PriorityBlockingQueue  — unbounded, priority-ordered
    └── SynchronousQueue       — zero-capacity handoff

Two Sets of Methods

Queue provides two methods for each operation — one throws, one returns a special value:

Operation	Throws on failure	Returns null/false
Insert	add(e)	offer(e)
Remove	remove()	poll()
Examine	element()	peek()

Prefer offer/poll/peek — they fail gracefully.

Basic Queue Usage

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

queue.offer("first");
queue.offer("second");
queue.offer("third");

queue.peek();    // "first" — looks at head without removing
queue.poll();    // "first" — removes and returns head
queue.poll();    // "second"
queue.size();    // 1

// Drain the queue
while (!queue.isEmpty()) {
    System.out.println(queue.poll());
}

ArrayDeque — The Default Choice

Resizable circular array. Faster than LinkedList for both queue and stack use cases due to better cache locality.

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

// Queue (FIFO)
deque.offerLast("a");    // add to tail
deque.pollFirst();       // remove from head

// Stack (LIFO)
deque.push("a");         // add to head
deque.pop();             // remove from head

// Both ends
deque.addFirst("start");
deque.addLast("end");
deque.peekFirst();
deque.peekLast();

Default initial capacity is 16. Pre-size with new ArrayDeque<>(expectedSize) if you know the count.

PriorityQueue

A min-heap that always gives you the smallest element first (by natural ordering or a Comparator). Not FIFO.

// Natural ordering (min first)
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(2);
pq.offer(8);
pq.poll();    // 2
pq.poll();    // 5
pq.poll();    // 8

// Max-heap (largest first)
PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Comparator.reverseOrder());

// Custom ordering
PriorityQueue<String> byLength = new PriorityQueue<>(
    Comparator.comparingInt(String::length)
);

Key points:

• offer/poll are O(log n), peek is O(1)
• Iterator does NOT return elements in priority order — only poll does
• Not thread-safe — use PriorityBlockingQueue for concurrency

Implementation Comparison

	ArrayDeque	LinkedList	PriorityQueue	BlockingQueue
Ordering	FIFO	FIFO	Priority	FIFO/Priority
offer/poll	O(1)*	O(1)	O(log n)	O(1) or O(log n)
Memory	Low	High	Low	Medium
Thread-safe	No	No	No	Yes
Use case	Default queue/stack	Need List + Queue	Scheduling, top-K	Producer-consumer

*Amortized

When to Use Which

• General-purpose queue or stack → ArrayDeque
• Need both List and Queue methods → LinkedList
• Process by priority, not insertion order → PriorityQueue
• Multi-threaded producer-consumer → ArrayBlockingQueue or LinkedBlockingQueue