120
правок
Изменения
Нет описания правки
К моменту опустошения стека <tex>R</tex> нам нужно получить стек <tex>R'</tex>, содержащий все элементы стека <tex>L</tex> в правильном для извлечения порядке. Этого можно добиться, если переместить все элементы стека <tex>L</tex>, в стек <tex>R'</tex>, назовем такой процесс перекопированием, а очередь будет в это время находится в режиме перекопирования (''recopy mode''). Режим перекопирования активируется, когда во время очередной операции мы уже можем не успеть переместить нужные элементы, а именно <tex>L.size>R.size</tex>. Состояние очереди будет фиксировать логическая переменная <tex>recopy</tex>.
Теперь рассмотрим как обрабатывать операции во время перекопирования. В режиме перекопирования операция <tex>empty=false</tex>, так как мы не можем извлекать элементы, находившиеся в не пустом стеке <tex>L</tex>, значит очередь всегда не пуста. Договоримся также, что операция <tex>empty</tex> не меняет внутреннюю структуру очереди и не создает новой версии очереди.
Поскольку стек <tex>L</tex> во время перемещения содержимого теряет свою структуру, мы не сможем положить туда элементы, пришедшие с <tex>push</tex>. Для таких элементов заведем специальный стек <tex>L'</tex> в который будем складывать поступающие элементы, а после перекопирования обменяем его ролями с <tex>L</tex>.
Этот алгоритм почти работает, но есть проблема: никто не гарантирует, что стек <tex>R</tex> опустошится за время перекопирования, то есть мы получим в итоге два стека с выходными данными, а значит во время следующего перекопирования у нас может не быть свободного стека (например, если все операции были <tex>push</tex>). Избавимся от этой проблемы следующим образом: мы принудительно извлечем все элементы стека <tex>R</tex> во вспомогательный стек <tex>T</tex>, затем переместим все элементы стека <tex>L</tex> в стек <tex>R</tex>, затем обратно переместим все элементы <tex>T</tex> в стек <tex>R</tex>. Легко показать, что такая последовательность действий получит приведет к правильному для извлечения порядку элементов в стеке <tex>R</tex> все элементы в правильном порядке.
Теперь разберемся с операциями <tex>pop</tex>. Теперь у нас теряет свою структуру стек <tex>R</tex>, значит нужна его копия для извлечения элементов. Без персистентности нам бы пришлось создавать такую копию параллельно с самим стеком <tex>R</tex>, но теперь мы можем просто записать в <tex>R'</tex> последнюю версию стека <tex>R</tex> и дальше извлекать элементы уже из нее. Чтобы учесть извлеченные из копии элементы, будем использовать переменную <tex>toCopy=R'.size</tex>, будем уменьшать ее на <tex>1</tex> при каждом извлечении из <tex>T</tex> и операциях <tex>pop</tex>. Так как извлеченные элементы будут нарастать со дна стека <tex>T</tex>, мы никогда не извлечем некорректный элемент, если <tex>toCopy>0</tex>.
Теперь проанализируем наш алгоритм. Пусть в стеке <tex>R</tex> на начало перекопирования содержатся <tex>n</tex> элементов, тогда в стеке <tex>R</tex> находится <tex>n+1</tex> элемент. Мы можем корректно обработать все операции <tex>push</tex>, а также <tex>n</tex> операций <tex>pop</tex>, операции <tex>empty</tex> мы не учитываем. Тогда мы должны завершить перекопирование не больше, чем за <tex>n+1</tex> операцию.
Всего в режиме перекопирования нужно:
# Переместить содержимое <tex>R</tex> в <tex>T</tex>, <tex>n</tex>времени, <tex>n</tex> памяти.
# Переместить содержимое <tex>L</tex> в <tex>R</tex>, <tex>n+1</tex>, <tex>n+1</tex>
# Переместить первые <tex>toCopy</tex> элементов из стека <tex>T</tex> в стек <tex>R</tex>, остальные выкинуть.
# Поменять ролями стеки <tex>L, L'</tex>.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]
