Deque ​

We know that a Queue is a data structure where elements can only be added at one end and removed from the other.

If we relax this condition and allow elements to be added and removed from both ends, we have a double-ended queue (Deque).

The Java Collections Framework provides the Deque interface to implement a double-ended queue with the following functionalities:

• Elements can be added to both the head and the tail.
• Elements can be retrieved from both the head and the tail.

Let’s compare the enqueue and dequeue methods of Queue and Deque:

For adding elements to the tail, Queue provides add() and offer() methods, while Deque provides addLast() and offerLast(). The operations for adding elements to the head and removing elements from the tail do not exist in Queue but are available in Deque through methods like addFirst() and removeLast().

It’s important to note that the Deque interface actually extends Queue:

public interface Deque<E> extends Queue<E> {
    ...
}

Thus, the add() and offer() methods provided by Queue can also be used in Deque. However, when using Deque, it is advisable to avoid calling offer() and instead use offerLast():

import java.util.Deque;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        Deque<String> deque = new LinkedList<>();
        deque.offerLast("A"); // A
        deque.offerLast("B"); // A <- B
        deque.offerFirst("C"); // C <- A <- B
        System.out.println(deque.pollFirst()); // C, remaining A <- B
        System.out.println(deque.pollLast()); // B, remaining A
        System.out.println(deque.pollFirst()); // A
        System.out.println(deque.pollFirst()); // null
    }
}

If we simply wrote deque.offer(), we would have to think about the fact that offer() actually refers to offerLast(). By explicitly writing offerLast(), we can see at a glance that this adds an element to the tail.

Therefore, when using Deque, it is recommended to always call offerLast() / offerFirst() or pollFirst() / pollLast() methods explicitly.

Deque is an interface, and its implementations include ArrayDeque and LinkedList.

We can see that LinkedList is quite versatile; it implements List, Queue, and Deque. However, when using it, we should always reference it through a specific interface. This is because holding an interface signifies a higher level of abstraction in the code, and the methods defined in the interface represent specific purposes.

// Not recommended:
LinkedList<String> d1 = new LinkedList<>();
d1.offerLast("z");
// Recommended:
Deque<String> d2 = new LinkedList<>();
d2.offerLast("z");

Thus, one principle of programming with abstraction is to hold interfaces whenever possible instead of concrete implementation classes.

Summary ​

• Deque implements a double-ended queue (Deque) that can:
  • Add elements to both the tail and the head: addLast() / offerLast() / addFirst() / offerFirst().
  • Retrieve and remove elements from both the head and the tail: removeFirst() / pollFirst() / removeLast() / pollLast().
  • Retrieve elements from both the head and the tail without removing them: getFirst() / peekFirst() / getLast() / peekLast().
  • Always call xxxFirst() / xxxLast() to distinguish from Queue methods.
  • Avoid adding null to the queue.