Java Deque: Methods, Implementations, and Examples

After Java was extended with the Queue interface in version 5, the java.util.Deque interface and the first deque implementations, ArrayDeque and LinkedBlockingDeque, were added in Java 6. LinkedList, which has been around since Java 1.2, has also implemented Deque since Java 6; ConcurrentLinkedDeque followed in Java 7.

The implementations differ in various characteristics (like bounded/unbounded, blocking/non-blocking, thread-safe/non-thread-safe). In this article, I’ll compare them and show you which one to use when.

Java Deque Class Hierarchy

Here you can see an overview of the Deque interfaces and classes in the form of a UML class diagram. The deque interfaces and classes are highlighted in color; to their left, outlined in gray, are the queue interfaces and classes:

I cover Queue and BlockingQueue in the articles Java Queue and BlockingQueue.

Since Java 21, Deque also extends the SequencedCollection interface, which adds the reversed() method. You can find out what this means for a deque in the article Queue vs. Deque.

I will introduce the BlockingDeque interface in the next part of the tutorial; after that, I’ll cover the concrete Deque classes ArrayDeque, LinkedList, ConcurrentLinkedDeque, and LinkedBlockingDeque.

You can always jump to the corresponding parts using the navigation for this series.

Java Deque Methods

The Deque interface inherits from Queue and adds twelve methods for inserting, removing, and viewing elements at both ends of the deque – the head and the tail – as well as three stack methods. On top of that, there are removeFirstOccurrence(), removeLastOccurrence(), descendingIterator(), and, since Java 21, reversed().

For consistency, the operations that Deque already inherits from Queue have counterparts with new names – for example, Queue.add() is equivalent to Deque.addLast() and Queue.remove() to Deque.removeFirst().

The three stack methods are alternatives to deque methods, e.g., Deque.push() to Deque.addFirst(). These methods should have been part of a separate Stack interface.

You can find out why you should use a Deque as a stack and not the legacy java.util.Stack class in the article Java Deque vs. Stack.

I have explicitly listed all these queue and stack methods in the following – each with the equivalent deque methods.

At the end of this chapter, you will find a summary table.

Methods for Inserting into the Deque

To get started, here is a graphical overview of all enqueue methods:

Deque.addFirst() + addLast()

These methods insert an element at the head or the tail of the deque. They have no return value. If a bounded deque is full, these methods throw an IllegalStateException.

The Queue.add() method inherited from the Queue interface is equivalent to Deque.addLast().

The Deque.push() method is the stack equivalent of Deque.addFirst().

Deque.offerFirst() + offerLast()

offerFirst() and offerLast() also insert elements into the deque, but they return true if successful. If a bounded deque is full, these methods return false instead of throwing an IllegalStateException.

The Queue.offer() method inherited from the Queue interface is equivalent to Deque.offerLast().

Methods for Removing from the Deque

Also, for the dequeue methods, first a graphical overview:

Deque.removeFirst() + removeLast()

The removeFirst() and removeLast() methods take the element from the head and tail of the deque, respectively. If the deque is empty, they throw a NoSuchElementException.

The Queue.remove() method inherited from the Queue interface is equivalent to Deque.removeFirst().

Deque.pop() is the stack equivalent of Deque.removeFirst().

Deque.pollFirst() + pollLast()

pollFirst() and pollLast() also take the element from the head and tail of the deque, respectively. Unlike removeFirst() and removeLast(), these methods do not throw an exception for an empty deque but return null.

The Queue.poll() method inherited from the Queue interface is equivalent to Deque.pollFirst().

Methods for Viewing the Head or Tail Element

And finally, a graphical overview of the peek methods:

Deque.getFirst() + getLast()

The getFirst() and getLast() methods return the element from the head and tail of the deque, respectively, without removing it. If the deque is empty, these methods throw a NoSuchElementException.

The Queue.element() method inherited from the Queue interface is equivalent to Deque.getFirst().

