Deque Interface in Java
(+ Code Examples)

After Java was extended with the Queue interface in version 5, the java.util.Deque interface and the first Deque implementations were added in Java 6.¹

The implementations differ in various characteristics (like bounded/unbounded, blocking/non-blocking, thread-safe/non-thread-safe). I will discuss these properties in the course of this tutorial.

¹ This is not entirely true: LinkedList, one of the deque implementations, has been around since Java 1.2.

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 left part of the diagram is covered in the queue tutorial.

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 of the series using the navigation on the right side.

Java Deque Methods

The Deque interface inherits from Queue and defines 15 (!) additional methods for inserting, removing, and viewing elements on both sides of the deque (12 deque methods and three stack methods).

For consistency, those operations that Deque already inherits from Queue have been re-implemented with new names – for example, Queue.add() as Deque.addLast() and Queue.remove() as Deque.removeFirst().

The Deque interface additionally defines three stack methods as alternatives to the deque methods, e.g., Deque.push() as an alternative to Deque.addFirst(). These methods should have been part of a separate Stack interface.

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. If successful, the methods return true. If a bounded deque is full, these methods throw an IllegalStateException.

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

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

Deque.offerFirst() + offerLast()

Also, offerFirst() and offerLast() insert elements into the deque and 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 forwarded 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 forwarded 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 forwarded 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 end 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 forwarded 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 forwarded to Deque.peekFirst(). peek() is also the stack equivalent of peekFirst().

Deque Methods – Summary

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

¹ These methods are implemented in the Queue interface and call the corresponding Deque methods.

² 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. An interface only describes which methods a class implementing this interface must implement.

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

Deque<Integer> deque = new ArrayDeque<>();Code language: Java (java)

I will introduce the concrete deque classes offered by the JDK – with an explanation of their characteristics – in the following parts of the tutorial:

• Java ArrayDeque (with examples)
• Java LinkedList (with examples)
• Java ConcurrentLinkedDeque (with examples)
• Java LinkedBlockingDeque (with examples)

You can find out which implementation you should use in which case in the "Deque Implementations – Which One to Use?" article.

Example: How to Use a Deque?

The following Java code example creates exactly the deque that I graphically depicted at the beginning of the article. Afterward, the elements are removed again.

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

public class JavaDequeDemo {
  public static void main(String[] args) {
    // 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());
  }
}Code language: Java (java)

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

1. It creates a deque. Which one you use is not important for this example, as the specific deque characteristics are irrelevant.
2. It writes some values into the deque with offerFirst() and offerLast().
3. We print the deque's state using isEmpty(), peekFirst() and peekLast().
4. We remove and print elements alternately from the head and the tail of the deque – until the deque is empty.
5. Finally, we take another look at the deque's state.

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()  = nullCode language: plaintext (plaintext)

It should be pretty easy to understand how the deque works by looking at the output.

Summary and Outlook

In this article, you have learned about the Deque interface and its methods. 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.

If you still have questions, please ask them via the comment function. Do you want to be informed about new tutorials and articles? Then click here to sign up for the HappyCoders.eu newsletter.