В каких алгоритмических задачах или сценариях используется Deque (двусторонняя очередь) в Java?

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

Типичные сценарии использования:

1. Реализация стека (LIFO): ArrayDeque предпочтительнее устаревшего класса Stack.

   Deque<Integer> stack = new ArrayDeque<>();
   stack.push(1); stack.push(2); // [2, 1]
   int top = stack.pop(); // Вернет 2

2. Реализация очереди (FIFO): ArrayDeque также эффективнее LinkedList для обычной очереди.

   Deque<Integer> queue = new ArrayDeque<>();
   queue.offer(1); queue.offer(2); // [1, 2]
   int first = queue.poll(); // Вернет 1

3. Алгоритм «скользящего окна» (Sliding Window): Требует быстрого доступа к максимуму/минимуму в окне. Используется монотонная очередь на основе Deque.

   // Пример: поиск максимума в каждом окне размера k
   Deque<Integer> indices = new ArrayDeque<>();
   for (int i = 0; i < nums.length; i++) {
       // Удаляем индексы, вышедшие за границу окна
       if (!indices.isEmpty() && indices.peekFirst() == i - k) {
           indices.pollFirst();
       }
       // Поддерживаем убывающий порядок значений в deque
       while (!indices.isEmpty() && nums[indices.peekLast()] < nums[i]) {
           indices.pollLast();
       }
       indices.offerLast(i);
       // Максимум для окна — элемент в начале deque
       if (i >= k - 1) result[i - k + 1] = nums[indices.peekFirst()];
   }

4. Обход графа (BFS) или задачи с палиндромами, где требуется проверка символов с обоих концов строки.

Ключевой выбор: ArrayDeque — стандартный выбор для стеков/очередей из-за высокой производительности и меньшего потребления памяти по сравнению с LinkedList.