Изменения

'''Персистентная очередь''' (англ. ''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>Rc, Rc'</tex> персистентная очередь хранит один стек <tex>R'</tex>, в который при активации перекопирования записывается последняя версия стека <tex>R</tex>, в дальнейшем все операции <tex>\mathtt{pop}</tex> обращаются именно к ней. Все замечания о <tex>\mathtt{toCopy}</tex> остаются в силе.

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

Пусть персистентный стек возвращает вместе с обычным результатом работы стека новую версию, то есть операция <tex>S.pop</tex> возвращает <tex><\langle Sn, x>\rangle</tex>, а операция <tex>S.push(x)</tex> возвращает <tex><Sn></tex>, аналогично . Аналогично свою новую версию вместе с результатом операции возвращает и персистентная очередь, то есть <tex>Q.pop</tex> возвращает <tex>\langle Qn, x\rangle</tex>, а <tex>Q.push(x)</tex> возвращает <tex>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>

== Пример ==

Пусть мы создали персистентную очередь. Будем изображать ее в виде пяти деревьев версий персистентных стеков, закрашенные вершины {{---}} текущие версии стеков, соответствующие текущему состоянию очереди; стрелка от стека <tex>R'</tex> указывает на ту версию стека <tex>R</tex>, которая там сейчас хранится. В самих вершинах записаны соответствующие этим вершинам значения.

[[Файл:PersistentQueue_state0.png|500px300px|nothumb|left|]]

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

[[Файл:PersistentQueue_state1.png|500px300px|nothumb|left|]]

Сделаем операцию <tex> \mathtt{push(2) } </tex>, у нас обычный режим, поэтому элемент пойдет в стек <tex>L</tex>, перекопирование не активируется.

[[Файл:PersistentQueue_state2.png|500px300px|nothumb|left|]]

Сделаем операцию <tex> \mathtt{push(3) } </tex>, у нас обычный режим, поэтому элемент пойдет в стек <tex>L</tex>, активируется перекопирование, <tex>R' = R</tex>, за три операции мы успеваем переложить перекопировать элемент стека <tex>R</tex> в стек <tex>TS</tex>, а также переложить перекопировать два элемента стека <tex>L</tex> в стек <tex>R</tex>.

[[Файл:PersistentQueue_state3.png|500px300px|nothumb|left|]]

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

[[Файл:PersistentQueue_state4.png|500px300px|nothumb|left|]]

Сделаем операцию <tex> \mathtt{push(5) } </tex>, у нас обычный режим, поэтому элемент пойдет в стек <tex>L</tex>, перекопирование не активируется.

[[Файл:PersistentQueue_state5.png|500px300px|nothumb|left|]]

Сделаем операцию <tex> \mathtt{push(6) } </tex>, у нас обычный режим, поэтому элемент пойдет в стек <tex>L</tex>, перекопирование не активируется.

[[Файл:PersistentQueue_state6.png|500px300px|nothumb|left|]]

Сделаем операцию <tex> \mathtt{push(7) } </tex>, у нас обычный режим, поэтому элемент пойдет в стек <tex>L</tex>, перекопирование активируется, <tex>R' = R</tex>, <tex>\mathtt{toCopy} = 3</tex>, за три операции мы успеваем переместить перекопировать содержимое стека <tex>R</tex> в стек <tex>TS</tex>.

[[Файл:PersistentQueue_state7.png|500px300px|nothumb|left|]]

Сделаем операцию <tex>\mathtt{pop}</tex>, мы находимся в режиме перекопирования, так что элемент извлекается из <tex>R'</tex>, <tex>\mathtt{toCopy} = 2</tex>. За три операции мы успеваем перекопировать три элемента стека <tex>L</tex> в стек <tex>R</tex>.

[[Файл:PersistentQueue_state8.png|500px300px|nothumb|left|]]

Сделаем операцию <tex>\mathtt{pop}</tex>, мы находимся в режиме перекопирования, так что элемент извлекается из <tex>R'</tex>, <tex>\mathtt{toCopy} = 1</tex>. За три операции мы успеваем перекопировать один элемент стека <tex>L</tex> в стек <tex>R</tex>, а также извлечь два элемента стека <tex>TS</tex>, с учетом <tex>\mathtt{toCopy}</tex> только один элемент попадет в стек <tex>R</tex>, <tex>\mathtt{toCopy} = 0</tex>.

[[Файл:PersistentQueue_State9.png|500px300px|nothumb|left|]]

Сделаем операцию <tex>\mathtt{pop}</tex>, мы находимся в режиме перекопирования, так что элемент извлекается из <tex>R'</tex>, но <tex>\mathtt{toCopy } = 0</tex>, так что нам приходится извлечь еше один элементиз стека <tex>R</tex>. Мы извлекаем один элемент из стека <tex>S</tex>, перекопирование заканчивается, стеки <tex>L, L'</tex> меняются местами.

[[Файл:PersistentQueue_state10.png|500px300px|nothumb|left|]]

= Ссылки = См. также ==*[[Персистентный стек]]*[[Персистентный дек]]*[[Персистентная приоритетная очередь]] == Источники информации ==