Изменения

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

Понятно, что во время перекопирования могут поступить операции <tex>\mathtt{push}</tex>, а стек <tex>L</tex> в это время потеряет свою структуру, сложить элементы туда мы уже не сможем, значит нужно завести еще один стек <tex>L'</tex>, в который мы и будем складывать новые элементы. После окончания перекопирования мы поменяем ролями <tex>L,L'</tex> и <tex>R,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>L</tex> в стеки <tex>R, Rc'</tex>, <tex>n + 1</tex> действий.

# Поменять ролями стеки <tex>Rc, Rc'</tex>, <tex>L, L'</tex>, <tex>2</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>Rc</tex> {{---}} копия <tex>R</tex>

# <tex>Rc'.size < R.size - L.size</tex>

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

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

# Если <tex>L.size = 0</tex>, то:

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

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

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

'''function''' checkNormal():

additionalOperations()

</code>

=== additionalOperations ===

<code>

'''function''' additionalOperations():

'''int''' toDo = 3

'''while''' '''not''' copied '''and''' toDo > 0 '''and''' R.size > 0

toDo = toDo - 1

'''while''' toDo > 0 '''and''' L.size > 0

copied = true

Rc'.push(x)

toDo = toDo - 1

'''if''' toCopy > 0

R.push(x)

toCopy = toCopy - 1

toDo = toDo - 1

swap(L, L')

swap(Rc, Rc')

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

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

'''if''' !recopy

'''stack<T>''' Ln = L.push(x)

'''return''' Q'.checkRecopy()

'''else'''

'''stack<T>''' Ln' = L'.push(x)

'''return''' Q'.checkNormal()

</code>

'''if''' !recopy

<Rn, x> = R.pop()

'''return''' <Q'.checkRecopy(), x>

'''else'''

'''else'''

<Rn, x> = Rn.pop()

'''return''' <Q'.checkNormal(), x>

</code>

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

'''if''' L.size > R.size

'''return''' Q'.checkNormal()

'''else'''

</code>

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

Q' = Q.additionalOperations()

</code>

=== additionalOperations ===

<code>

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

'''int''' toDo = 3

'''stack<T>''' Rn = R

'''boolean''' curCopied = copied

'''while''' '''not''' curCopied '''and''' toDo > 0 '''and''' Rn.size > 0

<Rn, x> = Rn.pop()

toDo = toDo - 1

Ln = L

'''while''' toDo > 0 '''and''' Ln.size > 0

curCopied = true

toDo = toDo - 1

curCopy = toCopy

'''if''' curCopy > 0

Rn = Rn.push(x)

toDo = toDo - 1

'''stack<T>''' Ln' = L'

swap(Ln, Ln')

</code>

<br clear = "all"/>

[[Файл:PersistentQueue_state3.png|300px|nothumb|left|]]

<br clear = "all"/>

[[Файл:PersistentQueue_state4.png|300px|nothumb|left|]]

<br clear = "all"/>

[[Файл:PersistentQueue_state7.png|300px|nothumb|left|]]

<br clear = "all"/>

[[Файл:PersistentQueue_State9.png|300px|nothumb|left|]]

<br clear = "all"/>

[[Файл:PersistentQueue_state10.png|300px|nothumb|left|]]

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

* [http://hdl.handle.net/1813/6273 ''Hood R., Melville R.'' Real Time Queue Operations in Pure LISP. {{---}} Cornell University, 1980]

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Амортизационный анализ]]