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