3622
правки
Изменения
Нет описания правки
Понятно, что во время перекопирования могут поступить операции <tex>push</tex>, а стек <tex>L</tex> в это время потеряет свою структуру, сложить элементы туда мы уже не сможем, значит нужно завести еще один стек <tex>L'</tex>, в который мы и будем складывать новые элементы. После окончания перекопирования мы поменяем ролями <tex>L,L'</tex> и <tex>R,R'</tex>, и вроде бы все станет хорошо.
Однако, если реализовать этот алгоритм, мы получим неприятную вещь: старый стек <tex>R</tex> может и не опустошиться за это время, то есть мы получили два стека с выходными данными, а значит , возможен случай (например, когда если все поступающие операции {{---}} <tex>push</tex>), когда при следующем перекопировании у нас не будет свободного стека для копирования копировании туда элементов <tex>L</tex>. Для преодоления этой проблемы мы принудительно будем извлекать все элементы из стека <tex>R</tex> во вспомогательный стек <tex>T</tex>, затем копировать элементы из стека <tex>L</tex> в <tex>R</tex>, а затем обратно копировать элементы из стека <tex>T</tex> в <tex>R</tex>. Легко показать, что приведенный алгоритм как раз получает на выходе в <tex>R</tex> все элементы стеков <tex>L,R</tex> в правильном порядке.
Но этого еще недостаточно. Если мы принудительно извлекаем элементы из стека <tex>R</tex>, появляются следующие проблемы:
# Что вернуть при операции <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>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>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>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>recopy=T.size==0</tex>), а при завершении меняются ролями стеки <tex>Rc, Rc'</tex>, <tex>L, L'</tex>.
=== empty ===
<code>
empty()
'''return ''' !recopy '''and ''' R.size == 0
</code>
=== push ===
<code>
push(x)
'''if ''' !recopy:
L.push(x)
'''if ''' Rc'.size > 0:
Rc'.pop()
checkRecopy()
'''else''':
L'.push(x)
checkNormal()
<code>
pop()
'''if ''' !recopy:
tmp = R.pop()
Rc.pop()
'''if ''' Rc'.size > 0:
Rc'.pop()
checkRecopy()
'''return ''' tmp '''else''':
tmp = Rc.pop()
toCopy = toCopy - 1
checkNormal()
'''return ''' tmp
</code>
=== checkRecopy ===
checkRecopy()
recopy = L.size > R.size
'''if ''' recopy:
toCopy = R.size
additionalOperations()
additionalOperations()
// Если мы не все перекопировали, то у нас не пуст стек T
recopy = T.size != <tex> \ne </tex> 0
</code>
=== additionalOperations ===
toDo = 3
// Пытаемся перекопировать R в T
'''while ''' toDo > 0 '''and ''' R.size > 0:
T.push(R.pop())
toDo = toDo - 1
// Пытаемся перекопировать L в R и Rc'
'''while ''' toDo > 0 '''and L''' L1.size > 0:
x = L.pop()
R.push(x)
toDo = toDo - 1
// Пытаемся перекопировать T в R и Rc' с учетом toCopy
'''while ''' toDo > 0 '''and ''' T.size > 0:
x = T.pop()
'''if ''' toCopy > 0:
R.push(x)
Rc'.push(x)
toDo = toDo - 1
// Если все скопировано, то меняем роли L1, L2 и Rc1, Rc2
'''if ''' T.size == 0:
swap(L, L')
swap(Rc, Rc')
