Java ArrayDeque с примерами

От /

В этом руководстве Java будет обсуждаться класс ArrayDeque и его основные функции с практическими примерами. Мы также увидим различные методы, представленные в этом классе, и то, как мы можем использовать их либо как стек, либо как очередь в нашем коде.

1. Введение в ArrayDeque

Очередь — это линейная структура данных, которая хранит элементы в порядке FIFO(First In, First Out). У каждой очереди есть два конца: передний и задний. Новые элементы добавляются в конец и удаляются из начала очереди. Несколько подинтерфейсов(например, TransferQueue, BlockingQueue и т. д.) и классов реализации(например, LinkedList, PriorityQueue и т. д.) используют интерфейс очереди внутренне.

Deque — это двухсторонняя очередь, которая позволяет добавлять или удалять элементы с обоих концов очереди. Она может использоваться как очередь, которая следует порядку FIFO(первым пришел, первым вышел); или как стек, который следует порядку LIFO(последним пришел, первым вышел).

ArrayDeque — это класс реализации интерфейса Deque в Java; следовательно, ArrayDeque — это особый вид растущего массива, который позволяет нам добавлять или удалять элемент с обеих сторон. Он также известен как «Array Double Ended Queue» или ArrayDeck. 

public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>
Java ArrayDeque с примерами0

1.1.Конструкторы

Мы можем создать объект ArrayDeque, используя следующие два конструктора:

  • ArrayDeque(): используется для создания пустого ArrayDeque с начальной емкостью по умолчанию 16.
  • ArrayDeque(Collection): используется для создания ArrayDeque, все элементы которого совпадают с элементами указанной коллекции.
  • ArrayDeque(int numofElements): используется для создания пустого ArrayDeque с указанным начальным значением емкости. 
Deque<String> deque = new ArrayDeque<String>();Deque<String> deque = new ArrayDeque<String>(10);Deque<String> deque = new ArrayDeque<>(Arrays.asList(new String("abc")));

1.2.Особенности

Давайте рассмотрим некоторые основные возможности ArrayDeque:

  • Мы не можем вставлять в него элементы Null, в противном случае будет выдан NullPointerException.
  • Он не является потокобезопасным и не поддерживает одновременный доступ нескольких потоков.
  • Он использует два указателя, называемые head и tail. Head отвечает за вставку и удаление с начала, а tail — за вставку и удаление с конца.
  • Он быстрее, чем LinkedList и Stack.
  • Он не имеет ограничений по мощности и расширяется по мере необходимости.
  • Возвращаемый им итератор устойчив к сбоям и может выдать исключение ConcurrentModificationException в случае изменения коллекции во время итерации.

2. Работа с ArrayDeque

Класс ArrayDeque предоставляет реализации для всех методов, присутствующих в интерфейсах Queue и Deque.

2.1 Добавление элементов

Следующие методы предлагают добавлять новые элементы в массив.

  • add(): вставляет указанный элемент в конец массива deque; если deque заполнен, этот метод выдает исключение IllegalStateException.
  • addFirst(): вставляет указанный элемент в начало очереди массива; если очередь заполнена, этот метод выдает исключение IllegalStateException.
  • addLast(): вставляет указанный элемент в конец очереди массива, если очередь заполнена; этот метод выдает исключение IllegalStateException.
  • offer(): вставляет указанный элемент в конец массива deque
  • offerFirst(): вставляет указанный элемент в начало массива deque
  • offerLast(): вставляет указанный элемент в конец массива deque 
ArrayDeque<String> languages = new ArrayDeque<>();languages.add(“English”);languages.addFirst(“Hindi”);languages.addLast(“French”);System.out.println("ArrayDeque: " + languages); // [Hindi, English, French]

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

  • remove(): возвращает и удаляет первый элемент массива deque; если deque пуст, этот метод выдает исключение NoSuchElementException.
  • removeFirst(): возвращает и удаляет первый элемент из массива deque(эквивалент remove()), если deque пуст, этот метод выдает исключение NoSuchElementException.
  • removeLast(): возвращает и удаляет последний элемент из массива deque; если deque пуст, этот метод выдает исключение NoSuchElementException.
  • poll(): возвращает и удаляет первый элемент массива deque
  • pollFirst(): возвращает и удаляет первый элемент массива deque(эквивалент poll())
  • pollLast(): возвращает и удаляет последний элемент массива deque 
