Java Deque Interface

---

The Deque (short for Double-Ended Queue) is a linear data structure in Java that allows elements to be added or removed from both ends. It is an extension of the Queue interface in the Java Collections Framework, offering more flexibility than a regular queue or stack. With a Deque, you can treat it as both a queue (FIFO) and a stack (LIFO) depending on how you add or remove elements.

---

What is the Java Deque Interface?

The Deque interface is part of the java.util package and extends the Queue interface. It represents a double-ended queue, allowing for the insertion and removal of elements at both the front and the back of the queue. This makes it more versatile than a traditional queue, where elements are only added at the rear and removed from the front.

Unlike a standard queue, which follows the First-In-First-Out (FIFO) order, a Deque can operate as a FIFO queue, a Last-In-First-Out (LIFO) stack, or a combination of both. This makes the Deque a powerful data structure for various use cases.

---

Key Methods of the Java Deque Interface

The Deque interface provides several methods for working with elements from both ends of the queue:

• addFirst(E e): Adds the specified element at the front of the deque.
• addLast(E e): Adds the specified element at the end of the deque.
• offerFirst(E e): Inserts the element at the front, returning true if successful.
• offerLast(E e): Inserts the element at the end, returning true if successful.
• removeFirst(): Removes and returns the first element.
• removeLast(): Removes and returns the last element.
• pollFirst(): Removes and returns the first element, or null if the deque is empty.
• pollLast(): Removes and returns the last element, or null if the deque is empty.
• getFirst(): Retrieves, but does not remove, the first element.
• getLast(): Retrieves, but does not remove, the last element.
• peekFirst(): Returns the first element without removing it, or null if the deque is empty.
• peekLast(): Returns the last element without removing it, or null if the deque is empty.
• size(): Returns the number of elements in the deque.
• isEmpty(): Checks if the deque is empty.

---

Common Implementations of the Java Deque Interface

Several classes implement the Deque interface, each offering different characteristics based on the underlying data structure:

1. ArrayDeque: A resizable array implementation of the Deque interface. It is faster than LinkedList for most use cases and supports adding and removing elements from both ends efficiently.

2. LinkedList: A doubly linked list that implements both the Deque and List interfaces. It is slower than ArrayDeque in most cases but provides additional list-related functionality.

3. ConcurrentLinkedDeque: A thread-safe version of Deque for use in multi-threaded environments. It is part of the java.util.concurrent package.

---

Using the Java Deque Interface: Code Examples

Let’s look at practical examples using the Deque interface with some common implementations.

Example 1: Using ArrayDeque as a Deque

ArrayDeque is one of the most commonly used implementations of the Deque interface. It supports fast insertions and removals at both ends.

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

public class Main {
    public static void main(String[] args) {
        // Creating a Deque using ArrayDeque
        Deque<String> deque = new ArrayDeque<>();

        // Adding elements at both ends
        deque.addFirst("First");
        deque.addLast("Last");

        // Displaying the deque
        System.out.println("Deque: " + deque);

        // Removing and displaying elements from both ends
        System.out.println("Removed First: " + deque.removeFirst());
        System.out.println("Removed Last: " + deque.removeLast());

        // Checking the size of the deque
        System.out.println("Deque size after removal: " + deque.size());
    }
}

Output:

Deque: [First, Last]
Removed First: First
Removed Last: Last
Deque size after removal: 0

Example 2: Using LinkedList as a Deque

While ArrayDeque is often preferred for better performance, LinkedList also implements the Deque interface and can be used when you need additional functionality from the List interface.

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

public class Main {
    public static void main(String[] args) {
        // Creating a Deque using LinkedList
        Deque<String> deque = new LinkedList<>();

        // Adding elements at both ends
        deque.offerFirst("Apple");
        deque.offerLast("Banana");

        // Displaying the deque
        System.out.println("Deque: " + deque);

        // Removing and displaying elements from both ends
        System.out.println("Removed First: " + deque.pollFirst());
        System.out.println("Removed Last: " + deque.pollLast());

        // Checking the size of the deque
        System.out.println("Deque size after removal: " + deque.size());
    }
}

Output:

Deque: [Apple, Banana]
Removed First: Apple
Removed Last: Banana
Deque size after removal: 0

Example 3: Deque as a Stack (LIFO Behavior)

A Deque can also be used as a stack, where elements are added and removed from the same end (the top of the stack).

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

public class Main {
    public static void main(String[] args) {
        // Creating a Deque using ArrayDeque
        Deque<String> stack = new ArrayDeque<>();

        // Pushing elements onto the stack (add to the front)
        stack.push("Red");
        stack.push("Green");
        stack.push("Blue");

        // Displaying the stack
        System.out.println("Stack: " + stack);

        // Popping elements from the stack (remove from the front)
        System.out.println("Popped Element: " + stack.pop());

        // Displaying the stack after pop
        System.out.println("Stack after pop: " + stack);
    }
}

Output:

Stack: [Blue, Green, Red]
Popped Element: Blue
Stack after pop: [Green, Red]

In this case, the Deque behaves like a stack, where the last element added is the first to be removed (LIFO).

Example 4: Deque as a Queue (FIFO Behavior)

In its simplest form, a Deque can also function as a queue, where elements are added at the end and removed from the front.

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

public class Main {
    public static void main(String[] args) {
        // Creating a Deque using ArrayDeque
        Deque<String> queue = new ArrayDeque<>();

        // Adding elements to the queue
        queue.offer("One");
        queue.offer("Two");
        queue.offer("Three");

        // Displaying the queue
        System.out.println("Queue: " + queue);

        // Removing elements from the front of the queue
        System.out.println("Polled Element: " + queue.poll());

        // Displaying the queue after poll
        System.out.println("Queue after poll: " + queue);
    }
}

Output:

Queue: [One, Two, Three]
Polled Element: One
Queue after poll: [Two, Three]

In this example, the Deque behaves like a queue, following the FIFO (First-In-First-Out) principle.

---

When to Use a Java Deque

The Deque is ideal for the following use cases:

• Double-ended queue: When you need to add or remove elements from both ends of a collection efficiently.
• Stack operations: If you need a Last-In-First-Out (LIFO) structure for managing elements.
• Queue operations: If you need a First-In-First-Out (FIFO) structure for managing tasks or events.
• Palindrome checking: Storing characters or elements from both ends to check for symmetry.

---

Deque vs. Queue and Stack

• Deque vs. Queue: A Deque allows insertion and removal of elements at both ends, while a Queue only allows access from one end (FIFO).
• Deque vs. Stack: A Deque can be used as a stack, but a Stack allows only operations at the top (LIFO).
• Deque vs. LinkedList: LinkedList can also function as a Deque, but it is generally slower than ArrayDeque for most operations.

---

---