Изменения
Нет описания правки
== Реализация циклической очереди на массиве ==
Очередь, способную вместить не более <tex>\mathtt{n}</tex> элементов, можно реализовать с помощью массива <tex>\mathtt{elements[0\dots n-1]}</tex>. Она будет обладать следующими полями:
* <tex>\mathtt{head}</tex> {{---}} голова очереди,* <tex>\mathtt{tail}</tex> {{---}} хвост очереди.
=== empty ===
'''Плюсы:'''
* Проста проста в разработке.,* По по сравнению с реализацией на списке есть незначительная экономия памяти.
'''Минусы:'''
* Количество количество элементов в очереди ограничено размером массива (исправляется написанием функции расширения массива).,* При при переполнении очереди требуется перевыделение памяти и копирование всех элементов в новый массив.
== Реализация на списке ==
Реализация очереди на односвязном списке:
=== List ===
* <code>ListItem(data : '''T''', next : '''ListItem''')</code> {{---}} конструктор,* <tex>\mathtt{x.value}</tex> {{---}} поле, в котором хранится значение элемента,* <tex>\mathtt{x.next}</tex> {{---}} указатель на следующий элемент очереди.
=== push ===
'''Плюсы:'''
* Каждая каждая операция выполняется за время <tex>O(1)</tex>.
'''Минусы:'''
* Память память фрагментируется гораздо сильнее и последовательная итерация по такой очереди может быть ощутимо медленнее, нежели итерация по очереди реализованной на массиве.
== Реализация на двух стеках ==
Очередь можно реализовать на двух [[Стек|стеках]] <tex>\mathtt{leftStack}</tex> и <tex>\mathtt{rightStack}</tex>. Поступим следующим образом: <tex>\mathtt{leftStack}</tex> будем использовать для операции <tex> \mathtt {push} </tex>, <tex>\mathtt{rightStack}</tex> для операции <tex> \mathtt{pop} </tex>. При этом, если при попытке извлечения элемента из <tex>\mathtt{rightStack}</tex> он оказался пустым, просто перенесем все элементы из <tex>\mathtt{leftStack}</tex> в него (при этом элементы в <tex>\mathtt{rightStack}</tex> получатся уже в обратном порядке, что нам и нужно для извлечения элементов, а <tex>\mathtt{leftStack}</tex> станет пустым).
* <tex> \mathtt{pushLeft} </tex> и <tex> \mathtt{pushRight} </tex> {{---}} функции, реализующие операцию <tex> \mathtt{push} </tex> для соответствующего стека; ,
* <tex> \mathtt{popLeft} </tex> и <tex> \mathtt{popRight} </tex> {{---}} аналогично операции <tex> \mathtt {pop} </tex>.
'''Плюсы:'''
* Эту эту реализацию несложно модифицировать для получения минимума в текущей очереди за <tex>O(1)</tex>.
'''Минусы:'''
* Если если <tex>\mathtt{leftStack}</tex> не пуст, то операция <tex> \mathtt{pop} </tex> может выполняться <tex>O(n)</tex> времени, в отличии от других реализаций, где <tex> \mathtt{pop} </tex> всегда выполняется за <tex>O(1)</tex>.
== Реализация на шести стеках ==
=== Отличия от других реализаций ===
'''Плюсы:''':* <tex>O(1)</tex> реального времени на операцию.,* Возможность возможность дальнейшего улучшения до [[Персистентная очередь|персистентной очереди]], если использовать [[Персистентный стек|персистентные стеки]].
'''Минусы:''':* Дольше дольше в среднем выполняются операции.,* Больше больше расход памяти.,* Большая большая сложность реализации.
== См. также ==
