«Введение в Java ArrayDeque»

«1. Обзор

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

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

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

2. Обзор API

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

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

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 as Stack

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

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

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

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

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

4.3. Замечания по ArrayDeque

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

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

5. Заключение

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

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