Deque.peekFirst() + peekLast()

Also, peekFirst() and peekLast() return the head and tail element, respectively, without removing it from the deque. However, if the deque is empty, these methods do not throw an exception but return null.

The Queue.peek() method inherited from the Queue interface is equivalent to Deque.peekFirst(). peek() is also the stack equivalent of peekFirst().

Other Deque Methods

Besides the methods for the head and the tail, the Deque interface defines these four methods:

• removeFirstOccurrence(Object o) removes the first occurrence of the given element – even from the middle of the deque – and returns true if there was one.
• removeLastOccurrence(Object o) removes the last occurrence accordingly.
• descendingIterator() returns an iterator that traverses the elements from the tail to the head.
• reversed(), available since Java 21, returns a reverse-ordered view of the deque. Changes to the view affect the deque itself. getFirst() on the view returns the last element of the deque.

Deque Methods – Summary

The following table shows, once again, all twelve deque methods, the three stack methods, and the equivalent queue methods, grouped by operation, head or tail, and type of error handling:

Operation	Head: exception	Head: return value	Tail: exception	Tail: return value
Inserting an element (enqueue)	addFirst(E e) push(E e)²	offerFirst(E e)	addLast(E e) add(E e)¹	offerLast(E e) offer(E e)¹
Removing an element (dequeue)	removeFirst() remove()¹ pop()²	pollFirst() poll()¹	removeLast()	pollLast()
Viewing an element (examine)	getFirst() element()¹	peekFirst() peek()¹ ²	getLast()	peekLast()

¹ These methods are inherited from the Queue interface; in a deque, they are equivalent to the Deque method in the same cell.

² These stack methods are additionally defined in the Deque interface. Unfortunately, the JDK does not contain a Stack interface.

How to Create a Deque?

The java.util.Deque interface cannot be instantiated directly.

So you have to select a concrete deque implementation, e.g., ArrayDeque:

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

The JDK offers four deque implementations. They differ in thread safety, blocking behavior, and capacity – the next section compares them.

Deque Implementations in Java: Which One to Use?

In the table, each class name links to the part of this series in which that deque and its specific characteristics are described.

For explanations of the terms blocking, non-blocking, fairness policy, bounded, and unbounded, see the article about the BlockingQueue interface.

Class	Thread- safe?	Blocking/ non-blocking	Fairness policy	Bounded/ unbounded	Iterator type
ArrayDeque	No	Non-blocking	—	Unbounded	Fail-fast¹
LinkedList	No	Non-blocking	—	Unbounded	Fail-fast¹
ConcurrentLinkedDeque	Yes (optimistic locking via compare-and-set)	Non-blocking	—	Unbounded	Weakly consistent²
LinkedBlockingDeque	Yes (pessimistic locking with a lock)	Blocking	Not available	Bounded³	Weakly consistent²

¹ Fail-fast: If the deque is modified after the iterator has been created, other than through the iterator’s own remove() method, the iterator generally throws a ConcurrentModificationException. This is not guaranteed, so don’t rely on it – the mechanism is only meant to detect bugs.

² Weakly consistent: All elements that exist when the iterator is created are traversed by the iterator exactly once. Changes that occur after this can, but do not need to, be reflected by the iterator. Such an iterator never throws a ConcurrentModificationException.

³ If you don’t pass a capacity to the constructor, the bound is Integer.MAX_VALUE elements.

Based on these characteristics, you can choose the right deque for your specific application. My recommendations are:

• ArrayDeque for single-threaded applications
• ConcurrentLinkedDeque as a thread-safe, non-blocking, and unbounded deque
• LinkedBlockingDeque as a thread-safe, blocking deque – bounded with a capacity, practically unbounded without one

Here is my recommendation as a decision tree:

You probably notice that LinkedList is missing here. The reason is that I generally advise against using LinkedList as a deque.

