Queue and Deque Interfaces in Java

Put the strings "A", null and "B" into a LinkedList queue and drain it with the usual loop while ((s = queue.poll()) != null) — the program prints only A and silently leaves "B" in the queue. poll() returns null both for an empty queue and for a null element, which is why the choice between queue methods is more than a formality.

Queue is the java.util.Queue interface that describes a queue: elements are added at the tail and removed from the head of the queue, usually in “first in, first out” (FIFO) order. Deque (short for double-ended queue, pronounced “deck”) is the java.util.Deque interface: it extends Queue and lets you add and remove elements at both ends, so the same object works as a FIFO queue and as a LIFO stack.

Queue interface in Java

The Queue<E> interface appeared in Java 5, extends Collection and defines three queue operations: insert at the tail, remove the head, and examine the head without removing it. Each operation comes in two forms: one throws an exception when the operation fails, the other returns a special value — false or null.

Most queues are FIFO, but the interface does not require it: a PriorityQueue, for example, hands out the smallest element first, not the oldest one. The queue as an abstract data structure, without Java classes, is explained in Data Structures in Java: Queue (FIFO), and where Queue sits in the Collection Framework is shown in Collection hierarchy in Java.

The Java Queue methods one by one:

So the answer to “peek vs poll” is simple: both return the head, but poll() removes it and peek() does not. Do not confuse remove() without arguments with remove(Object o) inherited from Collection: the first takes the head of the queue, the second searches for a specific element anywhere in it. The queue size is returned by size(), and isEmpty() checks for emptiness (the shared Collection methods are covered in Collection interface methods in Java). The full contract is in the Queue Javadoc.

Example: offer(), peek(), poll() and remove()

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

public class QueueExample {
    public static void main(String[] args) {
        Queue<String> queue = new ArrayDeque<>();
        queue.offer("London");
        queue.offer("Paris");
        queue.offer("Berlin");
        queue.offer("Madrid");

        System.out.println("Head: " + queue.peek());
        System.out.println("Size: " + queue.size());

        String city;
        while ((city = queue.poll()) != null) {
            System.out.println(city);
        }

        System.out.println("poll() on an empty queue: " + queue.poll());
        queue.remove();
    }
}

Output:

Head: London
Size: 4
London
Paris
Berlin
Madrid
poll() on an empty queue: null
Exception in thread "main" java.util.NoSuchElementException

Elements leave in the same order they were added. peek() does not remove the head, so size() is still 4 after it. On an empty queue poll() quietly returns null, while remove() ends the program with an exception. The poll() != null loop is safe here: ArrayDeque does not store null, so null can only mean that the queue is empty.

Queue and null: when poll() misleads you

Most Queue implementations reject null: ArrayDeque, PriorityQueue and the queues in java.util.concurrent throw NullPointerException on offer(null). The reason is that poll() and peek() use null as the “queue is empty” signal. LinkedList is the exception: it accepts null, and then that signal becomes ambiguous.

What does this code print?

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

public class QueueNullExample {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("A");
        queue.offer(null);
        queue.offer("B");

        String s;
        while ((s = queue.poll()) != null) {
            System.out.println(s);
        }
        System.out.println("Left in the queue: " + queue.size());
    }
}

Output:

A
Left in the queue: 1

The second poll() call removed the null element and returned it — the loop decided the queue was over, and "B" was never processed. If a queue may contain null, check for emptiness explicitly:

while (!queue.isEmpty()) {
    System.out.println(queue.poll()); // Output: A, null, B - each on its own line
}

The safer habit is not to put null into queues at all. Replace LinkedList with ArrayDeque and the bug shows up immediately: the line queue.offer(null) throws NullPointerException.

Deque interface in Java

The Deque<E> interface appeared in Java 6 and extends Queue: a double-ended queue has a head (first) and a tail (last), and every operation can be performed at either end. Method names follow the pattern “operation + First/Last” and, as in Queue, come in two forms — one throws an exception, the other returns a special value.

