* Если <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_1, либо два персистентных и три обычных. Рассмотрим последний вариант как более простойL_2, R, Rc_1, Rc_2, T</tex>, причем стеки <tex>L_1, L_2</tex> используются для операций <tex>push</tex>, стек <tex>R</tex> используется для операций <tex>pop</tex>, стеки <tex>Rc_1, Rc_2</tex> используются в качестве копий стека <tex>R</tex>, стек <tex>T</tex> используется для перекопирования элементов.
Пусть мы имеем стеки В каждый момент времени в очереди зафиксировано какой <tex>L, L', R, R', T</tex>, причем стеки из стеков <tex>LL_1</tex> и <tex>L'L_2</tex> используются используется для операций помещения туда элементов, пришедших с операцией <tex>push</tex>, персистентные стеки а также какой <tex>RRc</tex> и из стеков <tex>R'Rс_1</tex> используются для операций и <tex>popRс_2</tex>, а стек является в данный момент точной копией стека <tex>TR</tex> используется для перекопирования элементов.
В каждый момент времени Также очередь будет запоминать, находится ли она сейчас в режиме перекопирования (''recopy mode''), в очереди зафиксировано какой <tex>Lcur</tex> который переходит из стеков <tex>L</tex> и обычного режима, когда после очередной операции в стеке <tex>L'</tex> используется для помещения туда становится больше элементов, пришедших с операцией <tex>push</tex>, а также какой <tex>Rcur</tex> из стеков чем в стеке <tex>R</tex> и . При активации инициализируется счетчик <tex>R'toCopy</tex> используется для извлечения оттуда , показывающий, сколько находится неизвлеченных элементов, запрашиваемых операцией в стеке <tex>popRc</tex>.
Очередь будет работать Пусть в двух режимах:# Обычный режимэтот момент в стеке <tex>R</tex>, аналогично реализации на двух стеках.# Режим перекопирования (''recopy mode''). Этот режим активируется, когда при очередной операции в обычном режиме а значит и в стеке <tex>LcurRc</tex> находились <tex>n</tex> становится больше элементов, чем тогда в стеке <tex>RcurL</tex> их <tex>n+1</tex>. Обрабатываем поступающие дальше операции следующим образом: <tex>push</tex> кладет элемент в парный нашему стеку <tex>L</tex> стек <tex>L'</tex>, а <tex>pop</tex> извлекает элемент только из <tex>Rc</tex>, при этом уменьшая счетчик <tex>toCopy</tex>.
При активации режима перекопирования:* Инициализируется счетчик Заметим, что мы можем корректно обработать все операции <tex>toCopy=Rcur.size+Lcur.sizepush</tex>, который означает, сколько элементов нужно будет скопировать из и первые <tex>Tn</tex>.* Текущий стек для операций <tex>pushpop</tex> меняется с , то есть у нас есть на перекопирование не меньше <tex>Lcurn+1</tex> на другой стекоперации вместе с активирующей.
В режиме перекопирования на каждую операцию выполняются дополнительные действия. Поскольку Корректной ситуация станет, когда в этом режиме остаются корректными все операции стеках <tex>pushR</tex> и <tex>Rcur.size</tex> операций <tex>pop</tex>, которые мы сможем выполнить на персистентном парном стеке <tex>RcurRc'</tex>, можно предполагать, что окажутся все находящиеся на перекопирование у нас есть по крайней мере <tex>n + 1 = Rcur.size + 1</tex> операций, включая ту, которая активировала этот режиммомент активации в очереди и не извлеченные после активации элементы.
Суммарно за эти операции мы должны сделатьЧтобы получить корректную ситуацию и перейти в обычный режим, нужно:# Перемещение содержимого стека Извлечь весь стек <tex>L</tex> в стеки <tex>R, Rc'</tex>, <tex>n+1</tex> действие.# Извлечь весь стек <tex>RcurR</tex> в стек <tex>T</tex>, это <tex>n</tex> операцийдействий.# Перемещение содержимого стека Извлечь <tex>toCopy</tex> элементов <tex>LcurT</tex> в стек стеки <tex>TR, Rc'</tex>, это а оставшиеся выкинуть, <tex>n + 1</tex> операциядействий.# Перемещение содержимого Назначить <tex>Rc'</tex> текущей копией стека <tex>TR</tex>, а <tex>L'</tex> во второй стек {{---}} текущим стеком для извлеченияопераций <tex>push</tex>, это <tex>2 \cdot n + 1</tex> операцийдействия.
Счетчик Таким образом, получили <tex>toCopy3 \cdot n + 3</tex> уменьшается в двух случаях:* Мы переместили часть содержимого действий на <tex>Tn + 1</tex> в стек для извлеченияопераций с очередью, то есть выполняя 3 дополнительных действия во время операции мы успеем перекопировать все элементы вовремя.* Нам пришел запрос <tex>pop</tex> и мы уменьшили Тогда очередь действительно будет выполнять каждое действие за <tex>toCopy</tex> на O(1, чтобы показать, что один из элементов <tex>Rcur</tex> на дне <tex>T)</tex> уже был извлеченреального времени.
Итого имеем суммарно Теперь рассмотрим, какие изменения произошли за время перекопирования. Пусть среди <tex>n</tex> следующих за активацией операций у нас <tex>4 x</tex> операций <tex>pop</tex> и <tex>n-x</tex> операций <tex>push</tex>. Тогда в стеке <tex>R</tex> оказалось <tex>2 \cdot n + 21 - x</tex> дополнительные стековые операцииэлементов, которые мы должны сделать за а в новом стеке <tex>L</tex> оказалось <tex>n - x</tex> элементов. Тогда в стеке <tex>R</tex> на <tex>n + 1</tex> операцийбольше элементов, чем в стеке <tex>L</tex>, а это значит, то есть что до следующего режима перекопирования <tex>4n + 2</tex> дополнительных операции на одну обычную, что означает и за это время мы успеем очистить старый стек <tex>Rc</tex>, в котором находится максимум <tex>n</tex> ненужных элементов, просто удаляя при каждой операции в обычном режиме один элемент из <tex>O(1)Rc</tex> истинного времени на операцию, если он непуст.
