Коллекции: очередь и стек

Содержание

1. Очередь
2. Стек
3. Дек
4. Выводы

Ранее мы рассматривали наиболее популярные Коллекции: list, set, map. В данной статье рассмотрим чуть более специфичные коллекции. Все рассмотренные ниже коллекции реализуют один из двух алгоритмов манипулирования данными: «First In – First Out» (FIFO) и «Last In – First Out» (LIFO).

Очередь

Очередь реализует принцип «first in – first out», т.е. «первым пришёл – первым ушёл». Базовым интерфейсом всех очередей Java является Queue. Добавление элементов в очередь делается методом add(), удаление – poll(), получение первого элемента без его удаления – peek().

Две самые простые реализации очереди – это LinkedList и PriorityQueue. Рассмотрим их на примере.

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

Обратите внимание, что LinkedList также реализует интерфейс List, который мы рассматривали в предыдущей статье.

Теперь проделаем то же самое с очередью PriorityQueue.

На экране увидим следующее:

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

Стек

Стек реализует принцип «last in – first out», т.е. «последним пришёл – первым вышел». Аналогия из реального мира – это стопка книг на столе (сначала берём верхнюю). В Java есть одноимённый класс Stack. Добавление элементов осуществляется методом push(), а удаление методом pop(). Рассмотрим пример:

Тогда на экране увидим:

То есть элементы извлекаются в обратном порядке, начиная с последнего. Класс Stack является расширением класса Vector. Оба этих класса появились ещё в Java 1.0. Ныне они считаются устаревшими и их не рекомендуется применять в новых проектах.

Дек

Интерфейс Deque позиционируется как современная альтернатива классу Stack. Deque – это сокращение от «double ended queue» (двусторонняя очередь). Технически Deque является расширением интерфейса очереди Queue.

Интерфейс Deque реализуют всё тот же LinkedList, а также ArrayDeque.

Пример работы с деком в качестве стека:

Результат:

Выводы

На основании рассмотренных нами интерфейсов и реализаций можно сделать вывод, что для самой простой реализации очереди Queue следует выбрать LinkedList. Если требуется как-то сортировать элементы внутри очереди, то подойдёт PriorityQueue. Если же нам нужна функциональность стека, то надо использовать интерфейс Deque и одну из его реализаций: LinkedList или ArrayDeque.

См. также

• Интерфейсы Comparable и Comparator
• SequencedCollection и SequencedSet
• Коллекции: list, set, map
• Алгоритм поиска суммы двух элементов в массиве
• Перебор элементов через Iterator
• SequencedMap
• Работа с коллекциями