Руководство по интерфейсу очереди Java

1. Введение

В этом уроке мы обсудим интерфейс Java Queue .

Во- первых, мы взглянем на то, что делает Queue , и на некоторые из его основных методов `` . Далее мы углубимся в ряд реализаций, которые Java предоставляет в качестве стандарта.

Наконец, мы поговорим о безопасности потоков, прежде чем закончить все это.

2. Визуализация очереди

Давайте начнем с быстрой аналогии.

Представьте, что мы только что открыли наш первый бизнес – киоск с хот-догами. Мы хотим обслуживать наших новых потенциальных клиентов максимально эффективным для нашего малого бизнеса способом; один за раз. Во-первых, мы просим их выстроиться в стройную очередь перед нашим стендом, а новые клиенты присоединяются сзади. Благодаря нашим организаторским способностям теперь мы можем справедливо распространять наши вкусные хот-доги.

Очереди в Java работают аналогичным образом. После того, как мы объявим нашу очередь, мы можем добавить новые элементы сзади и удалить их спереди.

На самом деле, большинство очередей , с которыми мы столкнемся в Java, работают по принципу «первым пришел — первым обслужен» — часто сокращенно FIFO.

Однако есть одно исключение, о котором мы поговорим позже .

3. Основные методы

Очередь объявляет ряд методов , которые должны быть закодированы всеми реализующими классами. Давайте наметим некоторые из наиболее важных из них сейчас:

1. offer() — вставляет новый элемент в очередь
2. poll() — удаляет элемент из начала очереди .
3. peek() — Проверяет элемент в начале очереди, не удаляя его

4. Абстрактная очередь

AbstractQueue — это простейшая возможная реализация Queue , которую предоставляет Java. Он включает скелетную реализацию некоторых методов интерфейса Queue , за исключением offer .

Когда мы создаем пользовательскую очередь, расширяющую класс AbstractQueue , мы должны предоставить реализацию метода offer , которая не позволяет вставлять нулевые элементы.

Кроме того, мы должны предоставить методы peek , poll, size и итератор java.util . ``

Давайте соберем простую реализацию Queue , используя AbstractQueue.

Во-первых, давайте определим наш класс с помощью LinkedList для хранения элементов нашей очереди :

public class CustomForEachQueue<T> extends AbstractQueue<T> {

    private LinkedList<T> elements;

    public CustomForEachQueue() {
      this.elements = new LinkedList<T>();
    }

}

Далее давайте переопределим необходимые методы и предоставим код:

@Override
public Iterator<T> iterator() {
    return elements.iterator();
}

@Override
public int size() {
    return elements.size();
}

@Override
public boolean offer(T t) {
    if(t == null) return false;
    elements.add(t);
    return true;
}

@Override
public T poll() {
    Iterator<T> iter = elements.iterator();
    T t = iter.next();
    if(t != null){
        iter.remove();
        return t;
    }
    return null;
}

@Override
public T peek() {
    return elements.getFirst();
}

Отлично, давайте проверим, что это работает, с помощью быстрого модульного теста:

customQueue.add(7);
customQueue.add(5);

int first = customQueue.poll();
int second = customQueue.poll();

assertEquals(7, first);
assertEquals(5, second);

4. Подинтерфейсы

Как правило, интерфейс Queue наследуется тремя основными подинтерфейсами. Очереди блокировки, очереди передачи и очереди .

Вместе эти 3 интерфейса реализованы в подавляющем большинстве доступных очередей Java. Давайте кратко рассмотрим, для чего предназначены эти интерфейсы.

4.1. Блокировка очередей

Интерфейс BlockingQueue поддерживает дополнительные операции , которые заставляют потоки ожидать в очереди в зависимости от текущего состояния. Поток может ожидать, что очередь станет непустой при попытке извлечения или станет пустой при добавлении нового элемента.

Стандартные очереди блокировки включают LinkedBlockingQueue, SynchronousQueue и ArrayBlockingQueue .

Для получения дополнительной информации перейдите к нашей статье о блокировке очередей .

4.2. Очереди передачи

Интерфейс TransferQueue расширяет интерфейс BlockingQueue , но адаптирован к шаблону производитель-потребитель. Он контролирует поток информации от производителя к потребителю, создавая противодавление в системе.

Java поставляется с одной реализацией интерфейса TransferQueue , LinkedTransferQueue .

4.3. Деки

Deque — это сокращение от Double- Ended Que ue и аналог колоды карт — элементы могут быть взяты как из начала, так и из конца Deque . Подобно традиционной очереди, Deque предоставляет методы для добавления, извлечения и просмотра элементов, находящихся как сверху, так и снизу . ** ``**

Для подробного руководства о том, как работает Deque , ознакомьтесь с нашей статьей ArrayDeque .

5. Приоритетные очереди

Ранее мы видели, что большинство очередей , с которыми мы сталкиваемся в Java, следуют принципу FIFO.

Одним из таких исключений из этого правила является PriorityQueue . Когда новые элементы вставляются в очередь приоритетов , они упорядочиваются в соответствии с их естественным порядком или с помощью определенного компаратора , предоставляемого при создании очереди приоритетов . ``

Давайте посмотрим, как это работает, на простом модульном тесте:

PriorityQueue<Integer> integerQueue = new PriorityQueue<>();

integerQueue.add(9);
integerQueue.add(2);
integerQueue.add(4);

int first = integerQueue.poll();
int second = integerQueue.poll();
int third = integerQueue.poll();

assertEquals(2, first);
assertEquals(4, second);
assertEquals(9, third);

Несмотря на порядок, в котором наши целые числа были добавлены в Priority Queue , мы видим, что порядок извлечения изменяется в соответствии с естественным порядком чисел.

Мы видим, что то же самое верно и для строк :

PriorityQueue<String> stringQueue = new PriorityQueue<>();

stringQueue.add("blueberry");
stringQueue.add("apple");
stringQueue.add("cherry");

String first = stringQueue.poll();
String second = stringQueue.poll();
String third = stringQueue.poll();

assertEquals("apple", first);
assertEquals("blueberry", second);
assertEquals("cherry", third);

6. Безопасность потоков

Добавление элементов в очереди особенно полезно в многопоточных средах. Очередь может быть разделена между потоками и использоваться для блокировки прогресса до тех пор, пока не освободится место, что помогает нам преодолеть некоторые распространенные многопоточные проблемы.

Например, запись на один диск из нескольких потоков создает конкуренцию за ресурсы и может привести к увеличению времени записи. Создание одного потока записи с помощью BlockingQueue может решить эту проблему и значительно повысить скорость записи.

К счастью, Java предлагает ConcurrentLinkedQueue, ArrayBlockingQueue и ConcurrentLinkedDeque , которые являются потокобезопасными и идеально подходят для многопоточных программ.

7. Заключение

В этом руководстве мы подробно рассмотрели интерфейс Java Queue .

Во- первых, мы изучили, что делает Queue , а также реализации, которые предоставляет Java.

Далее мы рассмотрели обычный принцип очереди FIFO, а также PriorityQueue , который отличается своим порядком.

Наконец, мы рассмотрели безопасность потоков и способы использования очередей в многопоточной среде.

Как всегда, код доступен на GitHub .