Статьи
YouTube-канал

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

16 апреля 2019

Тэги: Collections Java

Содержание

  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. Рассмотрим их на примере.

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.


Облако тэгов

Kotlin, Java, Java 16, Java 11, Java 10, Java 9, Java 8, Spring, Spring Boot, Spring Data, SQL, PostgreSQL, Oracle, Hibernate, Collections, Stream API, многопоточность, ввод-вывод, Apache, maven, gradle, JUnit, YouTube, новости, ООП, алгоритмы, головоломки, rest, GraphQL, Excel, XML, json, yaml

Последние статьи


Комментарии

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

×

devmark.ru