Изменения

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

== Эффективная реализация Основная идея ==

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

В каждый момент времени определеноОдним из минусов реализации на двух стеках является то, какой стек что в худшем случае мы тратим <tex>LO(n)</tex> из стеков <tex>L_1времени на операцию. Если распределить время, L_2</tex> сейчас используется необходимое для операций <tex>push</tex>перемещения элементов из одного стека в другой, какой стек <tex>R</tex> из стеков <tex>R_1по операциям, R_2</tex> сейчас используется для операций мы получим очередь без худших случаев с <tex>popO(1)</tex>, а также находится ли очередь в режиме перекопирования (''recopy mode'')истинного времени на операцию.

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

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

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

Для заверешения перекопирования нужноНо этого еще недостаточно. Если мы принудительно извлекаем элементы из стека <tex>R</tex>, появляются следующие проблемы:# Переместить все содержимое стека Что вернуть при операции <tex>R\mathtt{pop}</tex> в ? Для этого заведем себе стек <tex>TRc</tex>, {{---}} копию стека <tex>nR</tex> операций, из которого мы и будем извлекать требуемые элементы.# Переместить все содержимое стека Как поддерживать корректность такой копии? Поскольку этот стек нужен только для перекопирования, а во время него он занят, нужна запасная копия <tex>LRc'</tex> для копирования всех элементов, которые мы копируем в <tex>R</tex>, а по окончании перекопирования поменяем ролями стеки <tex>n + 1Rc, Rc'</tex>, как мы делали со стеками <tex>L, L'</tex> операция. # Переместить первые Как учесть, что во время перекопирования часть элементов была извлечена из <tex>Rc</tex>? Для этого заведем специальную переменную <tex>\mathtt{toCopy}</tex> , которая показывает, сколько корректных элементов стека находится в стеке <tex>S</tex>, и уменьшается при каждом извлечении из <tex>TS</tex> в или операции <tex>R\mathtt{pop}</tex>. К счастью, а оставшиеся все некорректные элементы выкинутьбудут нарастать со дна стека, так что мы никогда не извлечем некорректный элемент, если <tex>n\mathtt{toCopy}>0</tex> операций. # Обменять местами стеки Если во время операции <tex>L\mathtt{pop}</tex> и у нас <tex>L'\mathtt{toCopy} = 0</tex>, это означает, что теперь в стеке <tex>2R</tex> операциинаходится весь правый кусок очереди, так что нам придется извлечь элемент из него.

