120
правок
Изменения
→Персистентная очередь на пяти стеках
В качестве версии очереди мы будем использовать запись <tex>Q=<L, L', R, R', T, recopy, toCopy, copied></tex>, содержащую пять версий персистентных стеков и три переменных.
Пусть персистентный стек возвращает вместе с обычным результатом работы стека новую версию, то есть операция <tex>S.pop</tex> возвращает <tex><Sn, x></tex>, а операция <tex>S.push(x)</tex> возвращает <tex><Sn></tex>, аналогично . Аналогично свою новую версию вместе с результатом операции возвращает и персистентная очередь, то есть <tex>Q.pop</tex> возвращает <tex><Qn, x></tex>, а <tex>Q.push(x)</tex> возвращает <tex>Qn</tex>.
Следующий псевдокод выполняет требуемые операции:
