Что такое ArrayDeque?

ArrayDeque: Двусторонняя очередь на базе массива

ArrayDeque — это реализация интерфейса Deque (double-ended queue), которая использует динамический циклический массив для хранения элементов. Это одна из наиболее эффективных структур данных для операций с обоими концами коллекции.

Что означает Deque

Deque расшифровывается как «Double Ended Queue» — очередь с двумя концами. В отличие от обычной Queue, где вы добавляете в конец и удаляете из начала, Deque позволяет:

• Добавлять элементы в начало и конец
• Удалять элементы из начала и конца
• Просматривать элементы на обоих концах

Основные характеристики ArrayDeque

1. Неограниченный размер

ArrayDeque автоматически растет при необходимости:

Deque<Integer> deque = new ArrayDeque<>();
for (int i = 0; i < 1000000; i++) {
    deque.addLast(i);
}
// Массив автоматически расширился

2. Циклический массив

Внутри используется циклический массив с индексами head и tail, что обеспечивает O(1) операции с обоих концов:

// После removeFirst() и addLast() head и tail просто сдвигаются
deque.addFirst(1);   // head указывает в начало
deque.addLast(2);    // tail указывает в конец
deque.removeFirst(); // head сдвигается вперед
deque.removeLast();  // tail сдвигается назад

3. Не синхронизирована

ArrayDeque не потокобезопасна. Для многопоточного доступа нужна синхронизация:

Deque<String> deque = new ArrayDeque<>();
Deque<String> syncDeque = Collections.synchronizedDeque(deque);

Методы ArrayDeque

Добавление элементов

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

// Добавить в конец
deque.addLast(10);
deque.add(10);      // то же самое
deque.offer(10);    // то же самое, возвращает boolean

// Добавить в начало
deque.addFirst(5);
deque.offerFirst(5);

// Состояние: [5, 10]

Удаление элементов

// Удалить из конца
int last = deque.removeLast();    // выбросит исключение если пусто
last = deque.pollLast();          // вернет null если пусто

// Удалить из начала
int first = deque.removeFirst();  // выбросит исключение если пусто
first = deque.pollFirst();        // вернет null если пусто

Получение элементов без удаления

// Просмотр начала
int first = deque.getFirst();     // выбросит исключение если пусто
first = deque.peekFirst();        // вернет null если пусто

// Просмотр конца
int last = deque.getLast();       // выбросит исключение если пусто
last = deque.peekLast();          // вернет null если пусто

Поиск элементов

deque.contains(5);        // boolean
deque.size();             // количество элементов
deque.isEmpty();          // пусто ли

Использование как Stack (LIFO)

ArrayDeque эффективнее Stack:

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

// Push
stack.push("a");
stack.push("b");
stack.push("c");

// Pop
String top = stack.pop();  // "c"
top = stack.pop();         // "b"

// Peek
top = stack.peek();        // "a"

Использование как Queue (FIFO)

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

// Enqueue
queue.add("first");
queue.add("second");
queue.add("third");

// Dequeue
String item = queue.remove();  // "first"
item = queue.remove();         // "second"

// Peek
item = queue.peek();           // "third"

Временная сложность операций

Практические примеры

Пример 1: Обращение последовательности

public static void reverseSequence(int[] arr) {
    Deque<Integer> deque = new ArrayDeque<>();
    
    for (int num : arr) {
        deque.push(num);  // push in stack style
    }
    
    while (!deque.isEmpty()) {
        System.out.print(deque.pop() + " ");  // pop from top
    }
}

Пример 2: Скользящее окно

public static void slidingWindow(int[] nums, int k) {
    Deque<Integer> deque = new ArrayDeque<>();
    
    for (int i = 0; i < nums.length; i++) {
        // Удалить индексы, которые вне окна
        while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
            deque.removeFirst();
        }
        
        // Удалить меньшие элементы
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
            deque.removeLast();
        }
        
        deque.addLast(i);
        
        if (i >= k - 1) {
            System.out.print(nums[deque.peekFirst()] + " ");
        }
    }
}

ArrayDeque vs LinkedList

Обе реализуют Deque, но:

• ArrayDeque — быстрее благодаря кэширванию массива (лучше locality of reference)
• LinkedList — позволяет получить доступ к элементам в середине быстрее
• ArrayDeque предпочтительнее для большинства использований

Когда использовать ArrayDeque

1. Стек операций — отмена/повтор функций
2. Очередь задач — обработка в порядке поступления
3. Алгоритмы с окном — скользящее окно, BFS
4. DFS и backtracking — как замена Stack
5. Системы планирования — задачи с приоритетом

ArrayDeque — это универсальная, высокопроизводительная структура данных, незаменимая в арсенале Java разработчика.