ArrayDeque<String> languages = new ArrayDeque<>();languages.add("English");languages.add("Hindi");languages.add("French");languages.add("German");System.out.println("ArrayDeque: " + languages); // [English, Hindi, French, German]String element = languages.remove(); // EnglishSystem.out.println("New ArrayDeque: " + languages); // [Hindi, French, German]String firstElement = languages.removeFirst(); // HindiString lastElement = languages.removeLast(); // German// Reinitialize arraydeque againString element = languages.poll(); // EnglishSystem.out.println("New ArrayDeque: " + languages); // [Hindi, French, German]String firstElement = languages.pollFirst(); // HindiString lastElement = languages.pollLast(); // German

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

  • getFirst(): возвращает первый элемент массива deque; если deque пуст, этот метод выдает исключение NoSuchElementException.
  • getLast(): возвращает последний элемент массива deque; если deque пуст, этот метод выдает исключение NoSuchElementException.
  • peek(): возвращает первый элемент массива deque
  • peekFirst(): возвращает первый элемент массива deque(эквивалент peek())
  • peekLast(): возвращает последний элемент массива deque 
String firstElement = languages.getFirst(); // EnglishString lastElement = languages.getLast(); // GermanString element = languages.peek(); // EnglishString firstElement = languages.peekFirst(); // EnglishString lastElement = languages.peekLast(); // German

Обратите внимание, что есть два метода, которые могут выполнять одну и ту же операцию с ArrayDeque. Например, мы можем удалить последний элемент из ArrayDeque, используя метод removeLast() или метод pollLast(). Разница между этими методами в том, что один возвращает исключение, если ArrayDeque пуст, а другой возвращает значение null.

Методы, которые возвращают исключение в случае, если ArrayDeque заполнен или пуст: addFirst(), addLast(), removeFirst(), removeLast(), getFirst() и getLast(). 

ArrayDeque<String> queue = new ArrayDeque<>();System.out.println(queue.removeLast()); // Exception in thread "main" java.util.NoSuchElementExceptionSystem.out.println(queue.pollLast()); // null

3. ArrayDeque как стек

Стек может быть реализован с помощью ArrayDeque. Мы выберем один конец Deque(передний или задний) для вставки и удаления элементов только с этого конца. Мы можем использовать методы ArrayDeque для вставки и удаления или методы push() и pop() класса Stack.

Для реализации LIFO(Last-In-First-Out) рекомендуется использовать Deque вместо класса Stack. Класс ArrayDeque, скорее всего, будет быстрее, чем класс Stack. 

// Creating ArrayDeque that acts as StackDeque<Integer> stack = new ArrayDeque<Integer>();// Pushing elements to Stackstack.push(15);stack.push(10);stack.push(5);System.out.println("Stack after insertion: " + stack); // [5, 10, 15]// Removing & Returning Stack elementsstack.pop();System.out.println("Stack after deletion: " + stack); // [10, 15]stack.pop();System.out.println("Stack after deletion: " + stack); // [15]

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

Мы можем реализовать Queue с помощью ArrayDeque, вставляя элементы на одном конце и удаляя их с другого. Мы можем либо использовать методы ArrayDeque для вставки и удаления, либо использовать методы add() и remove() класса Queue. Очередь, реализованная с его помощью, следует тому же принципу FIFO(First-In-First-Out). 

// Creating ArrayDeque that acts as QueueDeque<Integer> queue = new ArrayDeque<Integer>();// Adding elements to Queuequeue.add(15);queue.add(10);queue.add(5);System.out.println("Queue after insertion: " + queue); // [15, 10, 5]// Removing & Returning Queue elementsqueue.remove();System.out.println("Queue after deletion: " + queue); // [10, 5]queue. remove();System.out.println("Queue after deletion: " + queue); // [5]

5. Разница между ArrayDeque и LinkedList

ArrayDeque и LinkedList реализуют интерфейс Deque. Однако между ними существуют некоторые различия; давайте рассмотрим эти различия.

  • LinkedList поддерживает нулевые элементы, тогда как ArrayDeque — нет.
  • LinkedList требует больше памяти, чем ArrayDeque, поскольку каждый узел в LinkedList включает ссылки на другие узлы.
  • С точки зрения производительности ArrayDeque, скорее всего, будет быстрее, чем LinkedList.

6. Когда использовать?

ArrayDeque реализуется как стек и очередь, поэтому мы можем использовать его в таких приложениях, как ведение истории веб-браузера, ведение списка отмененных операций в приложении, в алгоритмах планирования заданий и т. д.

Проблемы, когда элементы необходимо удалить и/или добавить на оба конца, могут быть эффективно решены с его помощью. Кроме того, он предпочитает использовать ArrayDeque вместо Stack и LinkedList из-за его более высокой производительности.

Одним из примеров, где мы можем использовать Deque, является алгоритм планирования заданий A-Steal. Этот алгоритм реализует планирование задач для нескольких процессоров. Отдельная deque с потоками поддерживается для каждого процессора.

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

Мы узнали об ArrayDeque, его основных функциях, его основных методах и практических примерах. Мы также увидели, как он был реализован как Stack и как Queue. Также рассмотрели некоторые из основных различий между ArrayDeque и LinkedList и их практические варианты использования.

Похожие посты

Прокрутить вверх