Очередь

Общие сведения

Очередь (англ. queue) — абстрактный контейнер, доступ к элементам которого организован по принципу «первым вошёл — первым вышел» (англ. FIFO, First In — First Out). Поведение элементов очереди напоминает обслуживание покупателей в магазине: каждый новый клиент встаёт в конец очереди и ожидает, когда уйдут все стоящие перед ним.

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

Интерфейс

Очередь предоставляет три основные операции:

void enqueue(T value)	— вставка элемента value в очередь;
T dequeue()	— извлечение элемента из очереди;
bool isEmpty()	— проверка очереди на отсутствие элементов.

Все три метода должны иметь константное время работы (O(1)).

Демонстрация работы

Демонстрация работы очереди

Реализация на списке

Очередь можно реализовать на односвязном списке. Добавлять элементы в равной степени удобно как в начало списка, так и в конец (если имеется указатель на последний элемент), но в то же время удаление из конца списка реализуется сложнее, чем из начала (так как нужно иметь указатель на предпоследний элемент). Поэтому голова очереди будет располагаться в начале списка, а конец — в конце списка. На голову ссылается указатель Node *head, на хвост — Node *tail.

struct Node {
   int val;
   Node *next;
   Node(int v = 0, Node *n = NULL) {
       val = v;
       next = n;
   }
} * head, * tail;

В конструкторе очереди указатели на голову и хвост инициализируются значением NULL.

Queue() {
    head = tail = NULL;
}

Проверка на пустоту

Если очередь не пуста, то указатели head и tail обязательно будут ссылаться на какие-то её элементы (возможно, что на один и тот же). Поэтому проверку на остутствие элементов в очереди можно производить с помощью любого из этих двух указателей:

bool isEmpty() {
    return top == NULL;
}

Вставка элемента

Если до вставки элемента очередь пуста, то необходимо выполнить следующие операции:

• Определение нового элемента списка и инициализация его поля val;
• Так как единственный элемент будет являться и началом, и концом очереди, нужно направить на только что созданный элемент указатели head и tail.

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

• Определение нового элемента списка и инициализация его поля val;
• Новый элемент будет следовать за текущим конечным, поэтому на него будет указывать поле tail->next;
• Так как новый элемент становится последним, на него теперь будет указывать tail.

Обратите внимание, как выполнение последних двух операций происходит с помощью цепочки присваиваний: сначала адрес нового элемента сохраняется в tail->next, а затем он же передаётся в сам tail.

void enqueue(int value) {
    if (head == NULL)
        head = tail = new Node(value, NULL);
    else
        tail = tail->next = new Node(value, NULL);
}

Извлечение элемента

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

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

• Требуется сохранить значение head->val во временной переменой для возможности последующего возврата;
• Указатель на голову очереди нужно сместить на следующий элемент, но перед этим нужно сохранить во временной переменной предыдущий адрес, чтобы можно было освободить память;
• Единственная разница в реализации заключается в том, что если очередь становится пустой, то требуется явно присвоить значение NULL указателю tail;
• Далее можно освободить память и вернуть сохранённое ранее значение.

int dequeue() {
    if (head == NULL)
        /* обработка ошибки - нет элементов для извлечения */
    int v = head->val;
    Node *tmp = head;
    head = head->next;
    if (head == NULL)
        tail = NULL;
    delete tmp;
    return v;
}

---

Ниже приведён полный код реализации очереди на односвязном списке. Попытка извлечения из пустой очереди выявляется с помощью конструкции assert (заголовочный файл <assert.h> либо <cassert>).

class Queue {

    struct Node {
        int val;
        Node *next;
        Node(int v = 0, Node *n = NULL) {
            val = v;
            next = n;
        }
    } *head, *tail;

public:

    Queue() {
        head = tail = NULL;
    }

    void enqueue(int value) {
        if (head == NULL)
            head = tail = new Node(value, NULL);
        else
            tail = tail->next = new Node(value, NULL);
        }

    int dequeue() {
        assert(head != NULL)
        int v = head->val;
        Node *tmp = head;
        head = head->next;
        if (head == NULL)
            tail = NULL;
        delete tmp;
        return v;
    }

    bool isEmpty() {
        return head == NULL;
    }

};