Queue и вариации на тему. Часть II. Имплементации в Java

При рассмотрении реализаций коллекций типа Queue предлагаю пройти от интерфейса Queue к реализациям, обращая внимание на то, на каком этапе добавляются конкретные методы – они, зачастую, хорошо соотносятся с изученными в прошлом уроке структурами данных. Также, в конце урока рассмотрим коллекцию, которая реализует и Queue, и List.

Интерфейс Queue

Для знакомства с методами данного интерфейса предлагаю обратиться к статье (пока лишь по пункт «Интерфейс Queue» включительно): https://metanit.com/java/tutorial/5.7.php

Кроме того, рекомендую обратить внимание еще на 2 вещи:

1. При многократном использовании методов peek() или element() подряд – каждый раз будет возвращаться один и тот же элемент – последний в очереди. Разумеется, кроме ситуаций, когда вызов метода приводит к исключению;
2. Кроме метода offer(), описанного в статье, в Queue явно определен и один из методов интерфейса-родителя – Collection – add(). Однако для добавления элемента в очередь рекомендуют использовать именно offer() – он, в общем случае, реже бросает исключения.

Также считаю важным напомнить, что очередь (как структура данных) декларирует лишь допустимое поведение, не описывая способ хранения элементов. Что и позволяет описывать ее как интерфейс, а не класс.

Интерфейс Deque

Еще один интерфейс, который является наследником Queue и описывает двусвязную очередь – с этой структурой данных мы тоже познакомились в рамках предыдущего урока.

Кроме того, интерфейс закладывает основу для реализации структуры данных «Стек», посредством декларации нескольких характерных для стека методов.

Снова обращаясь к статье на metanit (теперь уже к пункту «Интерфейс Deque»), разберем методы, объявленные в Deque: https://metanit.com/java/tutorial/5.7.php

Обратите внимание, что использование методов Queue у наследника Deque также допустимо – поведение будет реализовываться с учетом принципа FIFO: poll(), element() и peek() будут работать с элементом, стоящим первым в деке, add() и offer() – добавлять элементы после последнего.

Кроме того, метод Collection addAll() в рамках наследников Deque будет работать как множественное добавление в хвост очереди. Т.е., по сути, закрепляя поведение, равноценное работе этого метода в Queue.

Класс PriorityQueue

Особенностью коллекций типа Queue является то, что прямой (по крайней мере, с точки зрения иерархии интерфейсов) публичный наследник в java.util только один – PriorityQueue. Насколько односвязные очереди популярны в разработке многопоточных решений, настолько же они непопулярны за их пределами. Если откроете иерархию наследников Queue, то увидите, что большинство из них находится в пакете java.util.concurrent – пакете, содержащем классы для работы с многопоточностью. Связано это, во многом, с неудобством работы с очередью, за исключением ряда узких задач. При равном, в плане затрат на реализацию структуры, очереди дэке, последний является куда более дружелюбным в использовании.

Вторым ироничным моментом является то, что PriorityQueue – не совсем каноничная очередь. Она хранит элементы отсортированном виде: либо в соответствии с реализацией compareTo(), если коллекция параметризована типом, реализующим Comparable, либо на основании переданного в параметры конструктора Comparator’а. Таким образом, принцип FIFO не соблюдается в этой реализации.

Таким образом, первым элементом в PriorityQueue всегда будет наименьший из всех (в соответствии с определенным правилом сравнения), а последним – наибольший.

Из других нюансов реализации могу отметить лишь то, что хранение элементов PriorityQueue реализовано через массив.

Не могу сказать, что данная коллекция имеет большую популярность, но именно она, на мой взгляд, является единственно допустимым для новичков примером реализации Queue (именно Queue, а не ее потомков, наследующих Deque).

Класс ArrayDeque

В свою очередь, классической реализацией Deque является класс ArrayDeque. С точки зрения реализации (в том, что связано с хранением элементов), он напоминает ArrayList – тот же массив для хранения элементов, тот же метод grow() для увеличения размеров массива. Даже классические для дека (и двусвязного списка вообще) точки входа в структуру – первый и последний узлы – на уровне полей класса представлены не узлами, а индексами массива. Это не влияет на работу с классом, но позволяет немного глубже понять нюансы его реализации.

Более подробно предлагаю познакомиться с ArrayDeque на базе все той же статьи на metanit (пункт «Класс ArrayDeque»): https://metanit.com/java/tutorial/5.7.php

