Перейти к основному содержимому

Введение в Java ArrayDeque

· 4 мин. чтения

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

./56bc8f1d746351b8cb948b9f28a5a163.jpg

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

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

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

4.1. ArrayDeque как стек

./733c1fece36779da18e6a9cf4fbdae4b.jpg

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

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

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

./637ed3791bf9aca3801b14d7015dd151.jpg

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

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

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

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

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

5. Вывод

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

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