Персистентная очередь — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 30 промежуточных версий 6 участников)
Строка 1: Строка 1:
После того, как мы получили [[Очередь#Реализация на шести стеках|очередь в реальном времени]] с <tex>O(1)=6</tex> обычными [[Стек|стеками]], ее можно легко превратить в персистентную, сделав все стеки [[Персистентный стек|персистентными]], но на самом деле персистентность позволяет не создавать явной копии стека, так что достаточно всего пяти стеков.
+
'''Персистентная очередь''' (англ. ''persistent queue'') {{---}} это [[Очередь|очередь]], реализующая [[Персистентные структуры данных|персистентность]], то есть позволяющая получить доступ ко всем своим предыдущим версиям. Как будет показано далее, можно реализовать функциональную персистентность, то есть каждая ячейка памяти в такой структуре будет инициализирована один раз и в дальнейшем не изменится.
  
== Эффективная реализация ==
+
== Основная идея ==
  
Будем отталкиваться от реализации на [[Очередь#Реализация на двух стеках|двух стеках]]. Пусть у нас есть стек <tex>L</tex> для операций <tex>push</tex>, стек <tex>R</tex> для операций <tex>pop</tex>.
+
Для создания персистентной очереди очень удобно пользоваться ее реализацией на [[Стек|стеках]], поскольку стеки легко сделать [[Персистентный стек|персистентными]], причем в этом случае мы добьемся функциональной персистентности. [[Очередь#Реализация на двух стеках|Реализация на двух стеках]] не подходит для этого, так как в худшем случае требует <tex>O(n)</tex> времени, а значит и <tex>O(n)</tex> памяти на операцию в случае персистентности. Покажем сначала, как создать очередь в реальном времени с <tex>O(1)</tex> времени на операцию, а затем превратим ее в персистентную.
К моменту опустошения стека <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>L</tex> во время перемещения содержимого теряет свою структуру, мы не сможем положить туда элементы, пришедшие с <tex>push</tex>. Для таких элементов заведем специальный стек <tex>L'</tex> в который будем складывать поступающие элементы, а после перекопирования обменяем его ролями с <tex>L</tex>.
+
Одним из минусов реализации на двух стеках является то, что в худшем случае мы тратим <tex>O(n)</tex> времени на операцию. Если распределить время, необходимое для перемещения элементов из одного стека в другой, по операциям, мы получим очередь без худших случаев с <tex>O(1)</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>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>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>\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>S</tex>, затем копировать элементы из стека <tex>L</tex> в <tex>R</tex>, а затем обратно копировать элементы из стека <tex>S</tex> в <tex>R</tex>. Легко показать, что приведенный алгоритм как раз получает на выходе в <tex>R</tex> все элементы стеков <tex>L,R</tex> в правильном порядке.
  
 +
Но этого еще недостаточно. Если мы принудительно извлекаем элементы из стека <tex>R</tex>, появляются следующие проблемы:
 +
# Что вернуть при операции <tex>\mathtt{pop}</tex>? Для этого заведем себе стек <tex>Rc</tex> {{---}} копию стека <tex>R</tex>, из которого мы и будем извлекать требуемые элементы.
 +
# Как поддерживать корректность такой копии? Поскольку этот стек нужен только для перекопирования, а во время него он занят, нужна запасная копия <tex>Rc'</tex> для копирования всех элементов, которые мы копируем в <tex>R</tex>, а по окончании перекопирования поменяем ролями стеки <tex>Rc, Rc'</tex>, как мы делали со стеками <tex>L, L'</tex>.
 +
# Как учесть, что во время перекопирования часть элементов была извлечена из <tex>Rc</tex>? Для этого заведем специальную переменную <tex>\mathtt{toCopy}</tex>, которая показывает, сколько корректных элементов находится в стеке <tex>S</tex>, и уменьшается при каждом извлечении из <tex>S</tex> или операции <tex>\mathtt{pop}</tex>. К счастью, все некорректные элементы будут нарастать со дна стека, так что мы никогда не извлечем некорректный элемент, если <tex>\mathtt{toCopy}>0</tex>. Если во время операции <tex>\mathtt{pop}</tex> у нас <tex>\mathtt{toCopy} = 0</tex>, это означает, что теперь в стеке <tex>R</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>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',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 = 0</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> \neq </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>Q.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 {{---}} Персистентная очередь и её друзья]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Амортизационный анализ]]
 
[[Категория: Амортизационный анализ]]
 +
[[Категория: Структуры данных‏‎]]

Текущая версия на 19:15, 4 сентября 2022

Персистентная очередь (англ. persistent queue) — это очередь, реализующая персистентность, то есть позволяющая получить доступ ко всем своим предыдущим версиям. Как будет показано далее, можно реализовать функциональную персистентность, то есть каждая ячейка памяти в такой структуре будет инициализирована один раз и в дальнейшем не изменится.

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

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

Реализация очереди на шести стеках

Одним из минусов реализации на двух стеках является то, что в худшем случае мы тратим [math]O(n)[/math] времени на операцию. Если распределить время, необходимое для перемещения элементов из одного стека в другой, по операциям, мы получим очередь без худших случаев с [math]O(1)[/math] истинного времени на операцию.

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

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

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

Но этого еще недостаточно. Если мы принудительно извлекаем элементы из стека [math]R[/math], появляются следующие проблемы:

  1. Что вернуть при операции [math]\mathtt{pop}[/math]? Для этого заведем себе стек [math]Rc[/math] — копию стека [math]R[/math], из которого мы и будем извлекать требуемые элементы.
  2. Как поддерживать корректность такой копии? Поскольку этот стек нужен только для перекопирования, а во время него он занят, нужна запасная копия [math]Rc'[/math] для копирования всех элементов, которые мы копируем в [math]R[/math], а по окончании перекопирования поменяем ролями стеки [math]Rc, Rc'[/math], как мы делали со стеками [math]L, L'[/math].
  3. Как учесть, что во время перекопирования часть элементов была извлечена из [math]Rc[/math]? Для этого заведем специальную переменную [math]\mathtt{toCopy}[/math], которая показывает, сколько корректных элементов находится в стеке [math]S[/math], и уменьшается при каждом извлечении из [math]S[/math] или операции [math]\mathtt{pop}[/math]. К счастью, все некорректные элементы будут нарастать со дна стека, так что мы никогда не извлечем некорректный элемент, если [math]\mathtt{toCopy}\gt 0[/math]. Если во время операции [math]\mathtt{pop}[/math] у нас [math]\mathtt{toCopy} = 0[/math], это означает, что теперь в стеке [math]R[/math] находится весь правый кусок очереди, так что нам придется извлечь элемент из него.

Теперь может возникнуть проблема с непустым [math]Rc[/math] после завершения перекопирования. Покажем, что мы всегда успеем его опустошить, если будем использовать дополнительное извлечение из него при каждой операции в обычном режиме, для этого полностью проанализируем алгоритм.

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

Посмотрим на дополнительные действия, которые нам предстоят:

  1. Переместить содержимое [math]R[/math] в [math]S[/math], [math]n[/math] действий.
  2. Переместить содержимое [math]L[/math] в стеки [math]R, Rc'[/math], [math]n + 1[/math] действий.
  3. Переместить первые [math]\mathtt{toCopy}[/math] элементов из [math]S[/math] в [math]R, Rc'[/math], остальные выкинуть, [math]n[/math] действий.
  4. Поменять ролями стеки [math]Rc, Rc'[/math], [math]L, L'[/math], [math]2[/math] действия.

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

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

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

Инвариант очереди (обычный режим):

  1. Стек [math]L[/math] содержит левую половину очереди, порядок при извлечении обратный.
  2. Стек [math]R[/math] содержит правую половину очереди, порядок при извлечении прямой.
  3. [math]L.size \leqslant R.size[/math]
  4. [math]R.size = 0 \equiv Q.size = 0[/math]
  5. [math]Rc[/math] — копия [math]R[/math]
  6. [math]Rc'.size \lt R.size - L.size[/math]
  7. [math]L'.size = 0, S.size = 0[/math]

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

Инвариант очереди (режим перекопирования):

  1. [math]Rc.size = \mathtt{toCopy}[/math]
  2. Если [math]L.size = 0[/math], то:
    1. При [math]\mathtt{toCopy} \gt 0[/math] первые [math]\mathtt{toCopy}[/math] элементов [math]S[/math] — корректны, то есть действительно содержатся в очереди.
    2. При [math]\mathtt{toCopy} \leqslant 0[/math] стек [math]R[/math] содержит весь правый кусок очереди в правильном порядке.

Очередь будет работать в двух режимах:

  1. Обычный режим, кладем в [math]L[/math], извлекаем из [math]R[/math] и из [math]Rc, Rc'[/math] для поддержания порядка, операция [math]empty = (R.size = 0)[/math].
  2. Режим перекопирования, кладем в [math]L'[/math], извлекаем из [math]Rc[/math], возможно из [math]R[/math], [math]\mathtt{empty} = \mathtt{false}[/math], совершаем дополнительные действия.

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

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

Следующий псевдокод выполняет требуемые операции:

empty

boolean empty():
   return !recopy and R.size == 0

push

function push(x : T):
   if !recopy
      L.push(x)
      if Rc'.size > 0
         Rc'.pop()
      checkRecopy()
   else
      L'.push(x)
      checkNormal()

pop

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

checkRecopy

function checkRecopy():    
   recopy = L.size > R.size
   if recopy
      toCopy = R.size
      copied = false
      checkNormal()

checkNormal

function checkNormal():
   additionalOperations()
    // Если мы не все перекопировали, то у нас не пуст стек S
   recopy = S.size [math] \neq [/math] 0

additionalOperations

function additionalOperations():
   // Нам достаточно 3 операций на вызов
   int toDo = 3
   // Пытаемся перекопировать R в S
   while not copied and toDo > 0 and R.size > 0
      S.push(R.pop())
      toDo = toDo - 1
   // Пытаемся перекопировать L в R и Rc'
   while toDo > 0 and L.size > 0
      copied = true
      T x = L.pop()
      R.push(x)
      Rc'.push(x)
      toDo = toDo - 1
   // Пытаемся перекопировать S в R и Rc' с учетом toCopy
   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
   // Если все скопировано, то меняем роли L, L' и Rc, Rc'
   if S.size == 0
      swap(L, L')
      swap(Rc, Rc')

Персистентная очередь на пяти стеках

После того, как мы получили очередь в реальном времени с [math]O(1) = 6[/math] обычными стеками, ее можно легко превратить в персистентную, сделав все стеки персистентными, но на самом деле персистентность позволяет не создавать явной копии стека [math]R[/math], так что достаточно всего пяти стеков.

Вместо стеков [math]Rc, Rc'[/math] персистентная очередь хранит один стек [math]R'[/math], в который при активации перекопирования записывается последняя версия стека [math]R[/math], в дальнейшем все операции [math]\mathtt{pop}[/math] обращаются именно к ней. Все замечания о [math]\mathtt{toCopy}[/math] остаются в силе.

Также нам нет необходимости опустошать стек [math]R'[/math] к моменту перекопирования, так как скопировать туда новую версию [math]R[/math] мы можем за [math]O(1)[/math], а освобождение ячеек памяти бессмысленно, так как они используются в других версиях персистентной очереди.

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

Пусть персистентный стек возвращает вместе с обычным результатом работы стека новую версию, то есть операция [math]S.pop[/math] возвращает [math]\langle Sn, x\rangle[/math], а операция [math]S.push(x)[/math] возвращает [math]Sn[/math].

Аналогично свою новую версию вместе с результатом операции возвращает и персистентная очередь, то есть [math]Q.pop[/math] возвращает [math]\langle Qn, x\rangle[/math], а [math]Q.push(x)[/math] возвращает [math]Qn[/math].

Следующий псевдокод выполняет требуемые операции:

empty

boolean empty():
   return !recopy and R.size == 0

push

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()

pop

<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>

checkRecopy

<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>

checkNormal

<stack<T>, stack<T>, stack<T>, stack<T>, stack<T>, boolean, int, boolean> checkNormal():
   Q' = Q.additionalOperations()
   // Если мы не все перекопировали, то у нас не пуст стек S
   return <Q'.L, Q'.L', Q'.R, Q'.R', Q'.S, Q'.S.size [math] \ne [/math] 0, Q'.toCopy, Q'.copied>

additionalOperations

<stack<T>, stack<T>, stack<T>, stack<T>, stack<T>, boolean, int, boolean> additionalOperations():
   // Нам достаточно 3 операций на вызов
   int toDo = 3
   // Пытаемся перекопировать R в S
   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
   // Пытаемся перекопировать L в R
   while toDo > 0 and Ln.size > 0
      curCopied = true
      <Ln, x> = Ln.pop()
      Rn = Rn.push(x)
      toDo = toDo - 1
   curCopy = toCopy
   // Пытаемся перекопировать S в R с учетом toCopy
   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'
   // Если все скопировано, то меняем роли L1, L2
   if S.size == 0
      swap(Ln, Ln')
   return <Ln, Ln', Rn, R', Sn, recopy, curCopy, curCopied>      

Пример

Пусть мы создали персистентную очередь. Будем изображать ее в виде пяти деревьев версий персистентных стеков, закрашенные вершины — текущие версии стеков, соответствующие текущему состоянию очереди; стрелка от стека [math]R'[/math] указывает на ту версию стека [math]R[/math], которая там сейчас хранится. В самих вершинах записаны соответствующие этим вершинам значения.

PersistentQueue state0.png


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

PersistentQueue state1.png


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

PersistentQueue state2.png


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

PersistentQueue state3.png


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

PersistentQueue state4.png


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

PersistentQueue state5.png


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

PersistentQueue state6.png


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

PersistentQueue state7.png


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

PersistentQueue state8.png


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

PersistentQueue State9.png


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

PersistentQueue state10.png


См. также

Источники информации