What is a Deque?

Deque (Double Ended Queue) is a linear collection that supports insertion and removal of elements from both the beginning and the end.

Main features:

• Extends the Queue interface.
• Allows using itself as a stack (LIFO) or a queue (FIFO).
• Provides methods for working with both ends: addFirst, addLast, removeFirst, removeLast, peekFirst, peekLast, etc.

Main implementations in Java:

• ArrayDeque
• LinkedList

Comparison of ArrayDeque and LinkedList as Deque:

Characteristic	ArrayDeque	LinkedList
Internal structure	Dynamic array	Doubly linked list
Performance	Fast insertion/removal at ends, sequential access	Fast insertion/removal at ends, slow random access
Memory usage	More efficient for primitives, may require resizing	More overhead for nodes, more flexible in size

Example of using ArrayDeque:

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

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

        // Add to the beginning
        deque.addFirst("Element 1");
        deque.addFirst("Element 2");

        // Add to the end
        deque.addLast("Element 3");

        System.out.println(deque); // Output: [Element 2, Element 1, Element 3]

        // Remove from the beginning
        String first = deque.removeFirst();
        System.out.println("Removed from beginning: " + first); // Output: Removed from beginning: Element 2

        // Remove from the end
        String last = deque.removeLast();
        System.out.println("Removed from end: " + last);   // Output: Removed from end: Element 3

        System.out.println(deque); // Output: [Element 1]
    }
}