120
правок
Изменения
Добавлена очередь на стеках в реальном времени
'''Минусы:'''
* Если <tex>leftStack</tex> не пуст, то операция <tex>pop</tex> может выполняться <tex>O(n)</tex> времени, в отличии от других реализаций, где <tex>pop</tex> всегда выполняется за <tex>O(1)</tex>
== Реализация на пяти стеках ==
Одним из минусов реализации на двух стеках является то, что в худшем случае мы тратим <tex>O(n)</tex> времени на операцию. Если распределить время, необходимое для перемещения элементов из одного стека в другой, по операциям, мы получим очередь без худших случаев с <tex>O(1)</tex> истинного времени на операцию.
Для такой очереди можно использовать либо шесть обычных стеков, либо два персистентных и три обычных. Рассмотрим последний вариант как более простой.
Пусть мы имеем стеки <tex>L, L', R, R', T</tex>, причем стеки <tex>L</tex> и <tex>L'</tex> используются для операций <tex>push</tex>, персистентные стеки <tex>R</tex> и <tex>R'</tex> используются для операций <tex>pop</tex>, а стек <tex>T</tex> используется для перекопирования элементов.
В каждый момент времени в очереди зафиксировано какой <tex>Lcur</tex> из стеков <tex>L</tex> и <tex>L'</tex> используется для помещения туда элементов, пришедших с операцией <tex>push</tex>, а также какой <tex>Rcur</tex> из стеков <tex>R</tex> и <tex>R'</tex> используется для извлечения оттуда элементов, запрашиваемых операцией <tex>pop</tex>.
Очередь будет работать в двух режимах:
# Обычный режим, аналогично реализации на двух стеках.
# Режим перекопирования (''recopy mode''). Этот режим активируется, когда при очередной операции в обычном режиме в стеке <tex>Lcur</tex> становится больше элементов, чем в стеке <tex>Rcur</tex>.
При активации режима перекопирования:
* Инициализируется счетчик <tex>toCopy=Rcur.size+Lcur.size</tex>, который означает, сколько элементов нужно будет скопировать из <tex>T</tex>.
* Текущий стек для операций <tex>push</tex> меняется с <tex>Lcur</tex> на другой стек.
В режиме перекопирования на каждую операцию выполняются дополнительные действия. Поскольку в этом режиме остаются корректными все операции <tex>push</tex> и <tex>Rcur.size</tex> операций <tex>pop</tex>, которые мы сможем выполнить на персистентном стеке <tex>Rcur</tex>, можно предполагать, что на перекопирование у нас есть по крайней мере <tex>n + 1 = Rcur.size + 1</tex> операций, включая ту, которая активировала этот режим.
Суммарно за эти операции мы должны сделать:
# Перемещение содержимого стека <tex>Rcur</tex> в стек <tex>T</tex>, это <tex>n</tex> операций.
# Перемещение содержимого стека <tex>Lcur</tex> в стек <tex>T</tex>, это <tex>n + 1</tex> операция.
# Перемещение содержимого стека <tex>T</tex> во второй стек для извлечения, это <tex>2 \cdot n + 1</tex> операций.
Счетчик <tex>toCopy</tex> уменьшается в двух случаях:
* Мы переместили часть содержимого <tex>T</tex> в стек для извлечения.
* Нам пришел запрос <tex>pop</tex> и мы уменьшили <tex>toCopy</tex> на 1, чтобы показать, что один из элементов <tex>Rcur</tex> на дне <tex>T</tex> уже был извлечен.
Итого имеем суммарно <tex>4 \cdot n + 2</tex> дополнительные стековые операции, которые мы должны сделать за <tex>n + 1</tex> операций, то есть <tex>4</tex> дополнительных операции на одну обычную, что означает <tex>O(1)</tex> истинного времени на операцию.
== См. также ==
