ArrayDeque

In Java, the Deque interface is implemented by classes such as ArrayDeque and LinkedList. This section offers a brief introduction to the two main Java implementations of the Deque interface:

1. ArrayDeque: A resizable-array implementation of the Deque interface. It's typically faster than LinkedList when used as a queue and outperforms Stack when used as a stack. ArrayDeque does not allow null elements. If you need a resizable Deque supporting null elements, consider LinkedList.

2. LinkedList: A doubly-linked list implementation of the Deque interface. It supports all optional list operations and allows all elements, including null. In addition to deque operations, the LinkedList class provides various methods for manipulating elements at both ends.

API

Java's ArrayDeque has two constructors:

1. ArrayDeque(): This no-argument constructor initializes an empty array deque with an initial capacity sufficient to hold 16 elements. It is useful when you are creating an empty ArrayDeque without a predetermined size.

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

2. ArrayDeque(int numElements): This constructor initializes an empty array deque with an initial capacity specified by the number of elements. This is useful when you already know how many elements the ArrayDeque will contain.

   Deque<String> deque = new ArrayDeque<String>(100);
   

In the second example, the ArrayDeque is initialized with a capacity large enough to hold 100 elements. This can be more efficient if you anticipate adding a large number of items to the deque.

Keep in mind that ArrayDeque objects in Java are dynamic, meaning they can grow and shrink at runtime. Therefore, even if you initialize an ArrayDeque with a specific capacity, it can still expand beyond that if necessary. Setting an initial capacity is mainly for performance optimization; it allows the ArrayDeque to operate more efficiently by reducing the need for frequent resizing.

Adding elements:

• addFirst(E e): Adds the specified element at the beginning of the deque.
• addLast(E e): Adds the specified element to the end of the deque.

  deque.addFirst("Element 1");
  deque.addLast("Element 2");
  

Removing elements:

• removeFirst(): Removes and returns the first element from the deque. If the deque is empty, this method throws NoSuchElementException
• removeLast(): Removes and returns the last element from the deque. If the deque is empty, this method throws a NoSuchElementException.

  String firstElement = deque.removeFirst();
  String lastElement = deque.removeLast();
  

Deque size:

• size(): Returns the number of elements in the deque.
• isEmpty(): Returns true if the deque contains no elements.

  int size = deque.size();
  boolean isEmpty = deque.isEmpty();
  

Clearing the deque:

• clear(): Removes all elements from the deque.

  deque.clear();
  

Iterating over the deque:

• You can use a foreach loop to iterate through the elements in the deque. Note that the iterator for ArrayDeque returns elements in a queue-like order, from the first (head) to the last (tail).

  for (String element : deque) {
      System.out.println(element);
  }
  

Remember that ArrayDeque does not permit null elements. Attempting to use addFirst(null), addLast(null), offerFirst(null), or offerLast(null), will result in a NullPointerException.

Example: checking for palindrome

A Deque can be used to check if a string is a palindrome, meaning it reads the same forwards and backwards. To do this, add each character of the string to the Deque. Then, repeatedly compare and remove the first and last characters to determine if the string is a palindrome.

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

public class Main {
    public static boolean isPalindrome(String str) {
        Deque<Character> deque = new ArrayDeque<Character>();

        for (int i = 0; i < str.length(); i++) {
            deque.addLast(str.charAt(i));
        }

        while (deque.size() > 1) {
            char first = deque.removeFirst();
            char last = deque.removeLast();
            if (first != last) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        String str = "radar";
        if (isPalindrome(str)) {
            System.out.println(str + " is a palindrome.");
        } else {
            System.out.println(str + " is not a palindrome.");
        }
    }
}

Conclusion

ArrayDeque is a versatile data structure in Java, implementing the Deque interface. It provides functionality for both a double-ended queue and a stack. Notably, it offers constant time complexity for adding or removing elements from either end, which makes it more efficient than other data structure implementations for specific tasks. It's crucial to understand that ArrayDeque does not allow null elements and is not thread-safe; it requires external synchronization if used in a multi-threaded environment. Overall, ArrayDeque serves as a powerful tool for developers in need of dynamic, resizable data structures that offer efficient operations.