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

Вернуться назад

16 апреля 2019

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

Очередь

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

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

Queue<String> queue = new LinkedList<>();
queue.add("банан");
queue.add("яблоко");
queue.add("ананас");
while (queue.peek() != null) { // или !queue.isEmpty()
    System.out.println(queue.poll());
}

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

банан
яблоко
ананас

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

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

Queue<String> queue = new PriorityQueue<>();
queue.add("банан");
queue.add("яблоко");
queue.add("ананас");
while (!queue.isEmpty()) {
    System.out.println(queue.poll());
}

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

ананас
банан
яблоко

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

Стек

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

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
while (!stack.empty()) {
    System.out.println(stack.pop());
}

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

3
2
1

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

Дек

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

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

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

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
stack.push(3);
while (!stack.isEmpty()) {
    System.out.println(stack.pop());
}

Результат:

3
2
1

Выводы

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

Тэги: Collections, Java.



Добавить комментарий

Ваше имя:
Текст комментария: