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

После того, как мы получили очередь в реальном времени с [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] памяти на персистентность на операцию.

Теперь рассмотрим, какие изменения произошли за время перекопирования. Пусть среди [math]n[/math] следующих за активацией операций у нас [math]x[/math] операций [math]pop[/math] и [math]n-x[/math] операций [math]push[/math]. Тогда в стеке [math]R[/math] оказалось [math]2 \cdot n + 1 - x[/math] элементов, а в новом стеке [math]L[/math] оказалось [math]n - x[/math] элементов. Тогда в стеке [math]R[/math] на [math]n+1[/math] больше элементов, чем в стеке [math]L[/math], а это значит, что до следующего режима перекопирования [math]n + 2[/math] операции, и за это время мы успеем очистить старый стек [math]Rc[/math], в котором находится максимум [math]n[/math] ненужных элементов, просто удаляя при каждой операции в обычном режиме один элемент из [math]Rc[/math], если он не пустой.

Заметим, что вышеприведенный алгоритм гарантирует нам, что в обычном режиме в стеке [math]L[/math] находится не больше элементов, чем в [math]R[/math], так что проверка на пустоту очереди при обычном режиме сводится к проверке на пустоту стека [math]R[/math].