Deque Implementation in Java

A Deque (pronounced as "deck") stands for "Double Ended Queue." It is an abstract data type that generalizes a queue, allowing elements to be added or removed from both the front and the rear. This provides a greater degree of flexibility compared to a traditional queue or stack. It can be seen as a hybrid of both stack and queue data structures.

In this article, we will dive deep into implementing a deque in Java, exploring its operations, and understanding its potential use cases. 

Deque Operations

The primary operations associated with a deque include: 

• Inserting an element at the front. 
• Inserting an element at the rear. 
• Deleting an element from the front. 
• Deleting an element from the rear. 

Deque Implementation using Java's LinkedList

Java's LinkedList class (from the java.util package) inherently supports all deque operations. We will harness this capability to construct our deque:

import java.util.LinkedList;

class Deque<T> {
    LinkedList<T> dequeList = new LinkedList<T>();

    // Adds an item at the front of Deque.
    public void insertFront(T item) {
        dequeList.addFirst(item);
    }

    // Adds an item at the rear of Deque.
    public void insertRear(T item) {
        dequeList.addLast(item);
    }

    // Removes the front item from Deque.
    public T removeFront() {
        return dequeList.pollFirst();
    }

    // Removes the rear item from Deque.
    public T removeRear() {
        return dequeList.pollLast();
    }

    // Gets the front item from Deque without removing it.
    public T getFront() {
        return dequeList.peekFirst();
    }

    // Gets the rear item from Deque without removing it.
    public T getRear() {
        return dequeList.peekLast();
    }

    // Checks if the deque is empty.
    public boolean isEmpty() {
        return dequeList.isEmpty();
    }

    // Returns the size of the deque.
    public int size() {
        return dequeList.size();
    }
}

Testing the Deque Implementation:

public class Main {
    public static void main(String[] args) {
        Deque<Integer> deque = new Deque<>();

        deque.insertFront(10);
        deque.insertRear(20);
        deque.insertFront(5);
        deque.insertRear(25);

        System.out.println("Front: " + deque.getFront());   // 5
        System.out.println("Rear: " + deque.getRear());     // 25

        deque.removeFront();
        deque.removeRear();

        System.out.println("Front after removing: " + deque.getFront());   // 10
        System.out.println("Rear after removing: " + deque.getRear());     // 20
    }
}

Output:

Front: 5
Rear: 25
Front after removing: 10
Rear after removing: 20

Advantages of Deque

Versatility: Deque seamlessly integrates the features of both stacks and queues. 

Flexibility: Deque's design allows you to manipulate both ends, making it ideal for scenarios requiring dynamic data handling. 

Efficiency: Operations on a deque (using a doubly-linked list) generally run in constant time, making them efficient.