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

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

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

Будем отталкиваться от реализации на двух стеках. Пусть у нас есть стек [math]L[/math] для операций [math]push[/math], стек [math]R[/math] для операций [math]pop[/math]. К моменту опустошения стека [math]R[/math] нам нужно получить стек [math]R'[/math], содержащий все элементы стека [math]L[/math] в правильном для извлечения порядке. Этого можно добиться, если переместить все элементы стека [math]L[/math], в стек [math]R'[/math], назовем такой процесс перекопированием, а очередь будет в это время находится в режиме перекопирования (recopy mode). Режим перекопирования активируется, когда во время очередной операции мы уже можем не успеть переместить нужные элементы, а именно [math]L.size\gt R.size[/math]. Состояние очереди будет фиксировать логическая переменная [math]recopy[/math].

Теперь рассмотрим как обрабатывать операции во время перекопирования. В режиме перекопирования операция [math]empty=false[/math], так как мы не можем извлекать элементы, находившиеся в не пустом стеке [math]L[/math], значит очередь всегда не пуста. Договоримся также, что операция [math]empty[/math] не меняет внутреннюю структуру очереди и не создает новой версии очереди.

Поскольку стек [math]L[/math] во время перемещения содержимого теряет свою структуру, мы не сможем положить туда элементы, пришедшие с [math]push[/math]. Для таких элементов заведем специальный стек [math]L'[/math] в который будем складывать поступающие элементы, а после перекопирования обменяем его ролями с [math]L[/math].

Этот алгоритм почти работает, но есть проблема: никто не гарантирует, что стек [math]R[/math] опустошится за время перекопирования, то есть мы получим в итоге два стека с выходными данными, а значит во время следующего перекопирования у нас может не быть свободного стека (например, если все операции были [math]push[/math]). Избавимся от этой проблемы следующим образом: мы принудительно извлечем все элементы стека [math]R[/math] во вспомогательный стек [math]T[/math], затем переместим все элементы стека [math]L[/math] в стек [math]R[/math], затем обратно переместим все элементы [math]T[/math] в стек [math]R[/math]. Легко показать, что такая последовательность действий приведет к правильному для извлечения порядку элементов в [math]R[/math].

Теперь разберемся с операциями [math]pop[/math]. Теперь у нас теряет свою структуру стек [math]R[/math], значит нужна его копия для извлечения элементов. Без персистентности нам бы пришлось создавать такую копию параллельно с самим стеком [math]R[/math], но теперь мы можем просто записать в [math]R'[/math] последнюю версию стека [math]R[/math] и дальше извлекать элементы уже из нее. Чтобы учесть извлеченные из копии элементы, будем использовать переменную [math]toCopy=R'.size[/math], будем уменьшать ее на [math]1[/math] при каждом извлечении из [math]T[/math] и операциях [math]pop[/math]. Так как извлеченные элементы будут нарастать со дна стека [math]T[/math], мы никогда не извлечем некорректный элемент, если [math]toCopy\gt 0[/math].

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

Всего в режиме перекопирования нужно:

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