Алгоритмы и структуры данных

АТД: Очередь

Очередь (queue) — это абстрактный тип данных, который содержит коллекцию элементов, организованных по принципу FIFO.

Принцип FIFO (first in, first out — «первым пришёл — первым ушёл») предпологает, что элемент, первым попавшим в коллекцию, должен быть первым удален или обслужен. Принцип LIFO, по которому работает стек, полная противоположность этому — там элемент, пришедший первым, обслуживается самым последним, отдавая приоритет другим последним пришедшим элементам.

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

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

Операции на очереди

Очередь должна поддерживать следующие основные операции:

  • Enqueue (Add): добавить элемент в конец очереди
  • Dequeue (Remove): снять элемент с начала очереди
Принцип FIFO

Во всех популярных имплементациях обе операции выполняются за константное время.

Имплементация очереди

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

Имплементация с помощью массива

В данной имплементации мы сделаем ограниченную по размеру (bounded) очередь. Способ реализации очереди с помощью массива — это использование кольцевого буфера (circular buffer). Идея заключается в том, чтобы голова и хвост постоянно крутились по кругу в массиве, пока свободно место. То есть, если голова или хвост достигают последней ячейки массива (индекс N-1), их индекс сбрасывается и они начинают обход массива снова с первой ячейки массива (0).

Голова указывает на элемент, который надо забрать из очереди, а хвост — на ячейку, куда надо положить новый элемент (но не на ячейку, куда мы положили элемент в последний раз). Мы знаем, что места не осталось, если хвост при сдвиге вперед догонит голову. Также мы знаем, что очередь пуста, если голова догнала хвост, то есть голова теперь указывает на ячейку, куда ещё не был положен элемент. Для того, чтобы такие проверки были возможны, нам придется оставить 1 ячейку массива пустой, потому что хвост не должен догонять голову.

Для наглядности, это ситуация полной очереди:

Здесь показана ситуация, когда произошла вставка элемента 4 и tail сместился вперед. Мы видим, что мы имеем пустую ячейку, чтобы положить новый элемент, однако если мы это сделаем, то tail будет равен head, а это на самом деле ситуация пустой очереди:

Здесь показана ситуация, когда была очищена вся очередь путем чтения очереди (серым цветом показаны взятые из очереди элементы), и head догнал tail.

Если бы мы использовали для реализации обычный массив, а не кольцевой буффер (основанный на массиве), то при снятии какого-то элемента с очереди нам пришлось бы смещать все элементы в начало, чтобы следующий добавленный элемент оказался в первой ячейке массива (голова всегда смотрит на первую ячейку массива).

Заведем нужные переменные и стадию инициализации в конструкторе:

    private final E[] q;

    private final int arraySize = 64;

    /**
     * Голова.
     */
    private int head;

    /**
     * Хвост.
     */
    private int tail;

    @SuppressWarnings("unchecked")
    public ArrayQueue() {
        q = (E[]) new Object[arraySize];
        head = 0;
        tail = 0;
    }

Теперь напишем вспомогательную функция для сдвига указателя:

    private int movePointer(int pointer) {
        int next = ++pointer;
        if (next == arraySize) {
            return 0;
        } else {
            return next;
        }
    }

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

    public E add(E e) throws IllegalStateException {
        int tail = this.tail;
        if ((tail + 1 == head) || (head == 0 && tail + 1 == arraySize)) {
            throw new IllegalStateException("Queue is full");
        }

        q[tail] = e; /*вставляем новый элемент*/
        this.tail = movePointer(tail); /*сдвигаем хвост*/
        return e;
    }

Операция чтения забирает элемент с текущей головы и сдвигает голову вперед. При этом необходимо проверять, не пуста ли очередь, а пуста очередь тогда и только тогда, когда голова догнала хвост (то есть после последнего добавления элемента хвост сместился вперед, но новый элемент еще не был записан).

    public E remove() throws NoSuchElementException {
        int head = this.head;
        if (head == tail) {
            throw new NoSuchElementException("Queue is empty");
        }
        E e = q[head];
        q[head] = null;
        this.head = movePointer(head);
        return e;
    }

Имплементация на основе связного списка

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

Для реализации нам хватит односвязного списка: добавлять элементы мы будем в конец, а брать элементы — с начала, тем самым получая принцип FIFO. Обе операции работают за время O(1).

Добавление элемента в очередь:

    public E add(E e) {
        linkedList.insertLast(e);
        return e;
    }

Взятие элемента из очереди:

    public E remove() {
        return linkedList.removeFirst().value;
    }

Вот так вот просто!

Имплементации в Java

Также, как и в ситуации с стеком, самая популярная имплементация очереди — это ArrayDeque, но также очередь имплементирует LinkedList, который почти не используется.

Применение

Очереди используются в следующих задачах:

  • Когда необходимо обслужить данные или задачу, но на данный момент для этого нет ресурсов. Тогда, применив очередь, эти данные или задачи будут обслужены в порядке очереди. Пример — Kafka, RabbitMQ (брокеры сообщений)
  • Поикс в ширину (Breadth-First Search)
  • И другие задачи, где может понадобиться принцип FIFO

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

Ваш адрес email не будет опубликован.