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