ArrayDeque: примеры (JAVA)

Примеры базовых операций

Небольшие примеры и ожидаемые результаты.

Создание и добавление элементов

import java.util.ArrayDeque;

public class Demo1 {
    public static void main(String[] args) {
        ArrayDeque<String> dq = new ArrayDeque<>();
        dq.addLast("a");
        dq.addFirst("b");
        dq.offerLast("c");
        System.out.println(dq); // печать через toString
    }
}

[b, a, c]

Различие remove/poll и get/peek

ArrayDeque<Integer> dq = new ArrayDeque<>();
System.out.println(dq.pollFirst()); // пустая очередь
try {
    System.out.println(dq.removeFirst());
} catch (Exception e) {
    System.out.println(e.getClass().getSimpleName());
}

null
NoSuchElementException

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

ArrayDeque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.isEmpty());

2
1
true

Итерация в прямом и обратном порядке

ArrayDeque<String> dq = new ArrayDeque<>();
dq.addLast("x"); dq.addLast("y"); dq.addLast("z");
for (String s : dq) System.out.print(s + " ");
System.out.println();
var it = dq.descendingIterator();
while (it.hasNext()) System.out.print(it.next() + " ");

x y z 
z y x 

Аналоги в Java и их отличия

• LinkedList - реализует Deque на основе двусвязного списка. Лучше при частых произвольных удалениях/вставках внутри структуры; использует больше памяти на узел и медленнее по locality по сравнению с ArrayDeque.
• ArrayList - не deque, но при реализации очереди требует сдвига элементов или циклического буфера. Выбор в пользу ArrayList оправдан при частом доступе по индексу.
• ConcurrentLinkedDeque - потокобезопасная неблокирующая реализация Deque; предпочтительна при высококонкурентных операциях без внешней синхронизации.
• LinkedBlockingDeque - блокирующая очереди с ограничением емкости, подходит для producer-consumer сценариев с блокировкой при переполнении/опустошении.
• Stack - устаревшая классическая реализация стека; рекомендуется применять ArrayDeque для стека вместо Stack.

Аналоги в других языках

• Python - collections.deque. Поддерживает быстрые операции на концах, не принимает ограничений по null-equivalent. Пример:

  from collections import deque
  dq = deque()
  dq.append(1)
  dq.appendleft(0)
  print(list(dq))

  [0, 1]

  Отличие: встроенная в стандартную библиотеку, удобные методы rotate, clear.
• JavaScript - нет встроенного Deque; обычно используется Array с методами push/pop/unshift/shift. Пример:

  let dq = [];
  dq.push(1);
  dq.unshift(0);
  console.log(dq);

  [0, 1]

  Отличие: операции в начале массива (unshift/shift) имеют линейную сложность для больших массивов.
• C# - в BCL нет ArrayDeque; часто применяется LinkedList<T> или сторонние реализации Deque. Пример через LinkedList:

  var dq = new System.Collections.Generic.LinkedList<int>();
  dq.AddLast(1);
  dq.AddFirst(0);
  Console.WriteLine(string.Join(", ", dq));

  0, 1

  Отличие: LinkedList обеспечивает быстрые операции на концах, но отличается по локальности данных.
• Go - стандартный пакет container/list для двусвязного списка; часто используют срезы (slices) как дек при аккуратном управлении. Пример с list:

  package main
  
  import (
      "container/list"
      "fmt"
  )
  
  func main() {
      dq := list.New()
      dq.PushBack(1)
      dq.PushFront(0)
      for e := dq.Front(); e != nil; e = e.Next() {
          fmt.Print(e.Value, " ")
      }
  }
  

  0 1 

  Отличие: нет встроенного массивного deque с автопереразмериванием, используются списки или срезы.
• PHP - класс SplDoublyLinkedList или массивы; SplDoublyLinkedList поддерживает вставку и удаление с концов. Пример:

  $dq = new SplDoublyLinkedList();
  $dq->push(1);
  $dq->unshift(0);
  foreach ($dq as $v) echo $v . ' ';

  0 1 

  Отличие: SplDoublyLinkedList - двусвязный список, имеет свои ограничения и API.
• Kotlin - в стандартной библиотеке есть ArrayDeque (в более новых версиях) и можно использовать Java ArrayDeque через интероп. Пример Kotlin:

  val dq = ArrayDeque()
  dq.addLast(1)
  dq.addFirst(0)
  println(dq)

  [0, 1]

  Отличие: Kotlin-версия интегрирована со стандарной коллекцией Kotlin и имеет удобную Kotlin-ориентированную API.
• Lua - обычно используется table с table.insert и table.remove либо пользовательские реализации двусторонней очереди.
• SQL - концепция deque не применима напрямую; очереди моделируются таблицами и транзакциями.

