Deque Queue Implementation in Java

1. Introduction

A deque (pronounced as 'deck') or a double-ended queue is a data structure that allows insertion and deletion from both ends, i.e., front and rear. This structure provides a more generalized form of a queue and a stack. 

Deques are commonly used in algorithms where data needs to be processed from both ends, like the sliding window algorithm, palindrome checking, and more.

2. Implementation Steps

1. Define a Deque class.

2. Within the class:

a. Declare an ArrayList to store the deque elements.

b. Provide methods like insertFront(), insertRear(), deleteFront(), deleteRear(), getFront(), getRear(), and isEmpty().

3. Implement the methods to handle operations at both ends of the deque.

4. Create an instance of the deque class and perform operations to demonstrate its functionality.

3. Implementation in Java

import java.util.ArrayList;
public class Deque<T> {
    private ArrayList<T> deque;
    // Constructor
    public Deque() {
        deque = new ArrayList<>();
    }
    // Check if the deque is empty
    public boolean isEmpty() {
        return deque.isEmpty();
    }
    // Add element to the front of the deque
    public void insertFront(T data) {
        deque.add(0, data);
    }
    // Add element to the rear of the deque
    public void insertRear(T data) {
        deque.add(data);
    }
    // Remove and return front element from the deque
    public T deleteFront() {
        if (isEmpty()) {
            System.out.println("Deque is empty. Can't delete from front.");
            return null;
        }
        return deque.remove(0);
    }
    // Remove and return rear element from the deque
    public T deleteRear() {
        if (isEmpty()) {
            System.out.println("Deque is empty. Can't delete from rear.");
            return null;
        }
        return deque.remove(deque.size() - 1);
    }
    // View front element without removing it
    public T getFront() {
        if (isEmpty()) {
            System.out.println("Deque is empty. Nothing at the front.");
            return null;
        }
        return deque.get(0);
    }
    // View rear element without removing it
    public T getRear() {
        if (isEmpty()) {
            System.out.println("Deque is empty. Nothing at the rear.");
            return null;
        }
        return deque.get(deque.size() - 1);
    }
    public static void main(String[] args) {
        Deque<Integer> d = new Deque<>();
        d.insertFront(10);
        d.insertRear(20);
        d.insertFront(5);
        System.out.println("Front element: " + d.getFront());  // Outputs 5
        System.out.println("Rear element: " + d.getRear());  // Outputs 20
        System.out.println("Deleted from front: " + d.deleteFront());  // Outputs 5
        System.out.println("Front element after delete: " + d.getFront());  // Outputs 10
    }
}

Output:

Front element: 5
Rear element: 20
Deleted from front: 5
Front element after delete: 10

Explanation:

1. A generic Deque class is defined. This allows us to use the deque with any data type.

2. The isEmpty() method checks whether the deque is empty by checking the deque list.

3. The insertFront() and insertRear() methods allow the insertion of elements at the front and rear of the deque respectively.

4. The deleteFront() and deleteRear() methods remove and return elements from the front and rear of the deque respectively.

5. The getFront() and getRear() methods provide a way to view the front and rear elements without removing them.

6. In the main() method, we create a Deque of Integers, insert elements from both ends and perform some operations to demonstrate its functionality.