Deque

Double Ended Queue is an abstract data structure that allows us to enqueue from both of the sides but dequeue can only be done either of the side (rear or front). We have to decide before writing a code whether we are allowing dequeue from front or rear. We can implement the deque using an Array or Linked List. It is easy to create Deque using a linked list but in an array, we need to very careful to implement it. 

Dequeue From Rear

Dequeue From Front

NOTE: -Generic <T> type can accept any data type, If you have not passed explicitly then it will consider it as an Object.

Deque Implementation using an Array

#1 Initialization of Custom Deque - O(1)

public class CustomDeque<T> {
    T[] data;
    int length, front, rear, capacity;

    public CustomDeque(T[] data) {
        this.data = data;
        capacity = data.length;
    }

}

#2 Adding Element at the Front - O(1)

public void addFirst(T ele) {
    if (ele == null)
        throw new NullPointerException();
    if (length < capacity) {
        if ((length == 0  && front == 0) || (length > 0 && front == 0)) {
            front = capacity-1;
        } else
            front = front -1;
        if (rear == -1){
            rear = front;
        }
        data[front] = ele;
        length++;
    } else {
        throw new IllegalStateException();
    }
}

#3 Adding Element at the Rear - O(1)

public void addLast(T ele) {
    if (ele == null) {
        throw new NullPointerException();
    }
    if (length < capacity) {
        if (rear == capacity-1 || rear == -1){
            rear = 0;
        } else
            rear++;
        data[rear] = ele;
        length++;
    } else {
        throw new IllegalStateException();
    }
}

#4 Removing Element at the Front - O(1)

public T removeFirst() {
    if (length > 0) {
        T val = data[front];
        data[front] = null;
        if (length > 0 && front == capacity -1) {
            front = 0;
        } else
            front++;
        length--;
        return val;
    }
    rear  =  -1;
    front = 0;
    throw new NoSuchElementException();
}

#4 Removing Element at the Rear - O(1)

public T removeLast() {
    if (length > 0) {
        T val = data[rear];
        data[rear] = null;
        if (length > 0 && rear == 0){
            rear = capacity - 1;
        } else
            rear--;
        length--;
        return val;
    }
    rear  =  -1;
    front = 0;
    throw new NoSuchElementException();
}

#5 Peek Element at the Front - O(1)

public T getFirst() {
    if (length > 0) {
        return data[front];
    }
    throw new NoSuchElementException();
}

#6 Peek Element at the Rear - O(1)

public T getLast() {
    if (length > 0) {
        return data[rear];
    }
    throw new NoSuchElementException();
}

Deque Implementation using Linked List

#1 Initialization of Custom Deque - O(1)

public class CustomDeque<T> {
    Node<T> front, rear;
    int length = 0;

    class Node<T> {
        Node<T> next;
        T data;
        Node<T> previous;

        public Node() {
        }

        public Node(T data) {
            this.data = data;
        }

        public Node(Node<T> next, T data, Node<T> previous) {
            this.next = next;
            this.data = data;
            this.previous = previous;
        }
    }
}

#2 Adding Element at the Front - O(1)

public void addFirst(T ele) {
    if (ele == null){
        throw new NullPointerException();
    }
    if (front == null) {
        front = rear = new Node<>(ele);
    } else {
     front.previous = new Node<>(front, ele, null);
     front = front.previous;
    }
    length++;
}

#3 Adding Element at the Rear - O(1)

public void addLast(T ele) {
    if (ele == null)
        throw new NullPointerException();
    if (rear == null) {
        front = rear = new Node<>(ele);
    } else {
        rear.next = new Node<>(null, ele, rear);
        rear = rear.next;
    }
    length++;
} 

#4 Removing Element at the Front - O(1)

public T removeFirst() {
    if (length > 0) {
        T val = front.data;
        front = front.next;
        front.previous = null;
        length--;
        return val;
    }
    throw new NoSuchElementException();
}

#5 Removing Element at the Rear - O(1)

public T removeLast() {
   if (length > 0 ){
       T val = rear.data;
       rear = rear.previous;
       rear.next = null;
       length--;
       return val;
   }
   throw new NoSuchElementException();
}

#6 Peek Element at the Front - O(1)

public T getFirst() {
    if (length > 0) {
        return front.data;
    }
    throw new NoSuchElementException();
}

#7 Peek Element at the Rear - O(1)

public T getLast() {
    if (length > 0) {
        return rear.data;
    }
    throw new NoSuchElementException();
}