Типичные ошибки и их проявления

• Добавление null - попытка add(null) или offer(null) приводит к NullPointerException. Пример:

  ArrayDeque<String> dq = new ArrayDeque<>();
  try {
      dq.add(null);
  } catch (Exception e) {
      System.out.println(e.getClass().getSimpleName());
  }

  NullPointerException

• Удаление из пустой очереди - методы removeFirst/removeLast/pop/getFirst/getLast бросают NoSuchElementException при пустой коллекции. Пример выше в разделе examples показывает результат.
• ConcurrentModificationException - итератор ArrayDeque является fail-fast. Если структура изменяется извне во время обхода (например, вызовом addLast), итератор может бросить ConcurrentModificationException:

  ArrayDeque<Integer> dq = new ArrayDeque<>();
  dq.addLast(1);
  for (Integer x : dq) {
      dq.addLast(2); // изменение во время обхода
  }
  

  Exception in thread "main" java.util.ConcurrentModificationException
      at java.base/java.util.ArrayDeque$DeqIterator.checkForComodification(ArrayDeque.java:xxx)
      ...

• Неявные приведения типов - при использовании необобщённых типов возможны ClassCastException при извлечении элементов в ожидаемый тип.
• Использование в многопоточной среде без синхронизации - приводит к состояниям гонки, частичным потерям данных и некорректной работе; предпочтительнее применять потокобезопасные коллекции или внешнюю синхронизацию.

Изменения и совместимость

API ArrayDeque в основном стабилен и не претерпел значимых изменений на уровне публичного контракта в последних версиях JDK. Мелкие оптимизации реализации и исправления производительности могли вноситься между релизами, но методы и поведение сохраняют обратную совместимость. Для специфики версий рекомендуется сверяться с заметками к релизам используемой версии JDK.

Расширенные и редкие сценарии использования

Слайдинговое окно - максимум за O(n)

import java.util.ArrayDeque;

public class SlidingMax {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || k <= 0) return new int[0];
        int n = nums.length;
        int[] ans = new int[n - k + 1];
        ArrayDeque<Integer> dq = new ArrayDeque<>(); // хранит индексы
        for (int i = 0; i < n; i++) {
            // убрать индексы вне окна
            while (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();
            // поддерживать убывающий порядок по значениям
            while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) dq.pollLast();
            dq.addLast(i);
            if (i >= k - 1) ans[i - k + 1] = nums[dq.peekFirst()];
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] a = {1,3,-1,-3,5,3,6,7};
        int[] r = maxSlidingWindow(a, 3);
        for (int v : r) System.out.print(v + " ");
    }
}

3 3 5 5 6 7 

0-1 BFS (deque для рёбер веса 0 и 1)

// Упрощённый псевдо-Java пример использования deque для 0-1 BFS
import java.util.*;

class Edge { int to, w; Edge(int t, int w){to=t;w=w;} }

// Код демонстрирует идею: при рёбрах веса 0 - addFirst, веса 1 - addLast

(Визуальное объяснение: использование addFirst для приоритетных переходов и addLast для обычных.)

Реализация вращения очереди (rotate)

ArrayDeque<Integer> dq = new ArrayDeque<>();
dq.addLast(1); dq.addLast(2); dq.addLast(3);
// сдвиг влево на 1
dq.addLast(dq.pollFirst());
System.out.println(dq);

[2, 3, 1]

Использование clone()

ArrayDeque<String> original = new ArrayDeque<>();
original.addLast("a");
@SuppressWarnings("unchecked")
ArrayDeque<String> copy = (ArrayDeque<String>) original.clone();
copy.addLast("b");
System.out.println(original);
System.out.println(copy);

[a]
[a, b]

Ограничение размера вручную (bounded deque)

int capacity = 3;
ArrayDeque<Integer> dq = new ArrayDeque<>();
for (int i=1;i<=5;i++){
    if (dq.size() >= capacity) dq.pollFirst(); // удержание фиксированного размера
    dq.addLast(i);
    System.out.println(dq);
}

[1]
[1, 2]
[1, 2, 3]
[2, 3, 4]
[3, 4, 5]

Использование как буфер сообщений с внешней синхронизацией

// при многопоточном доступе возможна синхронизация
ArrayDeque<String> dq = new ArrayDeque<>();

synchronized(dq) {
    if (!dq.isEmpty()) System.out.println(dq.pollFirst());
}

(Зависит от содержимого очереди)

Примеры показывают гибкость ArrayDeque: от простых вставок и извлечений до алгоритмов с гарантированной производительностью. В задачах с высокими требованиями к многопоточности рекомендуется выбирать потокобезопасные аналоги или применять внешнюю синхронизацию.