Изменения

Перейти к: навигация, поиск

Очередь

683 байта добавлено, 19:21, 4 сентября 2022
м
rollbackEdits.php mass rollback
== Определение ==
[[Файл: Fifo_new.png|right|150px]]
'''Очередь''' (англ. ''queue'')  {{---}} это структура данных, добавление и удаление элементов в которой происходит путём операций <mathtex> \mathrm mathtt{push} </mathtex> и <mathtex> \mathrm mathtt{pop} </mathtex> соответственно. Притом первым из очереди удаляется элемент, который был помещен туда первым, то есть в очереди реализуется принцип «первым вошел — первым вышел» (англ. ''first-in, first-out {{---}} FIFO''). У очереди имеется '''голова''' (англ. ''head'') и '''хвост''' (англ. ''tail''). Когда элемент ставится в очередь, он занимает место в её хвосте. Из очереди всегда выводится элемент, который находится в ее голове.Очередь поддерживает следующие операции:* <tex> \mathtt{empty} </tex> {{---}} проверка очереди на наличие в ней элементов,*<mathtex> \mathrm mathtt {push} </mathtex> (запись в очередь) {{---}} операция вставки нового элемента.,*<mathtex> \mathrm mathtt{pop} </mathtex> (снятие с очереди) {{---}} операция удаления нового элемента.,*<mathtex> \mathrm mathtt{emptysize} </mathtex> {{---}} проверка операция получения количества элементов в очереди на наличие в ней элементов.
== Реализация циклической очереди на массиве ==
Очередь, способную вместить не более <tex>\mathtt{n}</tex> элементов, можно реализовать с помощью массива <tex>\mathtt{elements[0..\dots n-1]}</tex>. Она будет обладать следующими полями:* <tex>\mathtt{head}</tex> ({{---}} голова очереди),* <tex>\mathtt{tail}</tex> ({{---}} хвост очереди). === empty ===* <tex>size</tex> '''boolean''' empty(размер очереди): '''return''' head == tail
=== push ===
'''function''' push(x: '''T'''): '''if''' (size() != n) elements[tail] = x tail = (tail + 1) % elements.lengthn
=== pop ===
'''T''' pop():
'''if''' (empty()) '''notreturn null''' empty() x = elements[head] head = (head + 1) % elements.lengthn '''return''' x
=== empty size === '''booleanint''' emptysize(): '''if''' head > tail '''return''' n - head == + tail '''else''' '''return''' tail- headИз-за того что нам не нужно перевыделять снова выделять память, каждая операция выполняется за <tex>O(1)</tex> времени.
'''Плюсы:'''
* прост проста в разработке,* по сравнению с реализацией на списке, есть незначительная экономия памяти.
'''Минусы:'''
* количество элементов в очереди ограничено размером массива (исправляется написанием функции расширения массива),* при переполнении очереди требуется перевыделение памяти и копирование всех элементов в новый массив.
== Реализация на списке ==
Для данной реализации очереди необходимо создать [[Список | список]] (<tex>list</tex>) и операции работы на созданном списке.
Реализация очереди на односвязном списке:
=== list List ===* <code>ListItem(data : '''T''', next : '''ListItem''')</code> {{---}} конструктор,* <tex>\mathtt{x.value}</tex> {{---}} поле, в котором хранится значение элемента,* <tex>\mathtt{x.next}</tex> {{---}} указатель на следующий элемент очереди.
=== push ===
'''function''' push(x: '''T'''):
element = tail
tail = new listListItem(x, NULL)
'''if''' size == 0
head = tail
'''else'''
element.next = tail
size++
=== pop ===
'''T''' pop(): '''if''' empty() '''return'''size--
element = head
head = head.next
'''return''' head == tail
[[Файл: Queue.png|right|230px]]
Каждая операция выполняется за время <tex>O(1)</tex>.
'''Плюсы:'''
* каждая операция выполняется за время <tex>O(1)</tex>.
'''Минусы:'''
* Память память фрагментируется гораздо сильнее и последовательная итерация по такой очереди может быть ощутимо медленнее, нежели итерация по очереди реализованной на массиве.
== Реализация на двух стеках ==
Эта реализация пригодится, например, для нахождения наименьшего элемента за <tex>O(1)</tex>.Очередь можно реализовать на двух [[Стек|стеках]] <tex>\mathtt{leftStack}</tex> и <tex>\mathtt{rightStack}</tex>. Один из стеков Поступим следующим образом: <tex>(\mathtt{leftStack)}</tex> будем использовать для операции <mathtex> \mathrm mathtt {push} </mathtex>, другой <tex>\mathtt{rightStack}</tex> для операции <mathtex> \mathrm mathtt{pop} </mathtex>. При этом, если при попытке извлечения элемента из <tex>\mathtt{rightStack}</tex> он оказался пустым, просто перенесем все элементы из <tex>\mathtt{leftStack}</tex> в него (при этом элементы в <tex>\mathtt{rightStack}</tex> получатся уже в обратном порядке, что нам и нужно для извлечения элементов, а <tex>\mathtt{leftStack}</tex> станет пустым).
* <mathtex> \mathrm mathtt{pushLeft} </mathtex> и <mathtex> \mathrm mathtt{pushRight} </mathtex> {{---}} функции, реализующие операцию <tex>\mathtt{push} </tex> для соответствующего стека; ,* <mathtex> \mathrm mathtt{popLeft} </mathtex> и <mathtex> \mathrm mathtt{popRight} </mathtex> {{---}} аналогично операции <mathtex> \mathrm mathtt {pop} </mathtex>.
=== push ===
'''function''' push(x: '''T'''):
pushLeft(x)
=== pop ===
'''T''' pop():
'''if''' '''not''' rigthStackrightStack.empty()
'''return''' popRight()
'''else'''
'''return''' popRight()
При выполнении операции <mathtex> \mathrm mathtt{push} </mathtex> будем использовать три монеты: одну для самой операции, вторую в качестве резерва на операцию <mathtex> \mathrm mathtt{pop} </mathtex> из первого стека, третью во второй стек на финальный <mathtex> \mathrm mathtt{pop} </mathtex>. Тогда для операций <mathtex> \mathrm mathtt{pop} </mathtex> учётную стоимость можно принять равной нулю и использовать для операции монеты, оставшиеся после операции <mathtex> \mathrm mathtt{push} </mathtex>.
Таким образом, для каждой операции требуется <tex>O(1)</tex> монет, а значит, амортизационная стоимость операций <tex>O(1)</tex>.
'''Плюсы:'''
* эту реализацию несложно модифицировать для получения минимума в текущей очереди за <tex>O(1)</tex>.
'''Минусы:'''
* Если если <tex>\mathtt{leftStack}</tex> не пуст, то операция <mathtex> \mathrm mathtt{pop} </mathtex> может выполняться <tex>O(n)</tex> времени, в отличии отличие от других реализаций, где <mathtex> \mathrm mathtt{pop} </mathtex> всегда выполняется за <tex>O(1)</tex>.
== Реализация на шести стеках ==
=== Отличия от других реализаций ===
'''Плюсы:''':* <tex>O(1)</tex> реального времени на операцию.,* Возможность возможность дальнейшего улучшения до [[Персистентная очередь|персистентной очереди]], если использовать [[Персистентный стек|персистентные стеки]].
'''Минусы:''':* Дольше дольше в среднем выполняются операции.,* Больше больше расход памяти.,* Большая большая сложность реализации.
== См. также ==
* [[Персистентная очередь]]
== Ссылки Источники информации ==
* [[wikipedia:ru:Очередь_(программирование)|Википедия {{---}} Очередь (программирование)]]
* Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 10.1, стр. 262
1632
правки

Навигация