120
правок
Изменения
→Реализация на шести стеках: правки
Теперь может возникнуть проблема с непустым <tex>Rc</tex> после завершения перекопирования. Покажем, что мы всегда успеем его опустошить, если будем использовать дополнительное извлечение из него при каждой операции в обычном режиме, для этого полностью проанализируем алгоритм.
Пусть на начало перекопирования в стеке <tex>R</tex> содержится <tex>n</tex> элементов, тогда в стеке <tex>L</tex> находится <tex>n+1</tex> элементов. Мы корректно можем обработать любой любое количество операций <tex>push</tex>, а также <tex>n</tex> операций <tex>pop<tex>. Заметим, что операция <tex>empty</tex> во время перекопирования всегда возвращает <tex>false</tex>, так как мы не можем извлекать элементы из стека <tex>L</tex>, который не пустой. Таким образом, вместе с операцией, активирующей перекопирование, мы гарантированно можем корректно обработать <tex>n + 1</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>3 \cdot n + 3</tex> дополнительных действия за <tex>n + 1</tex> операций, или <tex>3=O(1)</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>L</tex> <tex>n-x</tex>, элементов в <tex>RL</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>L.size \leqslant R.size</tex>
# <tex>R.size = 0 \equiv Q.size = 0</tex>
# <tex>Rc</tex> {{---}} копия <tex>R</tex>
# <tex>Rc'.size < R.size - L.size</tex># <tex>L'.size = 0, T.size = 0</tex>
Инвариант очереди (режим перекопирования):
# <tex>Rc.size = toCopy</tex>
# Если <tex>L.size = 0</tex>, то первые <tex>toCopy</tex> элементов <tex>T</tex> {{---}} корректны, то есть действительно содержатся в очереди.
Пусть наша очередь <tex>Q</tex> имеет стеки <tex>L1L, L2L', R, Rc1Rc, Rc2Rc', T</tex>, а также переменные <tex>recopy</tex> и <tex>toCopy</tex>, тогда следующий псевдокод выполняет требуемые операции.
=== empty ===
<code>
push(x)
if !recopy
checkRecopy()
else
checkNormal()
</code>
if !recopy
tmp = R.pop()
checkRecopy()
return tmp
else
tmp = Rc1Rc.pop()
toCopy = toCopy - 1
checkNormal()
=== checkRecopy ===
<code>
checkRecopy() if Rc2.size > 0 Rc2.pop() recopy = L1L.size > R.size
if recopy
toCopy = Rc1R.size
additionalOperations()
</code>
T.push(R.pop())
toDo = toDo - 1
// Пытаемся перекопировать L1 L в R и Rc2Rc'
while toDo > 0 and L1.size > 0
x = L1L.pop()
R.push(x)
toDo = toDo - 1
// Пытаемся перекопировать T в R и Rc2 Rc' с учетом toCopy
while toDo > 0 and T.size > 0
x = T.pop()
if toCopy > 0
R.push(x)
toCopy = toCopy - 1
toDo = toDo - 1
// Если все скопировано, то меняем роли L1, L2 и Rc1, Rc2
if T.size = 0
swap(L1L, L2L') swap(Rc1Rc, Rc2Rc')
</code>