Example: How to Use a Deque?

The following Java code example inserts elements at both ends of a deque and then removes them alternately from the head and the tail.

You can also find the code in the JavaDequeDemo class in the tutorial’s GitHub repository.

public class JavaDequeDemo {
  static void main() {
    // 1.
    Deque<Integer> deque = new ArrayDeque<>();

    // 2.
    for (int i = 20; i <= 22; i++) {
      deque.offerFirst(i);
      System.out.println("deque.offerFirst(" + i + ") --> deque = " + deque);
    }

    for (int i = 23; i <= 25; i++) {
      deque.offerLast(i);
      System.out.println("deque.offerLast(" + i + ")  --> deque = " + deque);
    }

    for (int i = 26; i <= 27; i++) {
      deque.offerFirst(i);
      System.out.println("deque.offerFirst(" + i + ") --> deque = " + deque);
    }

    // 3.
    System.out.println();
    System.out.println("deque.isEmpty()   = " + deque.isEmpty());
    System.out.println("deque.peekFirst() = " + deque.peekFirst());
    System.out.println("deque.peekLast()  = " + deque.peekLast());
    System.out.println();

    // 4.
    while (!deque.isEmpty()) {
      System.out.println("deque.pollFirst() = " + deque.pollFirst()
          + " --> deque = " + deque);
      System.out.println("deque.pollLast()  = " + deque.pollLast()
          + " --> deque = " + deque);
    }

    // 5.
    System.out.println();
    System.out.println("deque.isEmpty()   = " + deque.isEmpty());
    System.out.println("deque.peekFirst() = " + deque.peekFirst());
    System.out.println("deque.peekLast()  = " + deque.peekLast());
  }
}

The program does the following (the numbers refer to the source code comments):

1. It creates an ArrayDeque. Any other deque implementation would produce the same output in this example.
2. It writes some values into the deque with offerFirst() and offerLast().
3. It prints the deque’s state using isEmpty(), peekFirst(), and peekLast().
4. It alternately removes elements from the head and the tail of the deque and prints them – until the deque is empty.
5. Finally, it prints the deque’s state once more.

The program prints the following:

deque.offerFirst(20) --> deque = [20]
deque.offerFirst(21) --> deque = [21, 20]
deque.offerFirst(22) --> deque = [22, 21, 20]
deque.offerLast(23)  --> deque = [22, 21, 20, 23]
deque.offerLast(24)  --> deque = [22, 21, 20, 23, 24]
deque.offerLast(25)  --> deque = [22, 21, 20, 23, 24, 25]
deque.offerFirst(26) --> deque = [26, 22, 21, 20, 23, 24, 25]
deque.offerFirst(27) --> deque = [27, 26, 22, 21, 20, 23, 24, 25]

deque.isEmpty()   = false
deque.peekFirst() = 27
deque.peekLast()  = 25

deque.pollFirst() = 27 --> deque = [26, 22, 21, 20, 23, 24, 25]
deque.pollLast()  = 25 --> deque = [26, 22, 21, 20, 23, 24]
deque.pollFirst() = 26 --> deque = [22, 21, 20, 23, 24]
deque.pollLast()  = 24 --> deque = [22, 21, 20, 23]
deque.pollFirst() = 22 --> deque = [21, 20, 23]
deque.pollLast()  = 23 --> deque = [21, 20]
deque.pollFirst() = 21 --> deque = [20]
deque.pollLast()  = 20 --> deque = []

deque.isEmpty()   = true
deque.peekFirst() = null
deque.peekLast()  = null

The output shows that offerFirst() puts each new element in front of the existing ones. That is why 27 comes first, even though it was the last element inserted.

Summary and Outlook

In this article, you have learned about the Deque interface and its methods, the four deque implementations of the JDK, and when to use which one. I used an example to show how the Java deque works.

In the next part of the tutorial, you will learn about the BlockingDeque interface.