Введение в Java ArrayDeque

1. Обзор

В этом руководстве мы покажем, как использовать класс Java ArrayDeque , который является реализацией интерфейса Deque .

ArrayDeque ( также известный как «Array Double Ended Queue», произносится как «ArrayDeck») — это особый вид расширяемого массива, который позволяет нам добавлять или удалять элементы с обеих сторон.

Реализация ArrayDeque может использоваться как стек (последний пришел – первый обслужен) или очередь (первый пришел – первый обслужен).

2. Краткий обзор API

Для каждой операции у нас в основном есть два варианта.

Первая группа состоит из методов, которые выдают исключение в случае сбоя операции. Другая группа возвращает статус или значение:

   | Операция    | Метод    | Исключение метода   | 
  | Вставка из головы    | `предложениеFirst(e)`    | `аддперст(е)`   | 
  | Снятие с головы    | `опроспервый()`    | `удалитьПервый()`   | 
  | Извлечение из головы    | `первый взгляд()`    | `получитьпервый()`   | 
  | Вставка из хвоста    | `предложениеПоследнее(e)`    | `добавитьпоследний(е)`   | 
  | Удаление из хвоста    | `опроспоследний()`    | `удалитьПоследний()`   | 
  | Извлечение из хвоста    | `последний просмотр()`    | `получитьпоследнее()`   | 

3. Использование методов

Давайте рассмотрим несколько простых примеров того, как мы можем использовать ArrayDeque .

3.1. Использование ArrayDeque в качестве стека

Мы начнем с примера того, как мы можем обращаться с классом как со стеком — и помещать элемент:

@Test
public void whenPush_addsAtFirst() {
    Deque<String> stack = new ArrayDeque<>();
    stack.push("first");
    stack.push("second");
 
    assertEquals("second", stack.getFirst());
}

Давайте также посмотрим, как мы можем извлечь элемент из ArrayDeque — при использовании в качестве стека:

@Test
public void whenPop_removesLast() {
    Deque<String> stack = new ArrayDeque<>();
    stack.push("first");
    stack.push("second");
 
    assertEquals("second", stack.pop());
}

Метод pop генерирует исключение NoSuchElementException , когда стек пуст.

3.2. Использование ArrayDeque в качестве очереди

Давайте теперь начнем с простого примера, показывающего, как мы можем предложить элемент в ArrayDeque — при использовании в качестве простой очереди :

@Test
public void whenOffer_addsAtLast() {
    Deque<String> queue = new ArrayDeque<>();
    queue.offer("first");
    queue.offer("second");
 
    assertEquals("second", queue.getLast());
}

И давайте посмотрим, как мы можем опросить элемент из ArrayDeque , также при использовании в качестве Queue :

@Test
public void whenPoll_removesFirst() {
    Deque<String> queue = new ArrayDeque<>();
    queue.offer("first");
    queue.offer("second");
 
    assertEquals("first", queue.poll());
}

Метод poll возвращает нулевое значение, если очередь пуста.

4. Как реализован ArrayDeque

Под капотом ArrayDeque поддерживается массивом, который удваивает свой размер при заполнении.

Первоначально массив инициализируется размером 16. Он реализован как двусторонняя очередь, в которой поддерживаются два указателя, а именно голова и хвост.

Давайте посмотрим на эту логику в действии — на высоком уровне.

4.1. ArrayDeque как стек

Как видно, когда пользователь добавляет элемент с помощью метода push , он перемещает указатель головы на единицу.

Когда мы извлекаем элемент, он устанавливает элемент в позиции head как нулевой , чтобы элемент мог быть удален сборщиком мусора, а затем перемещает указатель head на единицу назад.

4.2. ArrayDeque как очередь

Когда мы добавляем элемент с помощью метода offer , он перемещает хвостовой указатель на единицу.

В то время как, когда пользователь опрашивает элемент, он устанавливает для элемента в позиции head значение null, чтобы элемент мог быть удален сборщиком мусора, а затем перемещает указатель head.

4.3. Примечания к ArrayDeque

Наконец, еще несколько замечаний, которые стоит понять и запомнить об этой конкретной реализации:

• Это не потокобезопасно
• Нулевые элементы не принимаются
• Работает значительно быстрее, чем синхронизированный стек
• Является более быстрой очередью, чем LinkedList , из-за лучшей локальности ссылки
• Большинство операций имеют постоянную временную сложность.
• Итератор , возвращаемый ArrayDeque , является отказоустойчивым .
• ArrayDeque автоматически удваивает размер массива, когда указатель начала и хвоста встречаются друг с другом при добавлении элемента

5. Вывод

В этой короткой статье мы проиллюстрировали использование методов в ArrayDeque .

Реализацию всех этих примеров можно найти в проекте GitHub ; это проект на основе Maven, поэтому его легко импортировать и запускать как есть.