Коллекции Java: интерфейсы очередей и дек

Введение Java Collections Framework - это фундаментальная и важная среда, которую любой сильный Java-разработчик должен знать как свои пять пальцев. Коллекция в Java определяется как группа или набор отдельных объектов, которые действуют как единый объект. В Java существует множество классов коллекций, и все они расширяют интерфейсы java.util.Collection и java.util.Map. Эти классы в основном предлагают разные способы составить коллекцию объектов в рамках одного. Java Co

Вступление

Java Collections Framework - это фундаментальная и важная среда, которую любой сильный Java-разработчик должен знать как свои пять пальцев.

Коллекция в Java определяется как группа или набор отдельных объектов, которые действуют как единый объект.

В Java существует множество классов коллекций, и все они расширяют интерфейсы java.util.Collection и java.util.Map Эти классы в основном предлагают разные способы составить коллекцию объектов в рамках одного.

Коллекции Java - это среда, которая обеспечивает множество операций над коллекцией - поиск, сортировку, вставку, манипулирование, удаление и т. Д.

Это четвертая и последняя часть серии статей о Коллекциях Java :

Очередь

Давайте начнем эту заключительную статью серии с интерфейса java.util.Queue

Принцип

Во-первых, для чего это нужно? Queue предназначена для хранения элементов до их обработки . Некоторые из них могут иметь фиксированную емкость, что означает, что они могут содержать только определенное количество элементов.

Итак, идея состоит в том, чтобы поместить некоторые элементы в Queue , а затем получить их после этого. Как правило, очереди возвращают элементы в соответствии с шаблоном First-In First-Out (FIFO) , то есть сначала возвращается самый старый элемент очереди, затем самый старый и т. Д.

Вы можете думать о FIFO как о очереди перед магазином. Первый в очереди встает и входит первым.

Но могут быть и другие реализации, которые соблюдают шаблон Last-In First-Out (LIFO) , или даже отвечают какой-то системе приоритетов (например, с использованием Comparator ).

Вы можете думать о LIFO как о стопке монет. Последний, который кладут на вершину стопки, снимают первым.

Давайте теперь исследуем особенности интерфейса Queue

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

Начнем с добавления элемента в Queue . Во- первых, давайте Instantiate один с помощью ArrayDeque реализации, который также реализует Deque интерфейс мы рассмотрим позже:

 Queue<Integer> queue = new ArrayDeque<>();

Чтобы добавить элемент в эту Queue , у нас есть две возможности: метод add() или метод offer() .

Начнем с первого:

 queue.add(3);

А с последним:

 queue.offer(4);

Оба возвращают boolean значение, указывающее, был ли элемент добавлен в Queue или нет, в зависимости от его емкости (если это применимо). В чем же тогда разница между обоими методами?

Что ж, первый на самом деле никогда не вернет false , а скорее выбрасывает Exception при добавлении элемента в полную Queue . С другой стороны, второй в таких случаях false

Вместо ArrayDeque , который не ограничен, давайте использовать LinkedBlockingQueue которому можно назначить емкость:

 Queue<Integer> queue = new LinkedBlockingQueue<>(1);

Здесь мы создали очередь, которая может одновременно содержать не более одного элемента. Следовательно, мы не можем использовать метод add() два раза подряд без исключения:

 queue.add(3); 
 queue.add(4);

Попытка добавить эти два элемента приведет к:

 java.lang.IllegalStateException: Queue full 
 at java.base/java.util.AbstractQueue.add(AbstractQueue.java:98)

С другой стороны, использование offer() ничего не даст и в результате false

Получение элемента

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

Интерфейс предлагает несколько методов для получения элементов. Два из них, remove() и poll() , удаляют элемент перед его возвратом. Два других element() и peek() просто возвращают его, но не удаляют.

remove() и element() вызовут исключение при вызове в пустой Queue :

 Queue<Integer> queue = new ArrayDeque<>(); 
 queue.offer(3); 
 queue.offer(4); 
 
 queue.poll(); 
 queue.peek();

