1. Обзор
В этом уроке мы покажем, как использовать класс ArrayDeque Java, который является реализацией интерфейса Deque .
ArrayDeque (также известный как “Двойная очередь массива”, произносится как “Колода массивов”) – это особый вид растущего массива, который позволяет нам добавлять или удалять элемент с обеих сторон.
Реализация ArrayDeque может использоваться как Стек (Последний вход-Первый выход) или Очередь (Первый вход-Первый выход).
2. API с первого взгляда
Для каждой операции у нас в основном есть два варианта.
Первая группа состоит из методов, которые выдают исключение в случае сбоя операции. Другая группа возвращает статус или значение:
| Операция | Метод | Метод, выбрасывающий исключение |
| Вставка из головки | Предложение первое(e) | addFirst(e) |
| Снятие с головы | Опрос сначала() | removeFirst() |
| Извлечение из головы | Загляни сначала() | getFirst() |
| Вставка из хвоста | offerLast(e) | addLast(e) |
| Удаление из хвоста | опрос Последний() | removeLast() |
| Извлечение из хвоста | peekLast() | getLast() |
3. Использование Методов
Давайте рассмотрим несколько простых примеров того, как мы можем использовать ArrayDeque .
3.1. Использование ArrayDeque в качестве стека
Мы начнем с примера того, как мы можем рассматривать класс как Стек – и нажимать элемент:
@Test
public void whenPush_addsAtFirst() {
Deque stack = new ArrayDeque<>();
stack.push("first");
stack.push("second");
assertEquals("second", stack.getFirst());
}
Давайте также посмотрим, как мы можем извлечь элемент из ArrayDeque – при использовании в качестве стека:
@Test
public void whenPop_removesLast() {
Deque 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 queue = new ArrayDeque<>();
queue.offer("first");
queue.offer("second");
assertEquals("second", queue.getLast());
}
И давайте посмотрим , как мы можем опросить элемент из ArrayDeque , также при использовании в качестве Очереди :
@Test
public void whenPoll_removesFirst() {
Deque queue = new ArrayDeque<>();
queue.offer("first");
queue.offer("second");
assertEquals("first", queue.poll());
}
Метод poll возвращает значение null , если очередь пуста.
4. Как реализован ArrayDeque
Под капотом, в ArrayDeque поддерживается массивом, который удваивает свой размер при заполнении.
Первоначально массив инициализируется размером 16. Он реализован в виде двусторонней очереди, в которой он поддерживает два указателя, а именно голову и хвост.
Давайте посмотрим на эту логику в действии – на высоком уровне.
4.1. ArrayDeque как стек
Как видно, когда пользователь добавляет элемент с помощью метода push , он перемещает указатель головы на единицу.
Когда мы вставляем элемент, он устанавливает элемент в положение головы как null , чтобы элемент мог быть собран в мусор, а затем перемещает указатель головы на единицу назад.
4.2. ArrayDeque в виде очереди
Когда мы добавляем элемент с помощью метода offer , он перемещает указатель хвоста на единицу.
В то время как когда пользователь опрашивает элемент, он устанавливает для элемента в положении головы значение null, чтобы элемент можно было собирать мусор, а затем перемещает указатель головы.
4.3. Примечания по ArrayDeque
Наконец, еще несколько примечаний, которые стоит понять и запомнить об этой конкретной реализации:
- Это не потокобезопасно
- Нулевые элементы не принимаются
- Работает значительно быстрее, чем синхронизированный стек
- Является более быстрой очередью, чем Связанный список из-за лучшей локализации ссылки
- Большинство операций имеют амортизированную постоянную временную сложность
- Итератор , возвращаемый ArrayDeque , работает быстро
- ArrayDeque автоматически удваивает размер массива, когда указатель головы и хвоста встречаются друг с другом при добавлении элемента
5. Заключение
В этой короткой статье мы проиллюстрировали использование методов в ArrayDeque .
Реализацию всех этих примеров можно найти в проекте GitHub ; это проект на основе Maven, поэтому его должно быть легко импортировать и запускать как есть.