Double Ended Queues

In the previous lessons, we covered the basic queue data structure along with its implementations and operations. Now, let's explore another variant of the queue called a Double Ended Queue (Deque).

A Double Ended Queue is a type of queue where insertion and deletion operations can be performed at both ends, i.e., the front and the rear. This allows for more flexibility in manipulating and accessing the elements in the queue.

Implementation

Double Ended Queues can be implemented using arrays or linked lists. In Java, the Deque interface provides a way to implement Double Ended Queues. Java provides two classes that implement the Deque interface:

1. ArrayDeque: It is an implementation of Deque using a resizable array.
2. LinkedList: It is an implementation of Deque using a doubly-linked list.

Here's an example of using the Deque interface to implement a Double Ended Queue in Java:

1{{code}}

Output:

1Deque: [E, L, O]
2Removed Element: E
3Updated Deque: [L, O]

xxxxxxxxxx

import java.util.Deque;

import java.util.LinkedList;

​

public class Main {

    public static void main(String[] args) {

        Deque<String> deque = new LinkedList<>();

​

        deque.addFirst("E");

        deque.addLast("L");

        deque.addLast("O");

​

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

​

        String element = deque.removeFirst();

​

        System.out.println("Removed Element: " + element);

​

        System.out.println("Updated Deque: " + deque);

    }

}