Обратите внимание, что доступные конструкторы, по сути, аналогичны конструкторам в ArrayList.

Ласковое телятко двух маток сосёт. LinkedList

В одном из прошлых уроков уроков я обещал уделить внимание данному классу. Его достаточно часто любят вспоминать на собеседованиях и просят сравнить его с ArrayList’ом.

Связано это с тем, что LinkedList – вторая по известности реализация List’а. Но, по иронии судьбы, этот класс реализует и интерфейс Deque. В конечном итоге, LinkedList является классической реализацией двусвязного списка, знакомого вам из практики предыдущего урока.

В целом, данный класс является именно тем, чем кажется – структурой, предоставляющей методы для работы с собой как с List’ом, так и с Deque’ом.

Плохая новость состоит в том, что эти два подхода не стоит смешивать – есть шанс запутаться и написать код, в котором каждое второе обращение к этому классу будет приводить к исключению или неожиданному результату.

Хорошая же заключается в том, что даже если вам и придется работать с LinkedList’ом, скорее всего его объект будет присвоен переменной типа List или (менее вероятно) типа Deque. И шанса использовать методы коллекций разных типов у вас не будет.

Данному классу посвящена отдельная статья на metanit, но мне она кажется крайне неудачной (пометка для тех, кто обращается к этому сайту не только в рамках моих уроков).

В целом, я рекомендую большее внимание уделить не самому LinkedList, а его сравнению с ArrayList. Эта история глубже, чем может показаться на первый взгляд (вплоть до того, что на одни и те же вопросы относительно сравнения этих классов, от джуниора и от сеньора будут ожидать разных по смыслу ответов). На данном этапе не стоит переживать, просто будьте готовы, что тема может быть поводом для холивара.

В качестве лаконичных заметок, освещающих разницу, преимущества и недостатки ArrayList и LinkedList рекомендую первые два ответа в этом вопросе: https://ru.stackoverflow.com/questions/568119/%D0%9E%D1%82%D0%BB%D0%B8%D1%87%D0%B8%D0%B5-arraylist-%D0%BE%D1%82-linkedlist

Примерно тоже самое, но в более свободной форме (будет полезно, если вы даже минимально не знакомы с О-нотацией): https://javarush.com/quests/lectures/questsyntax.level08.lecture05

Другие реализации Queue и Deque

В рамках предыдущий уроков я предлагал классификацию коллекций по потокобезопасности. Предлагаю не изменять традиции и привести примеры коллекций и для свежеизученных типов.

Queue:

• Непотокобезопасная коллекция: PriorityQueue;
• Потокобезопасная (Legacy): отсутствует;
• Потокобезопасная (java.util.concurrent): ConcurrentLinkedQueue;

Deque:

• Непотокобезопасная коллекция: ArrayDeque;
• Потокобезопасная (Legacy): иерархически отсутствует. Если рассматривать Deque как идеологического предка стека – Stack (наследник Vector);
• Потокобезопасная (java.util.concurrent): LinkedBlockingDeque, ConcurrentLinkedDeque

В качестве итога

Queue – самый непонятный на ранних этапах тип коллекций. В первую очередь, потому что непонятна его сфера применения. По сути, в этом нет ничего страшного, очереди нужны в достаточно узких случаях. И большинство этих случаев очень тяжело представить до знакомства с многопоточностью. Поэтому с точки зрения пользы данной статьи при прохождении собеседований советую сконцентрироваться на иерархии, а также уделить минимальное внимание основным методам (характерным только для Queue/Deque). Но обязательно разобрать сравнительный анализ ArrayList и LinkedList.

Этого будет достаточно, при условии, что вы понимаете устройство структур данных вне контекста Collections Framework (по сути, содержание предыдущего урока). По крайней мере, за пределами многопоточной разработки.

С теорией на сегодня все!

Переходим к практике:

Задача:

Реализуйте класс Задание. Он должен содержать поле Название, состав остальных полей - на ваше усмотрение.

Реализуйте сервис, хранящий задания. Он должен иметь методы для добавления заданий и их "выполнения". Задания должны обрабатываться в порядке очереди. Критерием выполнения задания будем считать выведение в консоль фразы "Задание %название задания% выполнено!".

Также добавьте вывод сообщения в консоль о том, что задание (с указанием названия) добавлено.

Если что-то непонятно или не получается – welcome в комменты к посту или в лс:)

Канал: https://t.me/+relA0-qlUYAxZjI6

Мой тг: https://t.me/ironicMotherfucker

Дорогу осилит идущий!