У многих людей слово “очередь” вызывает очень мало приятных ассоциаций. Но сегодня мы говорим о других очередях — в Java. Очередью в Java считается все, что наследует интерфейс Queue, который в свою очередь расширяет Collection. Это значит, что с очередями можно работать, как с коллекциями.
Очереди в Java работают по двум принципам: FIFO и LIFO.
FIFO — First In First Out, принцип обычной очереди (конечно, если нет тех кому нужно “только спросить”), в котором первый элемент попадает в очередь и первым выходит из нее.
LIFO — Last In First Out, принцип стека, в котором последний элемент, добавленный в очередь, первым выйдет из нее. Например, как с колодой карт: ты будешь брать все карты с верха по одной, чтобы дойти до конца.
Иерархия Queue в Java выглядит следующим образом:
Здесь видно, что у Queue есть 3 класса реализации: LinkedList, ArrayDeque и PriorityQueue. LinkedList и ArrayDeque наследует напрямую не от Queue, а от Deque.
Deque — это интерфейс, который добавили в 6 версии Java. Он включает в себя ряд полезных для очередей методов и дает возможность очереди функционировать как двунаправленная очередь. То есть работать по принципу FIFO или LIFO.
Одним из двух наследников Deque является ArrayDeque. Он поддерживает двустороннюю структуру данных очереди, что дает возможность вставлять и удалять элементы с обеих сторон. Также он — динамический массив, который может автоматически увеличивать свой размер.
Есть еще класс PriorityQueue, прямой наследник Queue: принцип его работы отличается от наследников Dequeue.
PriorityQueue — это очередь с приоритетом, которая по умолчанию размещает элементы согласно естественному порядку сортировки. Для сортировки здесь используется Comparable и Comparator. Принцип здесь такой же, как и с TreeSet или TreeMap — классов, которые следуют интерфейсу Comparable и имеют свой порядок сортировки.
PriorityQueue<String> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(String::length));
priorityQueue.add("Andrew");
priorityQueue.add("John");
priorityQueue.add("Rob");
while (!priorityQueue.isEmpty()) {
System.out.println(priorityQueue.remove());
}
Запустив этот пример в консоли, ты получишь:
John
Andrew
Так как мы работаем с очередями, а не обычными коллекциями, мы должны удалить элемент из списка. Используем эту конструкцию:
while (!priorityQueue.isEmpty()) {
System.out.println(priorityQueue.remove());
}
Интерфейс Deque наследует методы Queue и добавляет ряд своих интересных методов:
void addFirst(Е obj) | Добавляет элемент obj в начало очереди |
void addLast(Е obj) | Добавляет элемент obj в конец очереди |
Е getFirst() | Возвращает первый элемент из очереди |
Е getLast() | Возвращает последний элемент из очереди |
boolean offerFirst(Е obj) | Добавляет элемент obj в начало очереди, и возвращает true если элемент добавлен, в противном случае вернет false |
boolean offerLast(E obj) | Добавляет элемент obj в конец очереди, и возвращает true если элемент добавлен, в противном случае вернет false |
Е рор() | Вытаскивает первый элемент из очереди и удаляет его |
void push(Е obj) | Добавляет элемент obj в начало очереди |
Е peekFirst() | Возвращает (но не удаляет) первый элемент из очереди |
Е peekLast() | Возвращает (но не удаляет) последний элемент из очереди |
Е pollFirst() | Возвращает и удаляет первый элемент из очереди, вернет null, если нет элементов |
Е pollLast() | Возвращает и удаляет последний элемент из очереди, вернет null, если нет элементов |
Е removeLast() | Возвращает и удаляет первый элемент очереди, создаст исключение, если нет элементов |
Е removeFirst() | Возвращает и удаляет последний элемент очереди, создаст исключение, если нет элементов |
boolean removeFirstOccurrence(Object obj) | Удаляет первое вхождение obj из очереди |
boolean removeLastOccurrence(Object obj) | Удаляет последнее вхождение obj из очереди |
Давай теперь рассмотрим несколько из них на практике.
Добавим сначала элемент в очередь:
Deque<String> deque = new ArrayDeque<>();
deque.add("Apple"); // Добавляет элемент Apple в конец очереди
deque.addFirst("Orange"); // Добавляет элемент Orange в начало очереди
deque.addLast("Pineapple"); // Добавляет элемент Pineapple в конец очереди
System.out.println(deque);
Теперь получим значения с очереди:
Deque<String> deque = new ArrayDeque<>();
deque.add("Apple");
deque.addFirst("Orange");
deque.addLast("Pineapple");
System.out.println("The First element is: "+ deque.getFirst());
System.out.println("The Last element is: " + deque.getLast());
}
Этот код выведет в консоли первый и последний элемент очереди.
The Last element is: Pineapple
Deque<String> deque = new ArrayDeque<>();
deque.add("Apple");
deque.addFirst("Orange");
deque.addLast("Pineapple");
deque.add("Lemon");
System.out.println(deque.pop()); // вытащит и удалит верхний элемент очереди
System.out.println(deque.poll()); // вытащит и удалит верхний элемент очереди
System.out.println(deque);
Запустив этот код, получим:
Apple
[Pineapple, Lemon]
Разница между методами pop() и poll() в том, что pop() вызовет исключение NoSuchElementException при пустом списке, а poll() вернет null.
Теперь рассмотрим методы pollFirst() и pollLast().
Deque<String> deque = new ArrayDeque<>();
deque.add("Apple");
deque.addFirst("Orange");
deque.addLast("Pineapple");
deque.add("Lemon");
System.out.println(deque.pollFirst()); // вытащит и удалит первый элемент очереди
System.out.println(deque.pollLast()); // вытащит и удалит последний элемент очереди.
System.out.println(deque);
Lemon
[Apple, PineApple]
Оба метода возвращают и удаляют значение из очереди.
Пример использования методов peekFirst() и peekLast():
Deque<String> friends = new ArrayDeque<>();
friends.add("John");
friends.add("Rob");
friends.add("Greg");
friends.add("Max");
friends.add("Oliver");
System.out.println("The first element is: " + friends.peekFirst());
System.out.println("The last element is: " + friends.peekLast());
System.out.println(friends);
The last element is: Oliver
[John, Rob, Greg, Max, Oliver]
Оба метода возвращают первый/последний элемент из очереди и не удаляют их. В случае, если очередь пуста, будет возвращено null.
В общем, как-то так, сегодня мы научились работать с очередями в Java. Теперь ты будешь знать, как их использовать на практике.
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ
LinkedList
и переопределил методaddAll
, где отсортировал коллекцию. Ну логично же, думал я, пока не посмотрел правильное решение сPriorityQueue
🤦♂️ Хотя, если подумать, в этом что-то есть. Т.е. если в будущем вам в лекции расскажут про класс PriorityQueue, а потом дадут задачу с условием (заменить LinkedList на другой класс), это будет совсем уныло и не интересно) лан, Валидатор принял и мойMyList
, идём дальше.