120
правок
Изменения
→Реализация на шести стеках: правки алгоритма (теперь все действительно работает)
# Что вернуть при операции <tex>pop</tex>? Для этого заведем себе стек <tex>Rc</tex> {{---}} копию стека <tex>R</tex>, из которого мы и будем извлекать требуемые элементы.
# Как поддерживать корректность такой копии? Поскольку этот стек нужен только для перекопирования, а во время него он занят, нужна запасная копия <tex>Rc'</tex> для копирования всех элементов, которые мы копируем в <tex>R</tex>, а по окончании перекопирования поменяем ролями стеки <tex>Rc, Rc'</tex>, как мы делали со стеками <tex>L, L'</tex>.
# Как учесть, что во время перекопирования часть элементов была извлечена из <tex>Rc</tex>? Для этого заведем специальную переменную <tex>toCopy</tex>, которая показывает, сколько корректных элементов находится в стеке <tex>T</tex>, и уменьшается при каждом извлечении из <tex>T</tex> или операции <tex>pop</tex>. К счастью, все некорректные элементы будут нарастать со дна стека, так что мы никогда не извлечем некорректный элемент, если <tex>toCopy>0</tex>. Если во время операции <tex>pop</tex> у нас <tex>toCopy = 0</tex>, это означает, что теперь в стеке <tex>R</tex> находится весь правый кусок очереди, так что нам придется извлечь элемент из него.
Теперь может возникнуть проблема с непустым <tex>Rc</tex> после завершения перекопирования. Покажем, что мы всегда успеем его опустошить, если будем использовать дополнительное извлечение из него при каждой операции в обычном режиме, для этого полностью проанализируем алгоритм.
# Переместить содержимое <tex>R</tex> в <tex>T</tex>, <tex>n</tex> действий.
# Переместить содержимое <tex>L</tex> в стеки <tex>R, Rc'</tex>, <tex>n + 1</tex> действий.
# Переместить первые <tex>toCopy</tex> элементов из <tex>T</tex> в <tex>R, Rc'</tex>, остальные выкинуть, <tex>n</tex> действий.
# Поменять ролями стеки <tex>Rc, Rc'</tex>, <tex>L, L'</tex>, <tex>2</tex> действия.
Теперь рассмотрим, как изменились наши стеки за весь период перекопирования. Договоримся, что операция <tex>empty</tex> не меняет очередь, то есть никакие дополнительные действия не совершаются. Пусть за <tex>n</tex> следующих за активацией меняющих операций (<tex>push, pop</tex>) поступило <tex>x</tex> операций <tex>pop</tex>, <tex>n - x</tex> операций <tex>push</tex>. Очевидно, что после перекопирования в новых стеках окажется: <tex>n-x</tex> элементов в <tex>L</tex>, <tex>2 \cdot n + 1 - x = (n - x) + (n + 1)</tex> элементов в <tex>R</tex>, то есть до следующего перекопирования еще <tex>n+2</tex> операции. С другой стороны, стек <tex>Rc</tex> содержал всего <tex>n</tex> элементов, так что мы можем очистить его, просто удаляя по одному элементу при каждой операции в обычном режиме.
Итак, очередь <tex>Q</tex> будет состоять из шести стеков <tex>L,L',R,Rc,Rc',T</tex>, а также двух внутренних переменных <tex>recopy, toCopy</tex>, которые нужны для корректности перекопирования+ дополнительная переменная <tex>copied</tex>, показывающая, перемещали ли мы элементы из стека <tex>L</tex> в стек <tex>R</tex>, чтобы не начать перемещать эти элементы в стек <tex>T</tex>.
Инвариант очереди (обычный режим):
# <tex>Rc'.size < R.size - L.size</tex>
# <tex>L'.size = 0, T.size = 0</tex>
Тогда к следующему перекопированию (<tex>L.size=R.size+1</tex>) мы гарантированно будем иметь пустые стеки <tex>L',T,Rc'</tex>, которые нам понадобятся.
Инвариант очереди (режим перекопирования):
# <tex>Rc.size = toCopy</tex>
# Если <tex>L.size = 0</tex>, то :## При <tex>toCopy > 0</tex> первые <tex>toCopy</tex> элементов <tex>T</tex> {{---}} корректны, то есть действительно содержатся в очереди.## При <tex>toCopy \leqslant 0</tex> стек <tex>R</tex> содержит весь правый кусок очереди в правильном порядке.
Очередь будет работать в двух режимах:
# Обычный режим, кладем в <tex>L</tex>, извлекаем из <tex>R</tex> и из <tex>Rc, Rc'</tex> для поддержания порядка, операция <tex>empty = (R.size = 0)</tex>.
# Режим перекопирования, кладем в <tex>L'</tex>, извлекаем из <tex>Rc</tex>, возможно из <tex>R</tex>, <tex>empty=false</tex>, совершаем дополнительные действия.
Также после операции в обычном режиме следует проверка на активацию перекопирования(<tex>recopy = (L.size > R.size)</tex>), если это так, <tex>toCopy=R.size, recopy=true, copied = false</tex>, совершается первый набор дополнительных действий.
После операции в режиме перекопирования следует проверка на завершение перекопирования (<tex>recopy=(T.size==0)</tex>), а при завершении меняются ролями стеки <tex>Rc, Rc'</tex>, <tex>L, L'</tex>.
Следующий псевдокод выполняет требуемые операции:
'''else''':
tmp = Rc.pop()
'''if''' toCopy > 0: toCopy = toCopy - 1 '''else''': R.pop()
checkNormal()
'''return''' tmp
'''if''' recopy:
toCopy = R.size
copied = false
checkNormal()
</code>
toDo = 3
// Пытаемся перекопировать R в T
'''while''' '''not''' copied '''and''' toDo > 0 '''and''' R.size > 0:
T.push(R.pop())
toDo = toDo - 1
// Пытаемся перекопировать L в R и Rc'
'''while''' toDo > 0 '''and''' L.size > 0:
copied = true
x = L.pop()
R.push(x)
