Очередь (абстрактный тип данных)
-
Определение и использование очередей
- Очередь — это структура данных, которая поддерживает добавление и удаление элементов в порядке их вставки.
- Очередь может быть реализована с использованием односвязных списков или массивов.
-
Структура данных очереди
- Очередь состоит из трех односвязных списков: начало (f), конец (r) и задняя часть (s).
- Инвариант структуры: s является задней частью f без первых элементов r.
-
Реализация очереди
- Используется вспомогательная функция aux для поддержания инварианта структуры.
- В случае пустого списка s, |r| = |f| + 1, в противном случае |r| = |f|.
- Функция rotate возвращает обратную конкатенацию списков f, r и a, с временем выполнения O(r).
-
Функции очереди
- Вставка элемента в очередь занимает O(1) время.
- Удаление элемента из очереди занимает O(1) время, если элемент находится в начале очереди, и O(n) время, если элемент находится в конце очереди.
-
Индуктивное определение функции rotate
- Функция rotate принимает три списка и возвращает обратную конкатенацию.
- Индуктивное определение функции основано на вращении списков и использовании отложенного вычисления.
-
Счетчик в структуре данных очереди
- Список s используется для подсчета количества элементов в очереди.
- При |f| = |r|, список f принудительно вычисляется, что обеспечивает постоянное время операций.
-
Рекомендации и дальнейшее чтение
- Статья содержит материалы, являющиеся общественным достоянием.
- Ссылки на другие источники, включая книги и статьи, для более глубокого изучения темы.
Полный текст статьи: