Очередь. Функциональная спецификация очереди: FIFO и семь операций
Что это такое
Очередь (queue) - упорядоченный динамический набор данных, у которого включение элементов производится на одном конце, а исключение - на другом. Полная аналогия с очередью в магазине: встать можно только в конец, а обслуживают того, кто стоит первым.
Отсюда принцип FIFO, First In - First Out: первым пришел - первым ушел. Сравните со стеком: там оба действия происходят на одном конце, и порядок инвертируется. Очередь порядок сохраняет - элементы выходят ровно в том порядке, в каком вошли.
Зачем это нужно
Очередь - стандартное средство сглаживания разницы в скорости двух процессов, когда поставщик данных работает быстрее потребителя или неравномерно:
- Буферы - клавиатуры, сетевых маршрутизаторов, печати: данные накапливаются и обрабатываются в порядке поступления.
- Планирование задач в операционных системах - запросы удовлетворяются строго в порядке прихода.
- Обработка сообщений - от событий интерфейса до очередей сообщений в распределенных системах.
- Моделирование реальных процессов: касса, посадка, колл-центр.
Очередь. Функциональная спецификация очереди: семь операций
Функциональная спецификация очереди почти повторяет стековую - меняется только конец, с которого читаем:
- СОЗДАТЬ - порождает пустую очередь.
- ПУСТО - проверяет, есть ли элементы.
- В_ОЧЕРЕДЬ (Enqueue) - добавляет элемент в хвост.
- ИЗ_ОЧЕРЕДИ (Dequeue) - удаляет первый, самый старый элемент. Чтение разрушающее.
- ПЕРВЫЙ (Front) - показывает первый элемент, не удаляя его.
- ДЛИНА - возвращает количество элементов.
- УНИЧТОЖИТЬ - удаляет очередь целиком.
Доступ к середине очереди спецификация запрещает - только два конца, у каждого своя роль.
Тренажер: операции очереди по шагам
Выполним над пустой очередью цепочку операций Enqueue 5, 3, 8, Front, Size, Dequeue, Dequeue, Enqueue 1, Dequeue, Dequeue и сравним со стеком: голова очереди слева, хвост справа, а числа взяты те же, что и в тренажере стека.
list для очереди
не подходит: pop(0) сдвигает все оставшиеся элементы и работает
за O(N). Правильный инструмент - collections.deque:
append() в хвост и popleft() из головы работают
за O(1).
Интерфейс очереди на C
Как и для стека, функциональная спецификация на C превращается в набор объявлений - без единого слова о том, как элементы хранятся в памяти:
#include <stdbool.h>
typedef int T; /* тип элемента */
typedef struct Queue Queue;
/* Интерфейс очереди (функциональная спецификация) */
void Create(Queue* q);
bool Empty(Queue* q);
void Push(Queue* q, T element); /* В_ОЧЕРЕДЬ: в хвост */
void Pop(Queue* q); /* ИЗ_ОЧЕРЕДИ: из головы */
T Top(Queue* q); /* ПЕРВЫЙ: смотрит, не удаляя */
int Size(Queue* q); /* ДЛИНА */
void Destroy(Queue* q);Как эти операции реализовать - тема следующих трех уроков: на файле, на массиве с кольцевым буфером и на связном списке.
Коротко: главное
- Очередь - структура с двумя концами: добавление в хвост, удаление из головы.
- Принцип FIFO: порядок извлечения совпадает с порядком добавления.
- Назначение: сглаживание разницы скоростей производителя и потребителя данных.
- Операции: Create, Empty, Enqueue, Dequeue (разрушающее чтение), Front, Size, Destroy.
- Стек инвертирует порядок элементов, очередь - сохраняет.
Проверьте себя
В пустую очередь по очереди добавили буквы А, Б, Ц. В каком порядке они будут извлечены?