Очередь
Определение
Очередь (англ. queue) — это структура данных, добавление и удаление элементов в которой происходит путём операций и соответственно. Притом первым из очереди удаляется элемент, который был помещен туда первым, то есть в очереди реализуется принцип «первым вошел — первым вышел» (англ. first-in, first-out — FIFO). У очереди имеется голова (англ. head) и хвост (англ. tail). Когда элемент ставится в очередь, он занимает место в её хвосте. Из очереди всегда выводится элемент, который находится в ее голове. Очередь поддерживает следующие операции:
- — проверка очереди на наличие в ней элементов,
- (запись в очередь) — операция вставки нового элемента,
- (снятие с очереди) — операция удаления нового элемента,
- — операция получения количества элементов в очереди.
Реализация циклической очереди на массиве
Очередь, способную вместить не более элементов, можно реализовать с помощью массива . Она будет обладать следующими полями:
- — голова очереди,
- — хвост очереди.
empty
boolean empty(): return head == tail
push
function push(x : T):
if (size() != n)
elements[tail] = x
tail = (tail + 1) % n
pop
T pop():
if (empty())
return null
x = elements[head]
head = (head + 1) % n
return x
size
int size()
if head > tail
return n - head + tail
else
return tail - head
Из-за того что нам не нужно снова выделять память, каждая операция выполняется за времени.
Плюсы:
- проста в разработке,
- по сравнению с реализацией на списке есть незначительная экономия памяти.
Минусы:
- количество элементов в очереди ограничено размером массива (исправляется написанием функции расширения массива),
- при переполнении очереди требуется перевыделение памяти и копирование всех элементов в новый массив.
Реализация на списке
Для данной реализации очереди необходимо создать список и операции работы на созданном списке.
Реализация очереди на односвязном списке:
List
-
ListItem(data : T, next : ListItem)— конструктор, - — поле, в котором хранится значение элемента,
- — указатель на следующий элемент очереди.
push
function push(x : T):
element = tail
tail = ListItem(x, NULL)
if size == 0
head = tail
else
element.next = tail
size++
pop
T pop(): size-- element = head head = head.next return element
empty
boolean empty(): return head == tail
Плюсы:
- каждая операция выполняется за время .
Минусы:
- память фрагментируется гораздо сильнее и последовательная итерация по такой очереди может быть ощутимо медленнее, нежели итерация по очереди реализованной на массиве.
Реализация на двух стеках
Очередь можно реализовать на двух стеках и . Поступим следующим образом: будем использовать для операции , для операции . При этом, если при попытке извлечения элемента из он оказался пустым, просто перенесем все элементы из в него (при этом элементы в получатся уже в обратном порядке, что нам и нужно для извлечения элементов, а станет пустым).
- и — функции, реализующие операцию для соответствующего стека,
- и — аналогично операции .
push
function push(x : T): pushLeft(x)
pop
T pop():
if not rightStack.empty()
return popRight()
else
while not leftStack.empty()
pushRight(popLeft())
return popRight()
При выполнении операции будем использовать три монеты: одну для самой операции, вторую в качестве резерва на операцию из первого стека, третью во второй стек на финальный . Тогда для операций учётную стоимость можно принять равной нулю и использовать для операции монеты, оставшиеся после операции .
Таким образом, для каждой операции требуется монет, а значит, амортизационная стоимость операций .
Плюсы:
- эту реализацию несложно модифицировать для получения минимума в текущей очереди за .
Минусы:
- если не пуст, то операция может выполняться времени, в отличии от других реализаций, где всегда выполняется за .
Реализация на шести стеках
Одним из минусов реализации на двух стеках является то, что в худшем случае мы тратим времени на операцию. Если распределить время, необходимое для перемещения элементов из одного стека в другой, по операциям, мы получим очередь без худших случаев с истинного времени на операцию.
Подробное описание в статье Персистентная очередь.
Отличия от других реализаций
Плюсы:
- реального времени на операцию,
- возможность дальнейшего улучшения до персистентной очереди, если использовать персистентные стеки.
Минусы:
- дольше в среднем выполняются операции,
- больше расход памяти,
- большая сложность реализации.
См. также
Источники информации
- Википедия — Очередь (программирование)
- Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 10.1, стр. 262
- T. H. Cormen. «Introduction to Algorithms» third edition, Chapter 10.1, p. 262
- Hood R., Melville R. Real Time Queue Operations in Pure LISP. — Cornell University, 1980
