Java Collections

Queue / Deque

Complete lesson for Queue / Deque using LEARNCODEGURU’s 6-level learning model — from basics to advanced practice, with Java OOP and Collections where relevant.

Basics — Queue / Deque

Section: Java Collections. FIFO queues and double-ended deques: Queue, Deque, PriorityQueue, and ArrayDeque.

Queue is FIFO

A queue adds at the tail and removes from the head. Think ticket line, BFS, task buffers.
Queue methods come in two styles: exception vs special value.

Action	Throws on failure	Returns false / null
Insert	`add(e)`	`offer(e)`
Remove head	`remove()`	`poll()`
Look at head	`element()`	`peek()`

Deque: both ends

Deque (double-ended queue) is the modern stack *and* queue interface.
ArrayDeque is a circular array: no nulls, not thread-safe, fastest general-purpose deque.
LinkedList also implements Deque but allocates a node per element.

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

public class QueueBasics {
    public static void main(String[] args) {
        Queue<String> q = new ArrayDeque<>();
        q.offer("first");
        q.offer("second");
        System.out.println(q.peek()); // first
        System.out.println(q.poll()); // first
        System.out.println(q.poll()); // second
        System.out.println(q.poll()); // null (empty)
    }
}

PriorityQueue

PriorityQueue is a binary heap, not a sorted list. peek is the least element (natural order) in O(1); offer/poll are O(log n).
Iteration order is **not** sorted. To print sorted, poll everything or copy into a TreeSet / sort a list.
Default is min-heap. Max-heap: new PriorityQueue<>(Comparator.reverseOrder()).

Advanced — Queue / Deque

Complexity, nulls, and concurrency

PriorityQueue does not allow null. Comparator must be consistent with equals if you also use the queue as a set-like structure (it is not a set).
Changing a field that affects ordering while the object sits in a PriorityQueue corrupts the heap — remove/re-offer or use an immutable key.
Concurrent queues: ConcurrentLinkedQueue (lock-free), ArrayBlockingQueue / LinkedBlockingQueue (producers-consumers).
BFS: Queue q = new ArrayDeque<>(); q.offer(root); — never use Stack for BFS.

Tricky Interview Points

Q1) offer vs add on a Queue?

Answer add throws if the queue cannot accept the element (capacity). offer returns false. ArrayDeque is unbounded (grows), so both succeed until memory fails.

Q2) poll vs remove?

Answer poll returns null when empty. remove() throws NoSuchElementException.

Q3) Is PriorityQueue a sorted queue you can iterate in order?

Answer No. Only peek/poll give the next extreme. Iterator order is unspecified.

Q4) ArrayDeque vs LinkedList as a queue?

Answer ArrayDeque is faster and more compact. LinkedList allows null and is also a List. Prefer ArrayDeque.

Q5) How do you implement a max-heap?

Answer new PriorityQueue<>(Comparator.reverseOrder()) or a custom Comparator.

Q6) Queue vs Deque?

Answer Queue is one-end-in, other-end-out (FIFO). Deque allows both ends and can model a stack.

Simple Programs

BFS-style level print and a min-heap

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

public class QueuePrograms {
    public static void main(String[] args) {
        Queue<Integer> bfs = new ArrayDeque<>();
        bfs.offer(1);
        bfs.offer(2);
        bfs.offer(3);
        while (!bfs.isEmpty()) {
            System.out.print(bfs.poll() + " ");
        }
        System.out.println();
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        heap.offer(5);
        heap.offer(1);
        heap.offer(4);
        System.out.println(heap.poll()); // 1
    }
}

Problem Solving Tricks

Prefer offer/poll/peek in application code — they do not throw on a full/empty unbounded deque (poll returns null).
For k-largest, keep a min-heap of size k — O(n log k).
Never sort a PriorityQueue in place; it is not a List.
BlockingQueue.put/take are the producer-consumer pair in java.util.concurrent.

Practice Programs List

Implement BFS on a 2D grid of 0/1 cells using ArrayDeque.
Find the k smallest numbers with a max-heap of size k.
Show that iterating a PriorityQueue is not sorted, then poll to sort.
Build a palindrome checker with a Deque (offerLast all chars, then compare ends).
Write a method that drains a queue into a list without using toArray (loop poll).