После того, как мы получили [[Очередь#Реализация на шести стеках|очередь в реальном времени]] с <tex>O(1)=6</tex> обычными [[Стек|стеками]], ее можно легко превратить в персистентную, сделав все стеки [[Персистентный стек|персистентными]], но реально можно ограничиться на самом деле персистентность позволяет не создавать явной копии стека, так что достаточно всего пятью персистентными стекамипяти стеков.
== Эффективная реализация ==
По сравнению с реализацией Будем отталкиваться от реализации на шести [[Очередь#Реализация на двух стеках, теперь |двух стеках]]. Пусть у нас все стеки персистентныеесть стек <tex>L</tex> для операций <tex>push</tex>, а значит у нас нет необходимости хранить отдельно копию стек <tex>R</tex> для операций <tex>pop</tex>.К моменту опустошения стека <tex>R</tex> нам нужно получить стек <tex>R'</tex>, так как содержащий все его версии теперь доступны по его персистентностиэлементы стека <tex>L</tex> в правильном для извлечения порядке. Это позволяет нам заменить два Этого можно добиться, если переместить все элементы стека <tex>Rc_1, Rc_2L</tex> на один , в стек <tex>R_2R'</tex>, назовем такой процесс перекопированием, а очередь будет в это время находится в который режиме перекопирования (''recopy mode''). Режим перекопирования активируется, когда во время очередной операции мы и будем записывать перекопированный кусокуже можем не успеть переместить нужные элементы, а именно <tex>L.size>R.size</tex>. Состояние очереди будет фиксировать логическая переменная <tex>recopy</tex>.
Персистентная очередь будет состоять из пяти персистентных стеков: Теперь рассмотрим как обрабатывать операции во время перекопирования. В режиме перекопирования операция <tex>L_1, L_2, R_1, R_2, Tempty=false</tex>, причем стеки <tex>L_1так как мы не можем извлекать элементы, L_2</tex> используются для операций находившиеся в не пустом стеке <tex>pushL</tex>, стеки <tex>R_1, R_2</tex> используются для операций <tex>pop</tex>, а стек <tex>T</tex> используется для временного хранения содержимого стека <tex>R</tex>значит очередь всегда не пуста.
В каждый момент времени определено, какой Поскольку стек <tex>L</tex> из стеков <tex>L_1во время перемещения содержимого теряет свою структуру, мы не сможем положить туда элементы, L_2</tex> сейчас используется для операций пришедшие с <tex>push</tex>, какой . Для таких элементов заведем специальный стек <tex>RL'</tex> из стеков <tex>R_1в который будем складывать поступающие элементы, R_2а после перекопирования обменяем его ролями с </tex> сейчас используется для операций <tex>popL</tex>, а также находится ли очередь в режиме перекопирования (''recopy mode'').
В режиме перекопирования операции Этот алгоритм почти работает, но есть проблема: никто не гарантирует, что стек <tex>pushR</tex> перенаправляются опустошится за время перекопирования, то есть мы получим в парный стек итоге два стека с выходными данными, а значит во время следующего перекопирования у нас может не быть свободного стека (например, если все операции были <tex>L'push</tex>; операции ). Избавимся от этой проблемы следующим образом: мы принудительно извлечем все элементы стека <tex>popR</tex> выполняются над последней персистентной версией во вспомогательный стек <tex>RT</tex>, тогда операция затем переместим все элементы стека <tex>emptyL</tex> всегда возвращает в стек <tex>falseR</tex>, так как стек затем обратно переместим все элементы <tex>LT</tex> содержит в стек <tex>n+1>0R</tex> элементов. Легко показать, а что такая последовательность действий получит в режиме перекопирования мы не можем извлечь их операцией стеке <tex>popR</tex>все элементы в правильном порядке.
Для хранения последней персистентной версии Теперь разберемся с операциями <tex>pop</tex>. Теперь у нас теряет свою структуру стек <tex>R</tex>, значит нужна его копия для извлечения элементов. Без персистентности нам бы пришлось создавать такую копию параллельно с самим стеком <tex>R</tex> , но теперь мы используем второй имеющийся стек можем просто записать в <tex>R'</tex>, а также переменную последнюю версию стека <tex>toCopyR</tex> {{---}} количество элементови дальше извлекать элементы уже из нее. Чтобы учесть извлеченные из копии элементы, оставшихся в будем использовать переменную <tex>toCopy=R'.size</tex>, оно уменьшается будем уменьшать ее на <tex>1</tex> с каждой следующей операцией при каждом извлечении из <tex>T</tex> и операциях <tex>pop</tex>. Так как извлеченные элементы будут нарастать со дна стека <tex>T</tex>, мы никогда не извлечем некорректный элемент, если <tex>toCopy>0</tex>.
Режим перекопирования активируется, когда в стеке <tex>L</tex> становится больше элементов, чем в стеке <tex>R</tex>. Пусть в стеке <tex>R</tex> в этот момент находилось <tex>n</tex> элементов, тогда в стеке <tex>L</tex> находилось <tex>n+1</tex> элементов. Заметим, что мы можем корректно обработать только <tex>n</tex> запросов <tex>pop</tex>, операции <tex>push</tex> и <tex>empty</tex> мы обрабатываем корректно всегда, следовательно мы должны закончить перекопирование за <tex>n+1</tex> операцию, включая активирующую.
Для завершения перекопирования нужно:
# Переместить все содержимое стека <tex>R</tex> в <tex>T</tex>, <tex>n</tex> операций.
# Переместить все содержимое стека <tex>L</tex> в <tex>R</tex>, <tex>n + 1</tex> операция.
# Переместить первые <tex>toCopy</tex> элементов стека <tex>T</tex> в <tex>R</tex>, а оставшиеся элементы выкинуть, <tex>n</tex> операций.
# Обменять местами стеки <tex>L</tex> и <tex>L'</tex>, <tex>2</tex> операции.
Итого, мы должны сделать <tex>3 \cdot n + 3</tex> дополнительных действия за <tex>n + 1</tex> операций, то есть выполняя <tex>O(1)=3</tex> дополнительных действия на операцию, мы сможем завершить перекопирование и вернуться в обычный режим до исчерпания стека <tex>R'</tex>, получив <tex>O(1)</tex> реального времени и <tex>O(1)</tex> памяти на персистентность на операцию.
Теперь рассмотрим, какие изменения произошли за время перекопирования. Пусть среди <tex>n</tex> следующих за активацией операций у нас <tex>x</tex> операций <tex>pop</tex> и <tex>n-x</tex> операций <tex>push</tex>. Тогда в стеке <tex>R</tex> оказалось <tex>2 \cdot n + 1 - x</tex> элементов, а в новом стеке <tex>L</tex> оказалось <tex>n - x</tex> элементов. Тогда в стеке <tex>R</tex> на <tex>n+1</tex> больше элементов, чем в стеке <tex>L</tex>, а это значит, что до следующего режима перекопирования <tex>n + 2</tex> операции, и за это время мы успеем очистить старый стек <tex>Rc</tex>, в котором находится максимум <tex>n</tex> ненужных элементов, просто удаляя при каждой операции в обычном режиме один элемент из <tex>Rc</tex>, если он не пустой.
Заметим, что вышеприведенный алгоритм гарантирует нам, что в обычном режиме в стеке <tex>L</tex> находится не больше элементов, чем в <tex>R</tex>, так что проверка на пустоту очереди при обычном режиме сводится к проверке на пустоту стека <tex>R</tex>.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]
