Очереди представляют структуру данных, работающую по принципу FIFO (first in - first out). То есть чем раньше был добавлен элемент в коллекцию, тем раньше он из нее удаляется. Это стандартная модель однонаправленной очереди. Однако бывают и двунаправленные - то есть такие, в которых мы можем добавить элемент не только в начала, но и в конец. И соответственно удалить элемент не только из конца, но и из начала.
Особенностью классов очередей является то, что они реализуют специальные интерфейсы Queue или Deque.
Обобщенный интерфейс Queue<E> расширяет базовый интерфейс Collection и определяет поведение класса в качестве однонаправленной
очереди. Свою функциональность он раскрывает через следующие методы:
E element(): возвращает, но не удаляет, элемент из начала очереди. Если очередь пуста, генерирует исключение
NoSuchElementException
boolean offer(E obj): добавляет элемент obj в конец очереди. Если элемент удачно добавлен, возвращает true, иначе - false
E peek(): возвращает без удаления элемент из начала очереди. Если очередь пуста, возвращает значение null
E poll(): возвращает с удалением элемент из начала очереди. Если очередь пуста, возвращает значение null
E remove(): возвращает с удалением элемент из начала очереди. Если очередь пуста, генерирует исключение
NoSuchElementException
Таким образом, у всех классов, которые реализуют данный интерфейс, будет метод offer для добавления в очередь, метод poll
для извлечения элемента из головы очереди, и методы peek и element, позволяющие просто получить элемент из головы очереди.
Таким образом, у Queue есть несколько методов, которые позволяют добавлять, удалять и получать данные, но эти методы различаются в зависимости от того, генерируют они исключение или возвращают специальное значение -
результат успешности операции. Краткая сводка по методам Queue
| Первый элемент (Head) | Последний элемент (Tail) | |||
Генерация исключение |
Возвращение значения |
Генерация исключение |
Возвращение значения |
|
Вставка |
|
|
|
|
Удаление |
|
|
|
|
Получение |
|
|
|
|
Сравнение методов Queue и Deque:
Метод |
Метод |
|
|
|
|
|
|
|
|
|
|
|
|
В Java очереди представлены рядом классов. Одни из низ - класс ArrayDeque<E>.
Этот класс представляют обобщенную двунаправленную очередь, наследуя функционал от класса AbstractCollection и применяя интерфейс
Deque.
В классе ArrayDeque определены следующие конструкторы:
ArrayDeque(): создает пустую очередь
ArrayDeque(Collection<? extends E> col): создает очередь, наполненную элементами из коллекции col
ArrayDeque(int capacity): создает очередь с начальной емкостью capacity. Если мы явно не указываем начальную емкость, то
емкость по умолчанию будет равна 16
Добавление в ArrayDeque:
import java.util.ArrayDeque;
public class Program{
public static void main(String[] args) {
ArrayDeque<String> people = new ArrayDeque<String>();
System.out.println(people); // []
// добавим ряд элементов
people.add("Tom"); // [Tom]
people.add("Bob"); // [Tom, Bob]
// добавляем элемент в самое начало
people.push("Sam"); // [Sam, Tom, Bob]
// добавляем элемент в самое начало
people.addFirst("Alice"); // [Alice, Sam, Tom, Bob]
// добавляем элемент в конец коллекции
people.addLast("Kate"); // [Alice, Sam, Tom, Bob, Kate]
// добавляем элемент в самое начало
people.offerFirst("Alex"); // [Alex, Alice, Sam, Tom, Bob]
// добавляем элемент в конец коллекции
people.offerLast("Bill"); // [Alex, Alice, Sam, Tom, Bob, Kate, Bill]
// добавляем элемент в конец коллекции
people.offer("Tim"); // [Alex, Alice, Sam, Tom, Bob, Kate, Bill, Tim]
// выводим все
System.out.println(people); // [Alex, Alice, Sam, Tom, Bob, Kate, Bill, Tim]
}
}
Удаление элементов из ArrayDeque:
import java.util.ArrayDeque;
import java.util.Collections;
public class Program{
public static void main(String[] args) {
ArrayDeque<String> people = new ArrayDeque<String>();
// добавляем ряд объектов
Collections.addAll(people, new String[]{ "Alex", "Alice", "Sam", "Tom", "Bob", "Kate", "Bill", "Tim"});
System.out.println(people); // [Alex, Alice, Sam, Tom, Bob, Kate, Bill, Tim]
// удаляем элемент из начала
var person = people.poll();
System.out.println(person); // Alex
// удаляем элемент из начала в [Alice, Sam, Tom, Bob, Kate, Bill, Tim]
person = people.poll();
System.out.println(person); // Alice
// удаляем элемент из конца в [Sam, Tom, Bob, Kate, Bill, Tim]
person = people.pollLast();
System.out.println(person); // Tim
// удаляем элемент из начала в [Sam, Tom, Bob, Kate, Bill]
person = people.remove();
System.out.println(person); // Sam
// удаляем элемент из начала в [Tom, Bob, Kate, Bill]
person = people.removeFirst();
System.out.println(person); // Tom
// удаляем элемент из конца в [Bob, Kate, Bill]
person = people.removeLast();
System.out.println(person); // Bill
// удаление произвольного элемента из [Bob, Kate]
boolean removed = people.remove("Kate");
System.out.println("Kate is removed: " + removed); // Kate is removed: true
// удаление произвольного элемента из [Bob]
removed = people.remove("Charl");
System.out.println("Charl is removed: " + removed); // Charl is removed: false
// выводим оставшиеся
System.out.println(people); // [Bob]
people.clear();
// удаляем оставшиеся
System.out.println(people); // [Bob]
}
}
Получение элементов из очереди:
import java.util.ArrayDeque;
import java.util.Collections;
public class Program{
public static void main(String[] args) {
ArrayDeque<String> people = new ArrayDeque<String>();
// добавляем ряд объектов
Collections.addAll(people, new String[]{"Tom", "Bob", "Sam"});
// получаем элемент из начала
var first = people.element();
System.out.println(first); // Tom
first = people.peek();
System.out.println(first); // Tom
first = people.peekFirst();
System.out.println(first); // Tom
first = people.getFirst();
System.out.println(first); // Tom
// получаем элемент из конца
var last = people.getLast();
System.out.println(last); // Sam
last = people.peekLast();
System.out.println(last); // Sam
// проверка наличия
boolean available = people.contains("Tom");
System.out.println("Tom is avalable: " + available); // true
available = people.contains("Alex");
System.out.println("Alex is avalable: " + available); // false
// перебор без извлечения
for(var p : people){
System.out.println(p);
}
// перебор коллекции с извлечением
while(people.peek() != null){
// извлечение c начала
System.out.println(people.pop());
}
}
}
Очередь приоритетов, представленная в языке Java классом PriorityQueue, извлекает элементы в отсортированном порядке. То есть, при каждом получении или удалении элемента с начала очереди мы будем получать условно говоря "наименьший элемент". Однако очередь приоритетов не сортирует все свои элементы. При итерации по элементам они не обязательно будут отсортированы. Очередь приоритетов использует структуру данных под названием куча. Куча — это самоорганизующееся двоичное дерево, в котором операции добавления и удаления перемещают наименьший элемент в корень, не тратя время на сортировку всех элементов.
Часто очередь приоритетов используется для планирования заданий. Каждое задание имеет приоритет. Задания добавляются в случайном порядке. Всякий раз, когда удаётся запустить новое задание, задание с наивысшим приоритетом удаляется из очереди.
Поскольку при работе очереди приоритетов применяется сортировка, то PriorityQueue может содержать либо элементы класса, который реализет интерфейс Comparable, либо через конструктор
при создании очереди приоритетов надо передать объект Comparator, который определяет логику сортировки. Конструкторы класса PriortyQueue:
PriorityQueue(): создает очередь PriorityQueue с начальной вместимостью по умолчанию (11), элементы которой упорядочены в соответствии с их естественным порядком
PriorityQueue(int initialCapacity): создает очередь PriorityQueue с указанной начальной вместимостью, элементы которой упорядочены в соответствии с их естественным порядком
PriorityQueue(int initialCapacity, Comparator<? super E> comparator): создает очередь PriorityQueue с указанной начальной вместимостью, элементы которой упорядочены в соответствии с указанным компаратором
PriorityQueue(Collection<? extends E> c): создает очередь PriorityQueue, которая содержит элементы изуказанной коллекции
PriorityQueue(Comparator<? super E> comparator): создает очередь PriorityQueue с начальной вместимостью по умолчанию, элементы которой упорядочены в соответствии с указанным компаратором
PriorityQueue(PriorityQueue<? extends E> c): создает PriorityQueue, которая содержит элементы из другой PriorityQueue
PriorityQueue(SortedSet<? extends E> c): создает PriorityQueue, которая содержит элементы из SortedSet
PriorityQueue реализует интерфейсы Collection<E> и Queue<E> и соответственно методы этих интерфейсов. Применение PriorityQueue:
import java.util.PriorityQueue;
public class Program{
public static void main(String[] args) {
var people = new PriorityQueue<String>();
// добавляем ряд объектов
people.add("Tom");
people.add("Bob");
people.add("Sam");
System.out.println(people); // [Bob, Tom, Sam]
var numbers = new PriorityQueue<Integer>();
// добавляем ряд объектов
numbers.add(3);
numbers.add(1);
numbers.add(5);
numbers.add(4);
System.out.println(numbers); // [1, 3, 5, 4]
}
}
Здесь определены две очереди приоритетов - для строк и чисел. И в обоих случаях "наименьший" элемент располагается в самом начале. Хотя в целом коллекция не сортируется.