Освоение Java ArrayDeque: полное руководство и реализация стека

Java ArrayDeque

Это руководство объясняет класс ArrayDeque, его методы и практические примеры — включая использование в качестве стека.

В Java ArrayDeque реализует структуры данных очередь и дек, основанные на изменяемом массиве.

---

Интерфейсы, реализуемые ArrayDeque

Класс ArrayDeque реализует следующие интерфейсы:

• Java Queue Interface
• Java Deque Interface

---

Создание ArrayDeque

Сначала импортируйте пакет:

import java.util.ArrayDeque;

Создайте типизированный дек:

ArrayDeque<Type> deque = new ArrayDeque<>();

Примеры:

// Дек строк
ArrayDeque<String> animals = new ArrayDeque<>();
// Дек целых чисел
ArrayDeque<Integer> ages = new ArrayDeque<>();

---

Ключевые методы ArrayDeque

Вставка элементов

1. Использование add(), addFirst(), addLast()

• add(E e) — добавляет e в хвост.
• addFirst(E e) — вставляет e в голову.
• addLast(E e) — эквивалентно add().

Примечание: Если дек полон, эти методы выбрасывают IllegalStateException.

ArrayDeque<String> animals = new ArrayDeque<>();
animals.add("Dog");
animals.addFirst("Cat");
animals.addLast("Horse");
System.out.println("ArrayDeque: " + animals);

Вывод

ArrayDeque: [Cat, Dog, Horse]

2. Использование offer(), offerFirst(), offerLast()

• offer(E e) — добавляет e в хвост, возвращая true при успехе.
• offerFirst(E e) — вставляет e в голову.
• offerLast(E e) — то же, что offer().

Примечание: Эти методы возвращают false, если дек полон.

ArrayDeque<String> animals = new ArrayDeque<>();
animals.offer("Dog");
animals.offerFirst("Cat");
animals.offerLast("Horse");
System.out.println("ArrayDeque: " + animals);

Вывод

ArrayDeque: [Cat, Dog, Horse]

Доступ к элементам

1. getFirst() и getLast()

• getFirst() — возвращает элемент головы.
• getLast() — возвращает элемент хвоста.

Примечание: Выбрасывает NoSuchElementException, если дек пуст.

ArrayDeque<String> animals = new ArrayDeque<>();
animals.add("Dog");
animals.add("Cat");
animals.add("Horse");
System.out.println("ArrayDeque: " + animals);
System.out.println("First Element: " + animals.getFirst());
System.out.println("Last Element: " + animals.getLast());

Вывод

ArrayDeque: [Dog, Cat, Horse] First Element: Dog Last Element: Horse

2. peek(), peekFirst(), peekLast()

• peek() — получает, но не удаляет голову.
• peekFirst() — синоним для peek().
• peekLast() — получает хвост.

ArrayDeque<String> animals = new ArrayDeque<>();
animals.add("Dog");
animals.add("Cat");
animals.add("Horse");
System.out.println("ArrayDeque: " + animals);
System.out.println("Head Element: " + animals.peek());
System.out.println("First Element: " + animals.peekFirst());
System.out.println("Last Element: " + animals.peekLast());

Вывод

ArrayDeque: [Dog, Cat, Horse] Head Element: Dog First Element: Dog Last Element: Horse

Примечание: Если дек пуст, peek() и друзья возвращают null вместо выбрасывания исключения.

Удаление элементов

1. remove(), removeFirst(), removeLast()

• remove() — удаляет и возвращает голову.
• removeFirst() — то же, что remove().
• removeLast() — удаляет и возвращает хвост.
• remove(Object o) — удаляет первое вхождение o, если присутствует.

Примечание: Выбрасывает NoSuchElementException, если дек пуст или если remove(o) не находит o.

ArrayDeque<String> animals = new ArrayDeque<>();
animals.add("Dog");
animals.add("Cat");
animals.add("Cow");
animals.add("Horse");
System.out.println("ArrayDeque: " + animals);
System.out.println("Removed Element: " + animals.remove());
System.out.println("New ArrayDeque: " + animals);
System.out.println("Removed First Element: " + animals.removeFirst());
System.out.println("Removed Last Element: " + animals.removeLast());

Вывод

ArrayDeque: [Dog, Cat, Cow, Horse] Removed Element: Dog New ArrayDeque: [Cat, Cow, Horse] Removed First Element: Cat Removed Last Element: Horse

2. poll(), pollFirst(), pollLast()

• poll() — удаляет и возвращает голову, или null, если пуст.
• pollFirst() — синоним для poll().
• pollLast() — удаляет и возвращает хвост.

ArrayDeque<String> animals = new ArrayDeque<>();
animals.add("Dog");
animals.add("Cat");
animals.add("Cow");
animals.add("Horse");
System.out.println("ArrayDeque: " + animals);
System.out.println("Removed Element: " + animals.poll());
System.out.println("New ArrayDeque: " + animals);
System.out.println("Removed First Element: " + animals.pollFirst());
System.out.println("Removed Last Element: " + animals.pollLast());

Вывод

ArrayDeque: [Dog, Cat, Cow, Horse] Removed Element: Dog New ArrayDeque: [Cat, Cow, Horse] Removed First Element: Cat Removed Last Element: Horse

3. clear()

Очищает весь дек.

ArrayDeque<String> animals = new ArrayDeque<>();
animals.add("Dog");
animals.add("Cat");
animals.add("Horse");
System.out.println("ArrayDeque: " + animals);
animals.clear();
System.out.println("New ArrayDeque: " + animals);

Вывод

ArrayDeque: [Dog, Cat, Horse] New ArrayDeque: []

Итерация по ArrayDeque

• iterator() — прямой итератор.
• descendingIterator() — обратный итератор.

ArrayDeque<String> animals = new ArrayDeque<>();
animals.add("Dog");
animals.add("Cat");
animals.add("Horse");
System.out.print("ArrayDeque: ");
Iterator<String> it = animals.iterator();
while(it.hasNext()) {
    System.out.print(it.next() + ", ");
}
System.out.print("\nArrayDeque in reverse order: ");
Iterator<String> rev = animals.descendingIterator();
while(rev.hasNext()) {
    System.out.print(rev.next() + ", ");
}

Вывод

ArrayDeque: [Dog, Cat, Horse] ArrayDeque in reverse order: [Horse, Cat, Dog]

Другие распространённые методы

Метод	Описание
element()	Получает, но не удаляет голову.
contains(Object o)	Проверяет наличие o; возвращает true, если найдено.
size()	Количество элементов в деке.
toArray()	Преобразует дек в массив.
clone()	Создаёт поверхностную копию дека.

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

Для поведения LIFO ArrayDeque предпочтительнее Stack из-за лучшей производительности и отсутствия накладных расходов устаревшей синхронизации.

Методы в стиле стека:

• push(E e) — добавляет в голову.
• peek() — получает верхний элемент без удаления.
• pop() — удаляет и возвращает верхний элемент.

ArrayDeque<String> stack = new ArrayDeque<>();
stack.push("Dog");
stack.push("Cat");
stack.push("Horse");
System.out.println("Stack: " + stack);
System.out.println("Accessed Element: " + stack.peek());
System.out.println("Removed Element: " + stack.pop());

Вывод

Stack: [Horse, Cat, Dog] Accessed Element: Horse Removed Element: Horse

ArrayDeque против LinkedList

Оба реализуют Deque, но различаются:

• LinkedList позволяет null элементы; ArrayDeque — нет.
• Узлы LinkedList хранят указатели, потребляя больше памяти.
• Для нагрузок очереди/дека ArrayDeque обычно превосходит LinkedList.