120
правок
Изменения
Нет описания правки
Теперь проверим корректность условия активации. Пусть среди <tex>n</tex> следующих за активацией операций <tex>push, pop</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>n + 1</tex> элемент меньше, чем в стеке <tex>R</tex>, а значит до следующего перекопирования <tex>n+2</tex> операции.
Заметим, что теперь если очередь находится в обычном режиме, <tex>L.size \leqslant R.size</tex>, значит <tex>empty=(R.size=0)</tex>.
Итак, очередь <tex>Q</tex> будет состоять из шести стеков <tex>L,L',R,R',T</tex>, а также двух внутренних переменных <tex>recopy, toCopy</tex>, которые нужны для корректности перекопирования.
Инвариант очереди (обычный режим):
# Стек <tex>L</tex> содержит левую половину очереди, порядок при извлечении обратный.
# Стек <tex>R</tex> содержит правую половину очереди, порядок при извлечении прямой.
# <tex>L.size \leqslant R.size</tex>
# <tex>R.size = 0 \equiv Q.size = 0</tex>
# <tex>L'.size = 0, T.size = 0</tex>
Инвариант очереди (режим перекопирования):
# Если <tex>L.size = 0</tex>, то первые <tex>toCopy</tex> элементов <tex>T</tex> {{---}} корректны, то есть действительно содержатся в очереди.
Очередь будет работать в двух режимах:
# Обычный режим, кладем в <tex>L</tex>, извлекаем из <tex>R</tex>, операция <tex>empty = (R.size = 0)</tex>.
# Режим перекопирования, кладем в <tex>L'</tex>, извлекаем из <tex>R'</tex>, <tex>empty=false</tex>, совершаем дополнительные действия.
Также после операции в обычном режиме следует проверка на активацию перекопирования(<tex>recopy = (L.size > R.size)</tex>), если это так, <tex>toCopy=R.size, recopy=true, R'=R</tex>, совершается первый набор дополнительных действий.
После операции в режиме перекопирования следует проверка на завершение перекопирования (<tex>recopy=T.size==0</tex>), а при завершении меняются ролями стеки <tex>L, L'</tex>.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]
