Что такое Deque?

Что такое Deque?

Deque (Double Ended Queue) — это специальная структура данных в Java, которая позволяет добавлять и удалять элементы с обоих концов, в отличие от обычной очереди (Queue), где операции доступа ограничены одним концом.

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

Deque — это интерфейс, расширяющий Queue, с дополнительными методами для работы с обоими концами структуры:

// Операции на начало
void addFirst(E e);      // Добавить элемент в начало
E removeFirst();         // Удалить первый элемент
E getFirst();            // Получить первый элемент

// Операции на конец
void addLast(E e);       // Добавить элемент в конец
E removeLast();          // Удалить последний элемент
E getLast();             // Получить последний элемент

// Методы из Queue (работают с началом/концом)
boolean add(E e);        // Эквивалент addLast()
E remove();              // Эквивалент removeFirst()
E element();             // Эквивалент getFirst()

// Безопасные версии
boolean offerFirst(E e); // addFirst без исключений
E pollFirst();           // removeFirst, но null если пусто
E peekFirst();           // getFirst, но null если пусто

Основные реализации Deque

1. LinkedList

Реализует интерфейсы List, Deque, Queue одновременно. На основе двусвязного списка.

Deque<Integer> deque = new LinkedList<>();
deque.addFirst(10);  // 10
deque.addLast(20);   // 10, 20
deque.addFirst(5);   // 5, 10, 20
int first = deque.removeFirst();  // 5
int last = deque.removeLast();    // 20
// Осталось: 10

2. ArrayDeque

Реализована на основе циклического массива. Более эффективна по памяти и быстродействию, чем LinkedList. НЕ потокобезопасна.

Deque<String> deque = new ArrayDeque<>();
deque.push("first");   // addFirst()
deque.push("second");  // addFirst() — начало [second, first]
deque.poll();          // removeFirst() — [first]
deque.addLast("last"); // [first, last]

3. ConcurrentLinkedDeque

Потокобезопасная реализация на основе связного списка.

Практические применения

1. Реализация стека (Stack)

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);      // addFirst()
stack.push(2);
int top = stack.pop();  // removeFirst()

2. Реализация очереди (Queue)

Deque<Integer> queue = new ArrayDeque<>();
queue.addLast(1);      // Добавляем в конец
queue.addLast(2);
int first = queue.removeFirst();  // Удаляем с начала

3. Алгоритм скользящего окна

public int[] maxSlidingWindow(int[] nums, int k) {
    Deque<Integer> deque = new ArrayDeque<>();
    List<Integer> result = new ArrayList<>();
    
    for(int i = 0; i < nums.length; i++) {
        // Удаляем элементы вне окна
        if(!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) {
            result.add(nums[deque.peekFirst()]);
        }
    }
    
    return result.stream().mapToInt(Integer::intValue).toArray();
}

4. Проверка палиндрома

public boolean isPalindrome(String s) {
    Deque<Character> deque = new ArrayDeque<>();
    for(char c : s.toCharArray()) {
        deque.add(Character.toLowerCase(c));
    }
    
    while(deque.size() > 1) {
        if(!deque.removeFirst().equals(deque.removeLast())) {
            return false;
        }
    }
    return true;
}

Сравнение методов

Когда использовать какую реализацию

• ArrayDeque — предпочтительна для большинства случаев. Быстра, эффективна по памяти, хороша для стеков и очередей
• LinkedList — когда часто вставляют/удаляют в середину (хотя Deque не поддерживает это напрямую)
• ConcurrentLinkedDeque — в многопоточной среде без блокировки

Важные замечания

• Deque более универсальна, чем Queue или Stack
• ArrayDeque обычно работает быстрее LinkedList
• В многопоточных приложениях используй ConcurrentLinkedDeque или синхронизацию