Изменения

После того, как мы получили [[Персистентная очередь#Реализация очереди на шести стеках|очередь в реальном времени]] с <tex>O(1)=6</tex> обычными [[Стек|стеками]], ее можно легко превратить в персистентную, сделав все стеки [[Персистентный стек|персистентными]], но на самом деле персистентность позволяет не создавать явной копии стека<tex>R</tex>, так что достаточно всего пяти стеков.

Будем отталкиваться от реализации на [[Очередь#Реализация на двух стеках|двух стеках]]. Пусть у нас есть стек <tex>LВместо стеков </tex> для операций <tex>push</tex>Rc, стек <tex>RRc'</tex> для операций <tex>pop</tex>.К моменту опустошения стека <tex>R</tex> нам нужно получить персистентная очередь хранит один стек <tex>R'</tex>, содержащий все элементы стека <tex>L</tex> в правильном для извлечения порядке. Этого можно добиться, если переместить все элементы который при активации перекопирования записывается последняя версия стека <tex>L</tex>, в стек <tex>R'</tex>, назовем такой процесс перекопированием, а очередь будет в это время находится в режиме перекопирования (''recopy mode''). Режим перекопирования активируется, когда во время очередной дальнейшем все операции мы уже можем не успеть переместить нужные элементы, а именно <tex>L.size>R.sizepop</tex>обращаются именно к ней. Состояние очереди будет фиксировать логическая переменная Все замечания о <tex>recopytoCopy</tex>остаются в силе.

Теперь рассмотрим как обрабатывать операции во время перекопирования. В режиме перекопирования операция Также нам нет необходимости опустошать стек <tex>empty=falseR'</tex>к моменту перекопирования, так как мы не можем извлекать элементы, находившиеся в не пустом стеке скопировать туда новую версию <tex>LR</tex>, значит очередь всегда не пуста. Договоримся также, что операция мы можем за <tex>emptyO(1)</tex> не меняет внутреннюю структуру очереди и не создает новой версии , а освобождение ячеек памяти бессмысленно, так как они используются в других версиях персистентной очереди.

Поскольку стек В качестве версии очереди мы будем использовать запись <tex>Q=<L</tex> во время перемещения содержимого теряет свою структуру, мы не сможем положить туда элементыL', R, пришедшие с <tex>push</tex>. Для таких элементов заведем специальный стек <tex>LR'</tex> в который будем складывать поступающие элементы, а после перекопирования обменяем его ролями с <texT, recopy, toCopy, copied>L</tex>, содержащую пять версий персистентных стеков и три переменных.

Этот алгоритм почти работает, но есть проблема: никто не гарантирует, что стек <tex>R</tex> опустошится за время перекопирования, то есть мы получим в итоге два стека с выходными данными, а значит во время следующего перекопирования у нас может не быть свободного стека (например, если все операции были <tex>push</tex>). Избавимся от этой проблемы следующим образом: мы принудительно извлечем все элементы стека <tex>R</tex> во вспомогательный стек <tex>T</tex>, затем переместим все элементы стека <tex>L</tex> в стек <tex>R</tex>, затем обратно переместим все элементы <tex>T</tex> в стек <tex>R</tex>. Легко показать, что такая последовательность действий приведет к правильному для извлечения порядку элементов в <tex>R</tex>. Теперь разберемся с операциями <tex>pop</tex>. Теперь у нас теряет свою структуру стек <tex>R</tex>, значит нужна его копия для извлечения элементов. Без персистентности нам бы пришлось создавать такую копию параллельно с самим стеком <tex>R</tex>, но теперь мы можем просто записать в <tex>R'</tex> последнюю версию стека <tex>R</tex> и дальше извлекать элементы уже из нее. Чтобы учесть извлеченные из копии элементы, будем использовать переменную <tex>toCopy=R'.size</tex>, будем уменьшать ее на <tex>1</tex> при каждом извлечении из <tex>T</tex> и операциях <tex>pop</tex>. Так как извлеченные элементы будут нарастать со дна стека <tex>T</tex>, мы никогда не извлечем некорректный элемент, если <tex>toCopy>0</tex>, а при <tex>toCopy \leqslant 0</tex> в стеке <tex>R</tex> будет содержаться весь правый кусок очереди в правильном порядке, так что придется извлечь элемент и из него тоже. Теперь проанализируем наш алгоритм. Пусть в стеке <tex>R</tex> на начало перекопирования содержатся <tex>n</tex> элементов, тогда в стеке <tex>R</tex> находится <tex>n+1</tex> элемент. Мы можем корректно обработать все операции <tex>push</tex>, а также <tex>n</tex> операций <tex>pop</tex>, операции <tex>empty</tex> мы не учитываем. Тогда мы должны завершить перекопирование не больше, чем за <tex>n+1</tex> операцию. Всего в режиме перекопирования нужно:# Переместить содержимое <tex>R</tex> в <tex>T</tex>, <tex>n</tex> времени, <tex>n</tex> памяти.# Переместить содержимое <tex>L</tex> в <tex>R</tex>, <tex>n+1</tex> времени, <tex>n+1</tex> памяти.# Переместить первые <tex>toCopy</tex> элементов из стека <tex>T</tex> в стек <tex>R</tex>, остальные выкинуть, <tex>n</tex> времени, <tex>n</tex> памяти.# Поменять ролями стеки <tex>L, L'</tex>, <tex>1</tex> времени. Таким образом, мы получили <tex>3 \cdot n + 2</tex> времени и <tex>3 \cdot n + 1</tex> памяти на <tex>n + 1</tex> операцию, то есть <tex>3=O(1)</tex> времени и памяти на операцию. Совершая три дополнительных действия вместе с каждой операцией <tex>push, pop</tex> в режиме перекопирования мы гарантируем, что перекопирование завершится до опустошения стека <tex>R'</tex>. Теперь проверим корректность условия активации. Пусть среди <tex>n</tex> следующих за активацией операций <tex>push, pop</tex> присуствует <tex>x</tex> операций <tex>pop</tex> и <tex>n - x</tex> операций <tex>push</tex>. Тогда, очевидно, в стеке <tex>R</tex> окажется <tex>2 \cdot n + 1 - x</tex> элементов, а в стеке <tex>L</tex> станет <tex>n - x</tex> элементов, то есть на <tex>n + 1</tex> элемент меньше, чем в стеке <tex>R</tex>, а значит до следующего перекопирования <tex>n+2</tex> операции. Заметим, что теперь если очередь находится в обычном режиме, <tex>L.size \leqslant R.size</tex>, значит <tex>empty=(R.size==0)</tex>. Итак, очередь <tex>Q</tex> будет состоять из пяти стеков <tex>L,L',R,R',T</tex>, а также двух внутренних переменных <tex>recopy, toCopy</tex>, которые нужны для корректности перекопирования, + дополнительной переменной <tex>copied</tex>, начинали ли мы уже перемещать элементы из стека <tex>L</tex> в <tex>R</tex>, чтобы не начать их перекладывать в <tex>T</tex>. Инвариант очереди (обычный режим):# Стек <tex>L</tex> содержит левую половину очереди, порядок при извлечении обратный.# Стек <tex>R</tex> содержит правую половину очереди, порядок при извлечении прямой.# <tex>L.size \leqslant R.size</tex># <tex>R.size = 0 \equiv Q.size = 0</tex># <tex>L'.size = 0, T.size = 0</tex> Инвариант очереди (режим перекопирования):# Если <tex>L.size = 0</tex>, то:## При <tex>toCopy > 0</tex> первые <tex>toCopy</tex> элементов <tex>T</tex> {{---}} корректны, то есть действительно содержатся в очереди.## При <tex>toCopy \leqslant </tex> стек <tex>R</tex> корректный, то есть содержит все элементы правого куска очереди в правильном порядке. Очередь будет работать в двух режимах:# Обычный режим, кладем в <tex>L</tex>, извлекаем из <tex>R</tex>, операция <tex>empty = (R.size = 0)</tex>.# Режим перекопирования, кладем в <tex>L'</tex>, извлекаем из <tex>R'</tex>, <tex>empty=false</tex>, совершаем дополнительные действия. Также после операции в обычном режиме следует проверка на активацию перекопирования(<tex>recopy = (L.size > R.size)</tex>), если это так, <tex>toCopy=R.size, recopy=true, copied = false, R'=R</tex>, совершается первый набор дополнительных действий. После операции в режиме перекопирования следует проверка на завершение перекопирования (<tex>recopy=(T.size==0)</tex>), а при завершении меняются ролями стеки <tex>L, L'</tex>. В качестве версии очереди мы будем использовать запись <tex>Q=<L, L', R, R', T, recopy, toCopy, copied></tex>, содержащую пять версий стеков и три переменных.Пусть персистентный стек возвращает вместе с обычным результатом работы стека новую версию, то есть операция <tex>S.pop</tex> возвращает <tex><Sn, x></tex>, а операция <tex>S.push</tex> возвращает <tex><Sn></tex>, аналогично свою новую версию вместе с результатом операции возвращает и персистентная очередь.