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

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

Эффективная реализация

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

Теперь рассмотрим как обрабатывать операции во время перекопирования. В режиме перекопирования операция [math]empty=false[/math], так как мы не можем извлекать элементы, находившиеся в не пустом стеке [math]L[/math], значит очередь всегда не пуста. Договоримся также, что операция [math]empty[/math] не меняет внутреннюю структуру очереди и не создает новой версии очереди.

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

Этот алгоритм почти работает, но есть проблема: никто не гарантирует, что стек [math]R[/math] опустошится за время перекопирования, то есть мы получим в итоге два стека с выходными данными, а значит во время следующего перекопирования у нас может не быть свободного стека (например, если все операции были [math]push[/math]). Избавимся от этой проблемы следующим образом: мы принудительно извлечем все элементы стека [math]R[/math] во вспомогательный стек [math]T[/math], затем переместим все элементы стека [math]L[/math] в стек [math]R[/math], затем обратно переместим все элементы [math]T[/math] в стек [math]R[/math]. Легко показать, что такая последовательность действий приведет к правильному для извлечения порядку элементов в [math]R[/math].

Теперь разберемся с операциями [math]pop[/math]. Теперь у нас теряет свою структуру стек [math]R[/math], значит нужна его копия для извлечения элементов. Без персистентности нам бы пришлось создавать такую копию параллельно с самим стеком [math]R[/math], но теперь мы можем просто записать в [math]R'[/math] последнюю версию стека [math]R[/math] и дальше извлекать элементы уже из нее. Чтобы учесть извлеченные из копии элементы, будем использовать переменную [math]toCopy=R'.size[/math], будем уменьшать ее на [math]1[/math] при каждом извлечении из [math]T[/math] и операциях [math]pop[/math]. Так как извлеченные элементы будут нарастать со дна стека [math]T[/math], мы никогда не извлечем некорректный элемент, если [math]toCopy\gt 0[/math].

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

Всего в режиме перекопирования нужно:

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

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

Теперь проверим корректность условия активации. Пусть среди [math]n[/math] следующих за активацией операций [math]push, pop[/math] присуствует [math]x[/math] операций [math]pop[/math] и [math]n - x[/math] операций [math]push[/math]. Тогда, очевидно, в стеке [math]R[/math] окажется [math]2 \cdot n + 1 - x[/math] элементов, а в стеке [math]L[/math] станет [math]n - x[/math] элементов, то есть на [math]n + 1[/math] элемент меньше, чем в стеке [math]R[/math], а значит до следующего перекопирования [math]n+2[/math] операции.

Заметим, что теперь если очередь находится в обычном режиме, [math]L.size \leqslant R.size[/math], значит [math]empty=(R.size=0)[/math].

Итак, очередь [math]Q[/math] будет состоять из пяти стеков [math]L,L',R,R',T[/math], а также двух внутренних переменных [math]recopy, toCopy[/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]L'.size = 0, T.size = 0[/math]

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

1. Если [math]L.size = 0[/math], то первые [math]toCopy[/math] элементов [math]T[/math] — корректны, то есть действительно содержатся в очереди.

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

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

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

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

В качестве версии очереди мы будем использовать запись [math]Q=\lt L, L', R, R', T, recopy, toCopy\gt [/math], содержащую пять версий стеков и две переменных. Пусть персистентный стек возвращает вместе с обычным результатом стека новую версию, то есть операция [math]S.pop[/math] возвращает [math]\lt Sn, x\gt [/math], а операция [math]S.push[/math] возвращает [math]\lt Sn\gt [/math], аналогично свою новую версию возвращает и персистентная очередь.

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

empty

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

push

push(x)
   if !recopy:
      Ln = L.push(x)
      Q' = <Ln, L', R, R', T, recopy, toCopy>
      return Q'.checkRecopy()
   else:
      Ln' = L'.push(x)
      Q' = <L, Ln', R, R', T, recopy, toCopy> 
      return Q'.checkNormal()

pop

pop()
   if !recopy:
      <Rn, x> = R.pop()
      Q' = <L, L', Rn, R', T, recopy, toCopy>
      return <Q'.checkRecopy(), x>
   else:
      <Rn', x> = R'.pop()
      Q' = <L, L', R, Rn', T, recopy, toCopy - 1>
      return <Q'.checkNormal(), x>

checkRecopy

checkRecopy()    
   if L.size > R.size:
      Q' = <L, L', R, R', T, true, R.size>
      return Q'.additionalOperations()
   else:
      return <L, L', R, R', T, false, toCopy>

checkNormal

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

additionalOperations

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