Изменения

'''Персистентная очередь''' (англ. ''persistent queue'') {{---}} это [[Очередь|очередь]], реализующая [[Персистентные структуры данных|персистентность]], то есть позволяющая получить доступ ко всем своим предыдущим версиям. Как будет показано далее, можно реализовать функциональную персистентность, то есть каждая ячейка памяти в такой структуре будет инициализирована один раз и в дальнейшем не изменятьсяизменится.

== Основная идея ==

Для создания персистентной очереди очень удобно пользоваться ее реализацией на [[Стек|стеках]], поскольку стеки легко сделать [[Персистентный стек|персистентными]], причем в этом случае мы добьемся функциональной персистентности. [[Очередь#Реализация на двух стеках|Реализация на двух стеках ]] не подходит для этого, так как в худшем сучае случае требует <tex>O(n)</tex> времени, а значит и <tex>O(n)</tex> памяти на операцию в случае персистентности на операцию. Покажем сначала , как создать очередь в реальном времени с <tex>O(1)</tex> времени на операцию, а затем превратим ее в персистентную.

Сначала будем действовать аналогично случаю с двумя стеками. Пусть у нас есть стек <tex>L</tex> для операций <tex>\mathtt{push}</tex> и стек <tex>R</tex> для операций <tex>\mathtt{pop}</tex>. К моменту опустошения стека <tex>R</tex> нам нужно успеть получить стек <tex>R'</tex>, содержащий текущие элементы стека <tex>L</tex> в правильном для извлечения порядке. Перекопирование (''recopy mode'') начнется, когда появится опасность того, что мы не сможем за оставшиеся <tex>R.size</tex> операций <tex>\mathtt{pop}</tex> со стеком <tex>R</tex> перекопировать стек <tex>L</tex> в новый стек <tex>R'</tex>. Очевидно, это ситуация <tex>L.size>R.size</tex>, пусть такое состояние отражает специальная переменная логического типа <tex>\mathtt{recopy}</tex>.

Понятно, что во время перекопирования могут поступить операции <tex>\mathtt{push}</tex>, а стек <tex>L</tex> в это время потеряет свою структуру, сложить элементы туда мы уже не сможем, значит нужно завести еще один стек <tex>L'</tex>, в который мы и будем складывать новые элементы. После окончания перекопирования мы поменяем ролями <tex>L,L'</tex> и <tex>R,R'</tex>, и вроде бы на первый взгляд, все станет хорошо.

Однако, если реализовать этот алгоритм, мы получим неприятную вещь: старый стек <tex>R</tex> может и не опустошиться за это время, то есть мы получили два стека с выходными данными, а значит, возможен случай (например, если все поступающие операции {{---}} <tex>\mathtt{push}</tex>), когда при следующем перекопировании у нас не будет свободного стека для копировании туда элементов <tex>L</tex>. Для преодоления этой проблемы мы принудительно будем извлекать все элементы из стека <tex>R</tex> во вспомогательный стек <tex>TS</tex>, затем копировать элементы из стека <tex>L</tex> в <tex>R</tex>, а затем обратно копировать элементы из стека <tex>TS</tex> в <tex>R</tex>. Легко показать, что приведенный алгоритм как раз получает на выходе в <tex>R</tex> все элементы стеков <tex>L,R</tex> в правильном порядке.

# Что вернуть при операции <tex>\mathtt{pop}</tex>? Для этого заведем себе стек <tex>Rc</tex> {{---}} копию стека <tex>R</tex>, из которого мы и будем извлекать требуемые элементы.

# Как учесть, что во время перекопирования часть элементов была извлечена из <tex>Rc</tex>? Для этого заведем специальную переменную <tex>\mathtt{toCopy}</tex>, которая показывает, сколько корректных элементов находится в стеке <tex>TS</tex>, и уменьшается при каждом извлечении из <tex>TS</tex> или операции <tex>\mathtt{pop}</tex>. К счастью, все некорректные элементы будут нарастать со дна стека, так что мы никогда не извлечем некорректный элемент, если <tex>\mathtt{toCopy}>0</tex>. Если во время операции <tex>\mathtt{pop}</tex> у нас <tex>\mathtt{toCopy } = 0</tex>, это означает, что теперь в стеке <tex>R</tex> находится весь правый кусок очереди, так что нам придется извлечь элемент из него.

Пусть на начало перекопирования в стеке <tex>R</tex> содержится <tex>n</tex> элементов, тогда в стеке <tex>L</tex> находится <tex>n+1</tex> элементов. Мы корректно можем обработать любое количество операций <tex>\mathtt{push}</tex>, а также <tex>n</tex> операций <tex>\mathtt{pop}</tex>. Заметим, что операция <tex>\mathtt{empty}</tex> во время перекопирования всегда возвращает <tex>false</tex>, так как мы не можем извлекать элементы из стека <tex>L</tex>, который не пустой. Таким образом вместе с операцией, активирующей перекопирование, мы гарантированно можем корректно обработать <tex>n + 1</tex> операцию.

# Переместить содержимое <tex>R</tex> в <tex>TS</tex>, <tex>n</tex> действий.

# Переместить первые <tex>\mathtt{toCopy}</tex> элементов из <tex>TS</tex> в <tex>R, Rc'</tex>, остальные выкинуть, <tex>n</tex> действий.

Таким образом, получили <tex>3 \cdot n + 3</tex> дополнительных действия за <tex>n + 1</tex> операций, или <tex>3=O(1)</tex> дополнительных действий на операцию в режиме перекопирования, что и требовалось.

Теперь рассмотрим, как изменились наши стеки за весь период перекопирования. Договоримся, что операция <tex>\mathtt{empty}</tex> не меняет очередь, то есть никакие дополнительные действия не совершаются. Пусть за <tex>n</tex> следующих за активацией меняющих операций (<tex>\mathtt{push}, \mathtt{pop}</tex>) поступило <tex>x</tex> операций <tex>\mathtt{pop}</tex>, <tex>n - x</tex> операций <tex>\mathtt{push}</tex>. Очевидно, что после перекопирования в новых стеках окажется: <tex>n-x</tex> элементов в <tex>L</tex>, <tex>2 \cdot n + 1 - x = (n - x) + (n + 1)</tex> элементов в <tex>R</tex>, то есть до следующего перекопирования еще <tex>n+2</tex> операции. С другой стороны, стек <tex>Rc</tex> содержал всего <tex>n</tex> элементов, так что мы можем очистить его, просто удаляя по одному элементу при каждой операции в обычном режиме.

Итак, очередь <tex>Q</tex> будет состоять из шести стеков <tex>L,L',R,Rc,Rc',TS</tex>, а также двух внутренних переменных <tex>\mathtt{recopy}, \mathtt{toCopy}</tex>, которые нужны для корректности перекопирования + дополнительная переменная <tex>\mathtt{copied}</tex>, показывающая, перемещали ли мы элементы из стека <tex>L</tex> в стек <tex>R</tex>, чтобы не начать перемещать эти элементы в стек <tex>TS</tex>.

# <tex>L'.size = 0, TS.size = 0</tex>

Тогда к следующему перекопированию (<tex>L.size=R.size+1</tex>) мы гарантированно будем иметь пустые стеки <tex>L',TS,Rc'</tex>, которые нам понадобятся.

# <tex>Rc.size = \mathtt{toCopy}</tex>

## При <tex>\mathtt{toCopy } > 0</tex> первые <tex>\mathtt{toCopy}</tex> элементов <tex>TS</tex> {{---}} корректны, то есть действительно содержатся в очереди.## При <tex>\mathtt{toCopy } \leqslant 0</tex> стек <tex>R</tex> содержит весь правый кусок очереди в правильном порядке.

# Режим перекопирования, кладем в <tex>L'</tex>, извлекаем из <tex>Rc</tex>, возможно из <tex>R</tex>, <tex>\mathtt{empty} =\mathtt{false}</tex>, совершаем дополнительные действия.

Также после операции в обычном режиме следует проверка на активацию перекопирования (<tex>\mathtt{recopy } = (L.size > R.size)</tex>), если это так, <tex>\mathtt{toCopy} =R.size, \mathtt{recopy} =true, \mathtt{copied } = false</tex>, совершается первый набор дополнительных действий.

После операции в режиме перекопирования следует проверка на завершение перекопирования (<tex>\mathtt{recopy} =(TS.size==0)</tex>), а при завершении меняются ролями стеки <tex>Rc, Rc'</tex>, <tex>L, L'</tex>.

'''boolean''' empty():

'''function''' push(x: '''T'''): '''if''' !recopy:

'''if''' Rc'.size > 0:

'''else''':

'''T''' pop(): '''if''' !recopy: '''T''' tmp = R.pop()

'''if''' Rc'.size > 0:

'''else''': '''T''' tmp = Rc.pop() '''if''' toCopy > 0:

'''else''':

'''function''' checkRecopy() :

'''if''' recopy:

'''function''' checkNormal():

<span style="color:#008000">// Если мы не все перекопировали, то у нас не пуст стек TS</span> recopy = TS.size <tex> \ne </tex> 0

'''function''' additionalOperations(): <span style="color:#008000">// Нам достаточно 3 операций на вызов</span> '''int''' toDo = 3 <span style="color:#008000">// Пытаемся перекопировать R в TS</span> '''while''' '''not''' copied '''and''' toDo > 0 '''and''' R.size > 0: TS.push(R.pop())

<span style="color:#008000">// Пытаемся перекопировать L в R и Rc'</span> '''while''' toDo > 0 '''and''' L.size > 0:

'''T''' x = L.pop()

<span style="color:#008000">// Пытаемся перекопировать T S в R и Rc' с учетом toCopy</span> '''while''' toDo > 0 '''and''' TS.size > 0: '''T''' x = TS.pop() '''if''' toCopy > 0:

<span style="color:#008000">// Если все скопировано, то меняем роли L, L' и Rc, Rc'</span> '''if''' TS.size == 0:

После того, как мы получили [[Персистентная очередь#Реализация очереди на шести стеках|очередь в реальном времени]] с <tex>O(1)=6</tex> обычными [[Стек|стеками]], ее можно легко превратить в персистентную, сделав все стеки [[Персистентный стек|персистентными]], но на самом деле персистентность позволяет не создавать явной копии стека<tex>R</tex>, так что достаточно всего пяти стеков.

Будем отталкиваться от реализации на [[Очередь#Реализация на двух стеках|двух стеках]]. Пусть у нас есть стек <tex>LВместо стеков </tex> для операций <tex>push</tex>Rc, стек <tex>RRc'</tex> для операций <tex>pop</tex>.К моменту опустошения стека <tex>R</tex> нам нужно получить персистентная очередь хранит один стек <tex>R'</tex>, содержащий все элементы стека <tex>L</tex> в правильном для извлечения порядке. Этого можно добиться, если переместить все элементы который при активации перекопирования записывается последняя версия стека <tex>L</tex>, в стек <tex>R'</tex>, назовем такой процесс перекопированием, а очередь будет в это время находится в режиме перекопирования (''recopy mode''). Режим перекопирования активируется, когда во время очередной дальнейшем все операции мы уже можем не успеть переместить нужные элементы, а именно <tex>L.size>R.size\mathtt{pop}</tex>обращаются именно к ней. Состояние очереди будет фиксировать логическая переменная Все замечания о <tex>recopy\mathtt{toCopy}</tex>остаются в силе.

Теперь рассмотрим как обрабатывать операции во время перекопирования. В режиме перекопирования операция Также нам нет необходимости опустошать стек <tex>empty=falseR'</tex>к моменту перекопирования, так как мы не можем извлекать элементы, находившиеся в не пустом стеке скопировать туда новую версию <tex>LR</tex>, значит очередь всегда не пуста. Договоримся также, что операция мы можем за <tex>emptyO(1)</tex> не меняет внутреннюю структуру очереди и не создает новой версии , а освобождение ячеек памяти бессмысленно, так как они используются в других версиях персистентной очереди.

Поскольку стек В качестве версии очереди мы будем использовать запись <tex>Q= \langle L</tex> во время перемещения содержимого теряет свою структуру, мы не сможем положить туда элементыL', R, пришедшие с <tex>push</tex>. Для таких элементов заведем специальный стек <tex>LR', S, \mathtt{recopy}, \mathtt{toCopy}, \mathtt{copied}\rangle</tex> в который будем складывать поступающие элементы, а после перекопирования обменяем его ролями с <tex>L</tex>содержащую пять версий персистентных стеков и три переменных.

Этот алгоритм почти работает, но есть проблема: никто не гарантирует, что Пусть персистентный стек <tex>R</tex> опустошится за время перекопированиявозвращает вместе с обычным результатом работы стека новую версию, то есть мы получим в итоге два стека с выходными данными, а значит во время следующего перекопирования у нас может не быть свободного стека (например, если все операции были <tex>pushоперация </tex>)S. Избавимся от этой проблемы следующим образом: мы принудительно извлечем все элементы стека <tex>Rpop</tex> во вспомогательный стек возвращает <tex>T</tex>\langle Sn, затем переместим все элементы стека <tex>L</tex> в стек <tex>Rx\rangle</tex>, затем обратно переместим все элементы а операция <tex>TS.push(x)</tex> в стек <tex>R</tex>. Легко показать, что такая последовательность действий приведет к правильному для извлечения порядку элементов в возвращает <tex>RSn</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>toCopy \leqslant 0</tex> в стеке <tex>R</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>n</tex> времени, <tex>n</tex> памяти.# Поменять ролями стеки <tex>L, L'</tex>, <tex>1</tex> времени. Таким образом, мы получили <tex>3 \cdot n + 2</tex> времени возвращает и <tex>3 \cdot n + 1</tex> памяти на <tex>n + 1</tex> операциюперсистентная очередь, то есть <tex>3=O(1)</tex> времени и памяти на операциюQ. Совершая три дополнительных действия вместе с каждой операцией <tex>push, pop</tex> в режиме перекопирования мы гарантируем, что перекопирование завершится до опустошения стека <tex>R'</tex>. Теперь проверим корректность условия активации. Пусть среди <tex>n</tex> следующих за активацией операций <tex>push, pop</tex> присуствует <tex>x</tex> операций <tex>pop</tex> и <tex>n - x</tex> операций <tex>push</tex>. Тогда, очевидно, в стеке <tex>R</tex> окажется возвращает <tex>2 \cdot n + 1 - x</tex> элементовlangle Qn, а в стеке <tex>L</tex> станет <tex>n - x</tex> элементов, то есть на <tex>n + 1</tex> элемент меньше, чем в стеке <tex>R</tex>, а значит до следующего перекопирования <tex>n+2</tex> операции. Заметим, что теперь если очередь находится в обычном режиме, <tex>L.size \leqslant R.size</tex>, значит <tex>empty=(R.size==0)</tex>. Итак, очередь <tex>Q</tex> будет состоять из пяти стеков <tex>L,L',R,R',Trangle</tex>, а также двух внутренних переменных <tex>recopy, toCopy</tex>, которые нужны для корректности перекопирования, + дополнительной переменной <tex>copied</tex>, начинали ли мы уже перемещать элементы из стека <tex>L</tex> в <tex>R</tex>, чтобы не начать их перекладывать в <tex>T</tex>. Инвариант очереди (обычный режим):# Стек <tex>L</tex> содержит левую половину очереди, порядок при извлечении обратный.# Стек <tex>R</tex> содержит правую половину очереди, порядок при извлечении прямой.# <tex>L.size \leqslant R.size</tex># <tex>R.size = 0 \equiv Q.size = 0</tex># <tex>L'.size = 0, T.size = 0</tex> Инвариант очереди push(режим перекопированияx):# Если <tex>L.size = 0</tex>, то:## При <tex>toCopy > 0</tex> первые <tex>toCopy</tex> элементов <tex>T</tex> {{---}} корректны, то есть действительно содержатся в очереди.## При <tex>toCopy \leqslant </tex> стек <tex>R</tex> корректный, то есть содержит все элементы правого куска очереди в правильном порядке. Очередь будет работать в двух режимах:# Обычный режим, кладем в <tex>L</tex>, извлекаем из <tex>R</tex>, операция <tex>empty = (R.size = 0)</tex>.# Режим перекопирования, кладем в <tex>L'</tex>, извлекаем из <tex>R'</tex>, <tex>empty=false</tex>, совершаем дополнительные действия. Также после операции в обычном режиме следует проверка на активацию перекопирования(<tex>recopy = (L.size > R.size)</tex>), если это так, <tex>toCopy=R.size, recopy=true, copied = false, R'=R</tex>, совершается первый набор дополнительных действий. После операции в режиме перекопирования следует проверка на завершение перекопирования (<tex>recopy=(T.size==0)</tex>), а при завершении меняются ролями стеки <tex>L, L'</tex>. В качестве версии очереди мы будем использовать запись <tex>Q=<L, L', R, R', T, recopy, toCopy, copied></tex>, содержащую пять версий стеков и три переменных.Пусть персистентный стек возвращает вместе с обычным результатом работы стека новую версию, то есть операция <tex>S.pop</tex> возвращает <tex><Sn, x></tex>, а операция <tex>S.push</tex> возвращает <tex><Sn>Qn</tex>, аналогично свою новую версию возвращает и персистентная очередь.

'''boolean''' empty():

'''function''' push(x: '''T'''): '''if''' !recopy: '''stack<T>''' Ln = L.push(x) <'''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''boolean''', '''int''', '''boolean'''> Q' = <Ln, L', R, R', TS, recopy, toCopy, copied>

'''else''': '''stack<T>''' Ln' = L'.push(x) <'''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''boolean''', '''int''', '''boolean'''> Q' = <L, Ln', R, R', TS, recopy, toCopy, copied>

<'''stack<T>''', '''T'''> pop(): '''if''' !recopy:

<'''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''boolean''', '''int''', '''boolean'''> Q' = <L, L', Rn, R', TS, recopy, toCopy, copied>

'''else''':

'''int''' curCopy = toCopy

'''if''' toCopy > 0:

'''else''':

Q' = <L, L', Rn, Rn', TS, recopy, curCopy, copied>

<'''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''boolean''', '''int''', '''boolean'''> checkRecopy() : '''if''' L.size > R.size: <'''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''boolean''', '''int''', '''boolean'''> Q' = <L, L', R, R', TS, true, R.size, false>

'''else''': '''return''' <L, L', R, R', TS, false, toCopy, copied>

<'''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''boolean''', '''int''', '''boolean'''> checkNormal():

<span style="color:#008000">// Если мы не все перекопировали, то у нас не пуст стек TS</span> return <Q'.L, Q'.L', Q'.R, Q'.R', Q'.TS, Q'.TS.size <tex> \ne </tex> 0, Q'.toCopy, Q'.copied>

<'''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''boolean''', '''int''', '''boolean'''> additionalOperations(): <span style="color:#008000">// Нам достаточно 3 операций на вызов</span> '''int''' toDo = 3 <span style="color:#008000">// Пытаемся перекопировать R в TS</span> '''stack<T>''' Rn = R Tn '''stack<T>''' Sn = TS '''boolean''' curCopied = copied '''while''' '''not''' curCopied '''and''' toDo > 0 '''and''' Rn.size > 0:

Tn Sn = TnSn.push(x)

<span style="color:#008000">// Пытаемся перекопировать L в R</span> '''while''' toDo > 0 '''and''' Ln.size > 0:

<span style="color:#008000">// Пытаемся перекопировать T S в R с учетом toCopy</span> '''while''' toDo > 0 '''and''' TnSn.size > 0: <TnSn, x> = TnSn.pop() '''if''' curCopy > 0:

'''stack<T>''' Ln' = L' <span style="color:#008000">// Если все скопировано, то меняем роли L1, L2</span> '''if''' TS.size == 0:

'''return''' <Ln, Ln', Rn, R', TnSn, recopy, curCopy, curCopied>