Здесь мы соберем элементы 3 и 4 , но в первый раз элемент будет удален (через poll() ), а во второй раз нет (через peek() ), оставив нашу очередь с элементом 4 в нем.

Использование remove() и element() вместо poll() и peek() соответственно дало бы те же результаты, поскольку в нашем случае очередь никогда не бывает пустой.

Итерация по элементам

Помимо индексированных циклов while и for , интерфейс Queue Iterable и предоставляет Iterator , что делает его подходящим для цикла for-each :

 for (Integer element: queue) { 
 System.out.println(element); 
 }

Этот цикл выводит на консоль каждый элемент очереди.

Начиная с Java 8, конечно, есть возможность вызвать метод forEach() , передав ссылку на метод :

 queue.forEach(System.out::println);

Это дает тот же результат, что и в предыдущем цикле.

Если вы хотите узнать больше об итерируемом интерфейсе в Java , мы вам поможем!

Реализации

Теперь, какие классы реализуют интерфейс Queue Существует несколько реализаций интерфейса, но на самом деле они наиболее актуальны:

  • LinkedList : Хотя этот класс в основном известен как List , он также реализует интерфейс Queue Эта реализация работает, связывая свои элементы вместе и проходя эту цепочку при итерации или поиске элементов.
  • ArrayDeque : реализация как Queue и Deque . Он поддерживается массивом, который может быть увеличен, когда количество элементов превышает его текущую емкость.
  • DelayQueue : может содержать только элементы, реализующие Delayed - элементы, которые становятся активными через определенное время. DelayQueue будет доставлять только те элементы, чьи задержки истекли.
  • PriorityQueue : упорядочивает элементы в соответствии с их естественным порядком или Comparator (если предоставляется). Это означает, что он не работает с использованием принципа FIFO, а скорее возвращает элемент с наивысшим приоритетом (определяемый тем, как они сравниваются друг с другом).

Представим себе систему аномалий с enum определяющим их серьезность:

 public class Anomaly implements Comparable<Anomaly> { 
 private String log; 
 private Severity severity; 
 
 public Anomaly(String log, Severity severity) { 
 this.log = log; 
 this.severity = severity; 
 } 
 
 @Override 
 public int compareTo(Anomaly o) { 
 return severity.compareTo(o.severity); 
 } 
 
 private enum Severity { 
 HIGH, 
 MEDIUM, 
 LOW 
 } 
 }

Здесь аномалии естественным образом упорядочены по степени серьезности (поскольку enum естественным образом упорядочены по порядку их объявления).

Итак, если бы мы добавили две аномалии в PriorityQueue без Comparator , одну LOW и одну HIGH , тогда метод poll() сначала вернул бы вторую аномалию, а затем первую:

 Queue<Anomaly> anomalies = new PriorityQueue<>(); 
 
 Anomaly optionalInformationNotRetrievedAnomaly = new Anomaly("Couldn't retrieve optional information", Anomaly.Severity.LOW); 
 anomalies.offer(optionalInformationNotRetrievedAnomaly); 
 
 Anomaly databaseNotReachableAnomaly = new Anomaly("Couldn't contact database", Anomaly.Severity.HIGH); 
 anomalies.offer(databaseNotReachableAnomaly); 
 
 anomalies.poll(); // This would return 'databaseNotReachableAnomaly'

Теперь, если мы передадим Comparator PriorityQueue , скажем, тот, который меняет естественный порядок на противоположный:

 Queue<Anomaly> anomalies = new PriorityQueue<>(Comparator.reverseOrder());

Затем в том же сценарии, что и раньше, метод poll() вернет первую аномалию - это optionalInformationNotRetrievedAnomaly .

Deque

Теперь, когда мы рассмотрели Queue , перейдем к Deque .

Принцип

Deque означает Double Ended Queue , что означает, что это очередь, к которой могут получить доступ оба конца, и поэтому ее можно использовать как со стилями FIFO, так и LIFO. По умолчанию он организует свой элемент в стиле LIFO, что означает, что получение первого в Deque вернет последний добавленный.

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

