120
правок
Изменения
псевдокод операций
В качестве версии очереди мы будем использовать запись <tex>Q=<L, L', R, R', T, recopy, toCopy></tex>, содержащую пять версий стеков и две переменных.
Пусть персистентный стек возвращает вместе с обычным результатом стека новую версию, то есть операция <tex>S.pop</tex> возвращает <tex><S'Sn, x></tex>, а операция <tex>S.push</tex> возвращает <tex><S'Sn></tex>, аналогично свою новую версию возвращает и персистентная очередь.
Следующий псевдокод выполняет требуемые операции:
push(x)
'''if''' !recopy:
Ln = L.push(x) Q'= <Ln, L', R, R'if, T, recopy, toCopy> ''' Rcreturn'.size > 0: Rc'' Q'.pop() checkRecopy()
'''else''':
Ln' = L'.push(x) Q' = <L, Ln', R, R', T, recopy, toCopy> '''return''' Q'.checkNormal()
</code>
=== pop ===
pop()
'''if''' !recopy:
'''else''':
</code>
=== checkRecopy ===
<code>
checkRecopy()
</code>
=== checkNormal ===
<code>
checkNormal()
Q' = Q.additionalOperations()
// Если мы не все перекопировали, то у нас не пуст стек T
</code>
=== additionalOperations ===
toDo = 3
// Пытаемся перекопировать R в T
Rn = R Tn = T '''while''' toDo > 0 '''and''' RRn.size > 0: T<Rn, x> = Rn.pushpop(R) Tn = Tn.poppush()x)
toDo = toDo - 1
Ln = L // Пытаемся перекопировать L в R и Rc' '''while''' toDo > 0 '''and''' L1Ln.size > 0: <Ln, x > = LLn.pop() R.push(x) Rc'Rn = Rn.push(x)
toDo = toDo - 1
curCopy = toCopy // Пытаемся перекопировать T в R и Rc' с учетом toCopy '''while''' toDo > 0 '''and''' TTn.size > 0: <Tn, x > = TTn.pop() '''if''' toCopy curCopy > 0: RRn = Rn.push(x) Rc'.push(x) toCopy curCopy = toCopy curCopy - 1
toDo = toDo - 1
Ln' = L' // Если все скопировано, то меняем роли L1, L2 и Rc1, Rc2
'''if''' T.size == 0:
swap(LLn, LLn') swap(Rc '''return''' <Ln, RcLn'), Rn, R', Tn, recopy, curCopy>
</code>
