Персистентная очередь

После того, как мы получили очередь в реальном времени с [math]O(1)=6[/math] обычными стеками, ее можно легко превратить в персистентную, сделав все стеки персистентными, но реально можно ограничиться всего пятью персистентными стеками.

Эффективная реализация

По сравнению с реализацией на шести стеках, теперь у нас все стеки персистентные, а значит у нас нет необходимости хранить отдельно копию стека [math]R[/math], так как все его версии теперь доступны по его персистентности. Это позволяет нам заменить два стека [math]Rc_1, Rc_2[/math] на один стек [math]R_2[/math], в который мы и будем записывать перекопированный кусок.

Персистентная очередь будет состоять из пяти персистентных стеков: [math]L_1, L_2, R_1, R_2, T[/math], причем стеки [math]L_1, L_2[/math] используются для операций [math]push[/math], стеки [math]R_1, R_2[/math] используются для операций [math]pop[/math], а стек [math]T[/math] используется для временного хранения содержимого стека [math]R[/math].

В каждый момент времени определено, какой стек [math]L[/math] из стеков [math]L_1, L_2[/math] сейчас используется для операций [math]push[/math], какой стек [math]R[/math] из стеков [math]R_1, R_2[/math] сейчас используется для операций [math]pop[/math], а также находится ли очередь в режиме перекопирования (recopy mode).

В режиме перекопирования операции [math]push[/math] перенаправляются в парный стек [math]L'[/math]; операции [math]pop[/math] выполняются над последней персистентной версией [math]R[/math], тогда операция [math]empty[/math] всегда возвращает [math]false[/math], так как стек [math]L[/math] содержит [math]n+1\gt 0[/math] элементов, а в режиме перекопирования мы не можем извлечь их операцией [math]pop[/math].

Для хранения последней персистентной версии [math]R[/math] мы используем второй имеющийся стек [math]R'[/math], а также переменную [math]toCopy[/math] — количество элементов, оставшихся в [math]R'[/math], оно уменьшается на [math]1[/math] с каждой следующей операцией [math]pop[/math].

Режим перекопирования активируется, когда в стеке [math]L[/math] становится больше элементов, чем в стеке [math]R[/math]. Пусть в стеке [math]R[/math] в этот момент находилось [math]n[/math] элементов, тогда в стеке [math]L[/math] находилось [math]n+1[/math] элементов. Заметим, что мы можем корректно обработать только [math]n[/math] запросов [math]pop[/math], операции [math]push[/math] и [math]empty[/math] мы обрабатываем корректно всегда, следовательно мы должны закончить перекопирование за [math]n+1[/math] операцию, включая активирующую.

Для заверешения перекопирования нужно:

1. Переместить все содержимое стека [math]R[/math] в [math]T[/math], [math]n[/math] операций.
2. Переместить все содержимое стека [math]L[/math] в [math]R[/math], [math]n + 1[/math] операция.
3. Переместить первые [math]toCopy[/math] элементов стека [math]T[/math] в [math]R[/math], а оставшиеся элементы выкинуть, [math]n[/math] операций.
4. Обменять местами стеки [math]L[/math] и [math]L'[/math], [math]2[/math] операции.

Итого, мы должны сделать [math]3 \cdot n + 3[/math] дополнительных действия за [math]n + 1[/math] операций, то есть выполняя [math]O(1)=3[/math] дополнительных действия на операцию, мы сможем завершить перекопирование и вернуться в обычный режим до исчерпания стека [math]R'[/math], получив [math]O(1)[/math] реального времени и [math]O(1)[/math] памяти на персистентность на операцию.