A Deque can also be traversed from the tail with descendingIterator(). Since Java 21, Deque extends SequencedCollection and gains reversed() — a reverse-ordered view of the deque (see Collection hierarchy in Java). The getFirst(), removeFirst() methods and their pairs have been in Deque since Java 6, so they work on Java 8 as well. All Deque methods are listed in the Deque Javadoc.

Deque as a stack: push, pop, peek

To use a Deque as a LIFO stack (“last in, first out”), work only with the head: push() puts an element on top, pop() takes it off, and peek() shows the top without removing it. To use a Deque as a FIFO queue, add at the tail with offer() and take from the head with poll(). All of these are aliases for the First/Last methods.

Because both the queue and the stack take elements from the head, you can mix them on one object. What does this code print?

import java.util.ArrayDeque;
import java.util.Deque;

public class DequeExample {
    public static void main(String[] args) {
        Deque<Integer> deque = new ArrayDeque<>();
        deque.offer(1);   // to the tail
        deque.offer(2);   // to the tail
        deque.push(0);    // to the head

        System.out.println(deque);            // [0, 1, 2]
        System.out.println(deque.pop());      // 0 - from the head
        System.out.println(deque.pollLast()); // 2 - from the tail
        System.out.println(deque.peek());     // 1 - the head, not removed

        deque.clear();
        System.out.println(deque.peek());     // null
        deque.pop();                          // NoSuchElementException
    }
}

Output:

[0, 1, 2]
0
2
1
null
Exception in thread "main" java.util.NoSuchElementException

push(0) placed zero in front of the elements added with offer(), because the top of the stack and the head of the queue are the same end. On an empty deque peek() returns null, while pop() throws, just like removeFirst(). Why Java code uses a Deque instead of the old java.util.Stack class is explained in Data Structures in Java: Stack (LIFO).

Java Queue vs Deque: the difference

Queue is a queue with one entrance and one exit: insert at the tail, remove from the head. Deque extends it into a double-ended queue in which you can insert, remove and examine elements at both ends. Every Deque is a Queue, but not the other way round: PriorityQueue implements only Queue.

A practical rule: declare the variable as Queue if the code needs only a queue, and as Deque if it needs a stack or access to both ends. The narrower type prevents an accidental pollLast() where only FIFO makes sense.

Queue and Deque implementations

For an ordinary queue or stack in single-threaded code, choose ArrayDeque; use LinkedList when the same collection must also be a List, and PriorityQueue when elements must come out by priority. Fixed-size and thread-safe queues live in the java.util.concurrent package.

How fast each class performs its operations is compared in Choosing an implementation. One more quirk: ArrayDeque does not override equals(), so two deques with the same elements are not equal (see When two collections are equal).

How to create (initialize) a queue in Java

Queue and Deque are interfaces, so a queue is created with one of the implementing classes and assigned to a variable of the interface type (fragment, imports java.util.*):

Queue<String> queue = new ArrayDeque<>();                 // the usual choice
Queue<String> withNulls = new LinkedList<>();             // allows null
Deque<Integer> stack = new ArrayDeque<>();                // a stack
Queue<Integer> byPriority = new PriorityQueue<>();        // smallest element first
Queue<String> filled = new ArrayDeque<>(Arrays.asList("a", "b", "c"));
System.out.println(filled.peek() + " " + filled.size());  // Output: a 3

The difference between add() and offer() (and between addFirst() and offerFirst() in a Deque) only shows up in capacity-restricted queues. Here is a fixed-size queue in Java:

import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;

public class FixedSizeQueue {
    public static void main(String[] args) {
        Queue<String> queue = new ArrayBlockingQueue<>(2);
        System.out.println(queue.offer("A")); // true
        System.out.println(queue.offer("B")); // true
        System.out.println(queue.offer("C")); // false - no room
        queue.add("C");                       // IllegalStateException
    }
}

Output:

true
true
false
Exception in thread "main" java.lang.IllegalStateException: Queue full

ArrayDeque, LinkedList and PriorityQueue have no capacity limit, so their offer() always returns true and add() never throws IllegalStateException. Note that ArrayBlockingQueue rejects new elements when full; it does not drop the oldest one. If you need a queue that keeps only the last N elements, call poll() before offer() when size() reaches N.