Перейдем к Deque со вставкой элементов. Для этого есть несколько возможностей:

  • Некоторые методы добавляют элемент вверху, некоторые - внизу
  • Некоторые методы выдают исключение, если Deque заполнена, некоторые - нет.

Сведем их в таблицу:

               Вершина                   Нижний

Без исключения offerFirst() offer() , offerLast() Исключение addFirst() , push() add() , addLast()

Допустим, у нас есть Deque of Integer и мы вызываем addFirst() с целыми числами 3 и 4 :

 Deque<Integer> deque = new ArrayDeque<>(); 
 deque.addFirst(3); 
 deque.addFirst(4);

Затем двухсторонняя очередь будет содержать 4 и 3 в указанном порядке.

Если бы мы использовали addLast() , то он содержал бы 3 и 4 в этом порядке. То же самое произошло бы с offerFirst() и offerLast() соответственно.

Получение и удаление элемента

Теперь давайте посмотрим, как получить элементы из Deque . Опять же, есть несколько возможностей:

  • Некоторые методы возвращают первый элемент, некоторые - последний.
  • Некоторые методы удаляют элемент при возврате, некоторые нет.
  • Некоторые методы вызывают исключение, если Deque пуста, некоторые - нет.

Чтобы упростить задачу, мы также обобщим это в таблице:

               Первый (верхний) элемент, без удаления   Первый (верхний) элемент, удаление

Без исключения peek() , peekFirst() poll() , pollFirst() Исключение getFirst() , element() remove() , removeFirst() , pop()

               Последний (нижний) элемент, без удаления   Последний (нижний) элемент, удаление

Без исключения peekLast() pollLast() Исключение getLast() removeLast()

Допустим, у нас есть Deque of Integer с элементами 4 и 3 сверху вниз. И мы вызываем peekFirst() :

 Deque<Integer> deque = new ArrayDeque<>(); 
 deque.push(3); 
 deque.push(4); 
 
 deque.peekFirst();

Тогда это вернет 4 без удаления элемента. Если бы мы использовали peekLast() , то вернули бы 3 .

Теперь, если бы мы использовали removeFirst() или pop() , мы получили бы 4 но в конце Deque содержал бы только 3

Итерация по элементам

Что касается Queue , мы можем выполнять итерацию, используя стандартные механизмы и метод forEach() . Нам просто нужно помнить, что по умолчанию Deque организует свои элементы в стиле LIFO и, следовательно, будет перебирать их сверху вниз:

 Deque<Integer> deque = new ArrayDeque<>(); 
 deque.push(3); 
 deque.push(4); 
 
 deque.forEach(System.out::println);

Это напечатает:

 4 
 3

Вы также можете использовать Iterator :

 Deque<Integer> deque = new ArrayDeque<>(); 
 deque.push(3); 
 deque.push(4); 
 
 for (Iterator<Integer> iterator = deque.iterator(); iterator.hasNext();) { 
 System.out.println(iterator.next()); 
 }

Это также напечатает:

 4 
 3

Реализации

  • ArrayDeque : это тот, который мы использовали для Queue и который поддерживается array . Реализует как Queue и Deque .
  • LinkedList : реализует как Queue , Deque и List . Мы также видели это раньше.
  • LinkedBlockingDeque : он немного похож на LinkedList , но может быть ограничен. Таким образом, операции вставки, которые мы видели ранее, вызовут исключение, если эта Deque будет заполнена.

Куча?

Стоит отметить, что Stack тоже существует. Он был представлен в начале Java и должен был использоваться как коллекция LIFO с методами push() и pop()

Почему бы тогда не использовать это?

Потому что документация советует нам использовать Deque который предлагает более согласованный API. Кроме того, Stack является подклассом Vector и поэтому тесно связан с ним, что делает его List , который концептуально отличается от стека.

Заключение

Java Collections Framework - это фундаментальная структура, которую каждый Java-разработчик должен знать, как использовать.

В этой статье мы поговорили об Queue и Deque и рассмотрели их основные операции. Полный код этой статьи можно найти на GitHub .

java
Licensed under CC BY-NC-SA 4.0
comments powered by Disqus

Содержание