120
правок
Изменения
м
→Реализация на шести стеках
Пусть мы имеем стеки <tex>L_1, L_2, R, Rc_1, Rc_2, T</tex>, причем стеки <tex>L_1, L_2</tex> используются для операций <tex>push</tex>, стек <tex>R</tex> используется для операций <tex>pop</tex>, стеки <tex>Rc_1, Rc_2</tex> используются в качестве копий стека <tex>R</tex>, стек <tex>T</tex> используется для перекопирования элементов.
В каждый момент времени в очереди зафиксировано какой <tex>L</tex> из стеков <tex>L_1</tex> и <tex>L_2</tex> используется для помещения туда элементов, пришедших с операцией <tex>push</tex>, а также какой <tex>Rc</tex> из стеков <tex>Rс_1Rc_1</tex> и <tex>Rс_2Rc_2</tex> является в данный момент точной копией стека <tex>R</tex>.
Также очередь будет запоминать, находится ли она сейчас в режиме перекопирования (''recopy mode''), в который переходит из обычного режима, когда после очередной операции в стеке <tex>L</tex> становится больше элементов, чем в стеке <tex>R</tex>. При активации инициализируется счетчик <tex>toCopy</tex>, показывающий, сколько находится неизвлеченных элементов в стеке <tex>Rc</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>L</tex> находится не больше элементов, чем в <tex>R</tex>, так что проверка на пустоту очереди при обычном режиме сводится к проверке на пустоту стека <tex>R</tex>.
Пусть наша очередь <tex>Q</tex> имеет стеки <tex>L1, L2, R, Rc1, Rc2, T</tex>, а также переменные <tex>recopy</tex> и <tex>toCopy</tex>, тогда вышеприведенный алгоритм реализует следующий псевдокод:
additionalOperations()
// Нас Нам достаточно 3 операций на вызов
toDo = 3
// Пытаемся перекопировать R в T
toDo = toDo - 1
// Если все скопировано, то меняем роли L1, L2 и Rc1, Rc2
if toDo > T.size = 0
swap(L1, L2)
swap(Rc1, Rc2)
