120
правок
Изменения
→Эффективная реализация: правка алгоритма
Этот алгоритм почти работает, но есть проблема: никто не гарантирует, что стек <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>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.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=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>, аналогично свою новую версию возвращает и персистентная очередь.
Следующий псевдокод выполняет требуемые операции:
'''if''' !recopy:
Ln = L.push(x)
Q' = <Ln, L', R, R', T, recopy, toCopy, copied>
'''return''' Q'.checkRecopy()
'''else''':
Ln' = L'.push(x)
Q' = <L, Ln', R, R', T, recopy, toCopy, copied>
'''return''' Q'.checkNormal()
</code>
'''if''' !recopy:
<Rn, x> = R.pop()
Q' = <L, L', Rn, R', T, recopy, toCopy, copied>
'''return''' <Q'.checkRecopy(), x>
'''else''':
<Rn', x> = R'.pop()
curCopy = toCopy Rn = R '''if''' toCopy > 0: curCopy = curCopy - 1 '''else''': <Rn, x> = Rn.pop() Q' = <L, L', RRn, Rn', T, recopy, toCopy - 1curCopy, copied>
'''return''' <Q'.checkNormal(), x>
</code>
checkRecopy()
'''if''' L.size > R.size:
Q' = <L, L', R, R', T, true, R.size, false>
'''return''' Q'.checkNormal()
'''else''':
'''return''' <L, L', R, R', T, false, toCopy, copied>
</code>
Q' = Q.additionalOperations()
// Если мы не все перекопировали, то у нас не пуст стек T
return <Q'.L, Q'.L', Q'.R, Q'.R', Q'.T, Q'.T.size <tex> \ne </tex> 0, Q'.toCopy, Q'.copied>
</code>
=== additionalOperations ===
Rn = R
Tn = T
curCopied = copied '''while''' '''not''' curCopied '''and''' toDo > 0 '''and''' Rn.size > 0:
<Rn, x> = Rn.pop()
Tn = Tn.push(x)
// Пытаемся перекопировать L в R
'''while''' toDo > 0 '''and''' Ln.size > 0:
curCopied = true
<Ln, x> = Ln.pop()
Rn = Rn.push(x)
'''if''' T.size == 0:
swap(Ln, Ln')
'''return''' <Ln, Ln', Rn, R', Tn, recopy, curCopy, curCopied>
</code>