ИтогоТеперь может возникнуть проблема с непустым <tex>Rc</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>S</tex>, <tex>n</tex> действий.# Переместить содержимое <tex>L</tex> в стеки <tex>R, Rc'</tex>, <tex>n + 1</tex> действий.# Переместить первые <tex>\mathtt{toCopy}</tex> элементов из <tex>S</tex> в <tex>R, Rc'</tex>, остальные выкинуть, <tex>n</tex> действий.# Поменять ролями стеки <tex>Rc, Rc'</tex>, <tex>L, L'</tex>, <tex>2</tex> действия. Таким образом, получили <tex>3 \cdot n + 3</tex> дополнительных действия за <tex>n + 1</tex> операций, или <tex>3 = O(1)</tex> дополнительных действий на операцию в режиме перекопирования, что и требовалось. Теперь рассмотрим, как изменились наши стеки за весь период перекопирования. Договоримся, что операция <tex>\mathtt{empty}</tex> не меняет очередь, то есть выполняя никакие дополнительные действия не совершаются. Пусть за <tex>On</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',S</tex>, а также двух внутренних переменных <tex>\mathtt{recopy}, \mathtt{toCopy}</tex>, которые нужны для корректности перекопирования + дополнительная переменная <tex>\mathtt{copied}</tex>, показывающая, перемещали ли мы элементы из стека <tex>L</tex> в стек <tex>R</tex>, чтобы не начать перемещать эти элементы в стек <tex>S</tex>.  Инвариант очереди (обычный режим):# Стек <tex>L</tex> содержит левую половину очереди, порядок при извлечении обратный.# Стек <tex>R</tex> содержит правую половину очереди, порядок при извлечении прямой.# <tex>L.size \leqslant R.size</tex># <tex>R.size = 0 \equiv Q.size = 0</tex># <tex>Rc</tex> {{---}} копия <tex>R</tex># <tex>Rc'.size < R.size - L.size</tex># <tex>L'.size = 0, S.size = 0</tex> Тогда к следующему перекопированию (<tex>L.size=R.size+1</tex>) мы гарантированно будем иметь пустые стеки <tex>L',S,Rc'</tex>, которые нам понадобятся. Инвариант очереди (режим перекопирования):# <tex>Rc.size = \mathtt{toCopy}</tex># Если <tex>L.size =30</tex>, то:## При <tex>\mathtt{toCopy} > 0</tex> первые <tex>\mathtt{toCopy}</tex> элементов <tex>S</tex> {{---}} корректны, то есть действительно содержатся в очереди.## При <tex>\mathtt{toCopy} \leqslant 0</tex> стек <tex>R</tex> содержит весь правый кусок очереди в правильном порядке. Очередь будет работать в двух режимах:# Обычный режим, кладем в <tex>L</tex>, извлекаем из <tex>R</tex> и из <tex>Rc, Rc'</tex> для поддержания порядка, операция <tex>empty = (R.size = 0)</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} = (S.size == 0)</tex>), а при завершении меняются ролями стеки <tex>Rc, Rc'</tex>, <tex>L, L'</tex>. Следующий псевдокод выполняет требуемые операции:=== empty ===<code> '''boolean''' empty(): '''return''' !recopy '''and''' R.size == 0</code>=== push ===<code> '''function''' push(x : '''T'''): '''if''' !recopy L.push(x) '''if''' Rc'.size > 0 Rc'.pop() checkRecopy() '''else''' L'.push(x) checkNormal()</code>=== pop ===<code> '''T''' pop(): '''if''' !recopy '''T''' tmp = R.pop() Rc.pop() '''if''' Rc'.size > 0 Rc'.pop() checkRecopy() '''return''' tmp '''else''' '''T''' tmp = Rc.pop() '''if''' toCopy > 0 toCopy = toCopy - 1 '''else''' R.pop() Rc'.pop() checkNormal() '''return''' tmp</code> === checkRecopy ===<code> '''function''' checkRecopy(): recopy = L.size > R.size '''if''' recopy toCopy = R.size copied = false checkNormal()</code> === checkNormal ===<code> '''function''' checkNormal(): additionalOperations() <span style="color:#008000">// Если мы сможем завершить перекопирование не все перекопировали, то у нас не пуст стек S</span> recopy = S.size <tex> \ne </tex> 0</code>=== additionalOperations ===<code> '''function''' additionalOperations(): <span style="color:#008000">// Нам достаточно 3 операций на вызов</span> '''int''' toDo = 3 <span style="color:#008000">// Пытаемся перекопировать R в S</span> '''while''' '''not''' copied '''and''' toDo > 0 '''and''' R.size > 0 S.push(R.pop()) toDo = toDo - 1 <span style="color:#008000">// Пытаемся перекопировать L в R и Rc'</span> '''while''' toDo > 0 '''and''' L.size > 0 copied = true '''T''' x = L.pop() R.push(x) Rc'.push(x) toDo = toDo - 1 <span style="color:#008000">// Пытаемся перекопировать S в R и Rc' с учетом toCopy</span> '''while''' toDo > 0 '''and''' S.size > 0 '''T''' x = S.pop() '''if''' toCopy > 0 R.push(x) Rc'.push(x) toCopy = toCopy - 1 toDo = toDo - 1 <span style="color:#008000">// Если все скопировано, то меняем роли L, L' и вернуться Rc, Rc'</span> '''if''' S.size == 0 swap(L, L') swap(Rc, Rc')</code> == Персистентная очередь на пяти стеках == После того, как мы получили [[Персистентная очередь#Реализация очереди на шести стеках|очередь в реальном времени]] с <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>R'</tex> к моменту перекопирования, так как скопировать туда новую версию <tex>R</tex> мы можем за <tex>O(1)</tex> реального времени , а освобождение ячеек памяти бессмысленно, так как они используются в других версиях персистентной очереди.  В качестве версии очереди мы будем использовать запись <tex>Q= \langle L, L', R, R', S, \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>OQ.pop</tex> возвращает <tex>\langle Qn, x\rangle</tex>, а <tex>Q.push(x)</tex> возвращает <tex>Qn</tex>. Следующий псевдокод выполняет требуемые операции:=== empty ===<code> '''boolean''' empty(): '''return''' !recopy '''and''' R.size == 0</code>=== push ===<code> '''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', S, recopy, toCopy, copied> '''return''' Q'.checkRecopy() '''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', S, recopy, toCopy, copied> '''return''' Q'.checkNormal()</code>=== pop ===<code> <'''stack<T>''', '''T'''> pop(): '''if''' !recopy <Rn, x> = R.pop() <'''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''boolean''', '''int''', '''boolean'''> Q' = <L, L', Rn, R', S, recopy, toCopy, copied> '''return''' <Q'.checkRecopy(), x> '''else''' <Rn', x> = R'.pop() '''int''' curCopy = toCopy Rn = R '''if''' toCopy > 0 curCopy = curCopy - 1 '''else''' <Rn, x> = Rn.pop() Q' = <L, L', Rn, Rn', S, recopy, curCopy, copied> '''return''' <Q'.checkNormal(), x></code>=== checkRecopy ===<code> <'''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', S, true, R.size, false> '''return''' Q'.checkNormal() '''else''' '''return''' <L, L', R, R', S, false, toCopy, copied></code> === checkNormal ===<code> <'''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''stack<T>''', '''boolean''', '''int''', '''boolean'''> checkNormal(): Q' = Q.additionalOperations() <span style="color:#008000">// Если мы не все перекопировали, то у нас не пуст стек S</span> return <Q'.L, Q'.L', Q'.R, Q'.R', Q'.S, Q'.S.size <tex> памяти \ne </tex> 0, Q'.toCopy, Q'.copied></code>=== additionalOperations ===<code> <'''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 в S</span> '''stack<T>''' Rn = R '''stack<T>''' Sn = S '''boolean''' curCopied = copied '''while''' '''not''' curCopied '''and''' toDo > 0 '''and''' Rn.size > 0 <Rn, x> = Rn.pop() Sn = Sn.push(x) toDo = toDo - 1 Ln = L <span style="color:#008000">// Пытаемся перекопировать L в R</span> '''while''' toDo > 0 '''and''' Ln.size > 0 curCopied = true <Ln, x> = Ln.pop() Rn = Rn.push(x) toDo = toDo - 1 curCopy = toCopy <span style="color:#008000">// Пытаемся перекопировать S в R с учетом toCopy</span> '''while''' toDo > 0 '''and''' Sn.size > 0 <Sn, x> = Sn.pop() '''if''' curCopy > 0 Rn = Rn.push(x) curCopy = curCopy - 1 toDo = toDo - 1 '''stack<T>''' Ln' = L' <span style="color:#008000">// Если все скопировано, то меняем роли L1, L2</span> '''if''' S.size == 0 swap(Ln, Ln') '''return''' <Ln, Ln', Rn, R', Sn, recopy, curCopy, curCopied> </code> == Пример == Пусть мы создали персистентную очередь. Будем изображать ее в виде пяти деревьев версий персистентных стеков, закрашенные вершины {{---}} текущие версии стеков, соответствующие текущему состоянию очереди; стрелка от стека <tex>R'</tex> указывает на ту версию стека <tex>R</tex>, которая там сейчас хранится. В самих вершинах записаны соответствующие этим вершинам значения. [[Файл:PersistentQueue_state0.png|300px|nothumb|left|]] <br clear = "all"/> Сделаем операцию <tex> \mathtt{push(1)} </tex>, изначально режим обычный, так что элемент пойдет в стек <tex>L</tex>. Эта операция активирует режим перекопирования, в результате которого содержимое <tex>L</tex> перекопируется в стек <tex>R</tex>, после чего перекопирование завершится, стеки <tex>L, L'</tex> поменяются местами. [[Файл:PersistentQueue_state1.png|300px|nothumb|left|]] <br clear = "all"/> Сделаем операцию <tex> \mathtt{push(2)} </tex>, у нас обычный режим, поэтому элемент пойдет в стек <tex>L</tex>, перекопирование не активируется. [[Файл:PersistentQueue_state2.png|300px|nothumb|left|]] <br clear = "all"/> Сделаем операцию <tex> \mathtt{push(3)} </tex>, у нас обычный режим, поэтому элемент пойдет в стек <tex>L</tex>, активируется перекопирование, <tex>R' = R</tex>, за три операции мы успеваем перекопировать элемент стека <tex>R</tex> в стек <tex>S</tex>, а также перекопировать два элемента стека <tex>L</tex> в стек <tex>R</tex>. [[Файл:PersistentQueue_state3.png|300px|nothumb|left|]] <br clear = "all"/> Сделаем операцию <tex> \mathtt{push(4)} </tex>, мы в режиме перекопирования, поэтому элемент пойдет в стек <tex>L'</tex>, далее мы успеваем перекопировать обратно элемент из стека <tex>S</tex> в стек <tex>R</tex>, перекопирование завершается, стеки <tex>L, L'</tex> меняются местами. [[Файл:PersistentQueue_state4.png|300px|nothumb|left|]] <br clear = "all"/> Сделаем операцию <tex> \mathtt{push(5)} </tex>, у нас обычный режим, поэтому элемент пойдет в стек <tex>L</tex>, перекопирование не активируется. [[Файл:PersistentQueue_state5.png|300px|nothumb|left|]] <br clear = "all"/> Сделаем операцию<tex> \mathtt{push(6)} </tex>, у нас обычный режим, поэтому элемент пойдет в стек <tex>L</tex>, перекопирование не активируется.  [[Файл:PersistentQueue_state6.png|300px|nothumb|left|]] <br clear = "all"/> Сделаем операцию <tex> \mathtt{push(7)} </tex>, у нас обычный режим, поэтому элемент пойдет в стек <tex>L</tex>, перекопирование активируется, <tex>R' = R</tex>, <tex>\mathtt{toCopy} = 3</tex>, за три операции мы успеваем перекопировать содержимое стека <tex>R</tex> в стек <tex>S</tex>. [[Файл:PersistentQueue_state7.png|300px|nothumb|left|]] <br clear = "all"/> Сделаем операцию <tex>\mathtt{pop}</tex>, мы находимся в режиме перекопирования, так что элемент извлекается из <tex>R'</tex>, <tex>\mathtt{toCopy} = 2</tex>. За три операции мы успеваем перекопировать три элемента стека <tex>L</tex> в стек <tex>R</tex>. [[Файл:PersistentQueue_state8.png|300px|nothumb|left|]] <br clear = "all"/> Сделаем операцию <tex>\mathtt{pop}</tex>, мы находимся в режиме перекопирования, так что элемент извлекается из <tex>R'</tex>, <tex>\mathtt{toCopy} = 1</tex>. За три операции мы успеваем перекопировать один элемент стека <tex>L</tex> в стек <tex>R</tex>, а также извлечь два элемента стека <tex>S</tex>, с учетом <tex>\mathtt{toCopy}</tex> только один элемент попадет в стек <tex>R</tex>, <tex>\mathtt{toCopy} = 0</tex>. [[Файл:PersistentQueue_State9.png|300px|nothumb|left|]] <br clear = "all"/> Сделаем операцию <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|300px|nothumb|left|]] <br clear = "all"/> == См. также ==*[[Персистентный стек]]*[[Персистентный дек]]*[[Персистентная приоритетная очередь]] == Источники информации ==* [http://hdl.handle.net/1813/6273 ''Hood R., Melville R.'' Real Time Queue Operations in Pure LISP. {{---}} Cornell University, 1980]* [http://habrahabr.ru/post/241231 Хабрахабр {{---}} Персистентная очередь]* [http://codeforces.com/blog/entry/15685 Codeforces {{---}} Персистентная очередь и её друзья]