Очередь
Общие сведения
Очередь (англ. queue) — абстрактный контейнер, доступ к элементам которого организован по принципу «первым вошёл — первым вышел» (англ. FIFO, First In — First Out). Поведение элементов очереди напоминает обслуживание покупателей в магазине: каждый новый клиент встаёт в конец очереди и ожидает, когда уйдут все стоящие перед ним.
Для очереди вводятся два абстрактных понятия: хвост (конец) очереди — место, в которое происходит добавление элементов, и голова (начало) очереди — место, из которого происходит удаление элементов.
Интерфейс
Очередь предоставляет три основные операции:
| void enqueue(T value) | — вставка элемента value в очередь; |
| T dequeue() | — извлечение элемента из очереди; |
| bool isEmpty() | — проверка очереди на отсутствие элементов. |
Все три метода должны иметь константное время работы (O(1)).
Демонстрация работы
Реализация на списке
Очередь можно реализовать на односвязном списке. Добавлять элементы в равной степени удобно как в начало списка, так и в конец (если имеется указатель на последний элемент), но в то же время удаление из конца списка реализуется сложнее, чем из начала (так как нужно иметь указатель на предпоследний элемент). Поэтому голова очереди будет располагаться в начале списка, а конец — в конце списка. На голову ссылается указатель Node *head, на хвост — Node *tail.