Deque

TL;DR

• Deque (Double-Ended Queue, pronounced “deck”) extends the Queue interface.
• It allows elements to be added and removed from both ends (head and tail).
• It can be used as both a Queue (FIFO) and a Stack (LIFO).
• Common implementations: ArrayDeque and LinkedList.

Concept

Because a Deque operates on both ends, it doubles the standard Queue methods.
For example, instead of just offer() and poll(), it has:

• offerFirst(), offerLast()
• pollFirst(), pollLast()
• peekFirst(), peekLast()

The Stack Replacement

The Deque interface is the official, modern replacement for the legacy Stack class. It explicitly provides push() and pop() methods for this exact purpose. ArrayDeque is the preferred implementation for a stack because it uses a resizable array, which is faster and more cache-friendly than a LinkedList.

Examples

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

public class DequeExample {
    public static void main(String[] args) {
        Deque<String> deque = new ArrayDeque<>();
        
        // --- USING IT AS A QUEUE (FIFO) ---
        deque.offerLast("First");
        deque.offerLast("Second");
        System.out.println(deque.pollFirst()); // "First"
        
        deque.clear();
        
        // --- USING IT AS A STACK (LIFO) ---
        deque.push("Bottom");
        deque.push("Top");
        System.out.println(deque.pop()); // "Top"
        
        deque.clear();
        
        // --- MANIPULATING BOTH ENDS ---
        deque.offer("Middle"); // Same as offerLast
        deque.offerFirst("Head");
        deque.offerLast("Tail");
        System.out.println(deque); // [Head, Middle, Tail]
    }
}

Interview Questions

Q: Why is ArrayDeque preferred over LinkedList?
A: While both implement Deque, ArrayDeque is backed by a circular array, whereas LinkedList creates node objects for every element. ArrayDeque uses less memory (no node overhead) and is much faster due to continuous memory allocation (CPU cache locality). LinkedList should only be used if you frequently need to insert/delete elements in the middle of the collection.

Q: Can a Deque have a bounded capacity?
A: Yes. The interface itself does not mandate boundedness, but implementations like LinkedBlockingDeque (from the java.util.concurrent package) allow you to set a fixed capacity. Standard implementations like ArrayDeque and LinkedList are unbounded (they resize automatically).