120
правок
Изменения
Нет описания правки
Заметим, что теперь если очередь находится в обычном режиме, <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>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>. В качестве версии очереди мы будем использовать запись <tex>Q=<L, L', R, R', T, recopy, toCopy></tex>, содержащую пять версий стеков и две переменных.Пусть персистентный стек возвращает вместе с обычным результатом стека новую версию, то есть операция <tex>S.pop</tex> возвращает <tex><S', x></tex>, а операция <tex>S.push</tex> возвращает <tex><S'></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 ===<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 ===<code> checkRecopy() recopy = L.size > R.size '''if''' recopy: toCopy = R.size additionalOperations()</code>=== checkNormal ===<code> checkNormal() additionalOperations() // Если мы не все перекопировали, то у нас не пуст стек T recopy = T.size <tex> \ne </tex> 0</code>=== additionalOperations ===<code> additionalOperations() // Нам достаточно 3 операций на вызов 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''' L1.size > 0: x = L.pop() R.push(x) Rc'.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) toCopy = toCopy - 1 toDo = toDo - 1 // Если все скопировано, то меняем роли L1, L2 и Rc1, Rc2 '''if''' T.size == 0: swap(L, L') swap(Rc, Rc')</code>
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]
