120
правок
Изменения
Нет описания правки
'''return''' <Ln, Ln', Rn, R', Tn, recopy, curCopy, curCopied>
</code>
= Пример =
Пусть мы создали персистентную очередь. Будем изображать ее в виде пяти персистентных стеков, закрашенные вершины {{---}} текущие версии стеков, соответствующие текущему состоянию очереди; стрелка от стека <tex>R'</tex> указывает на ту версию стека <tex>R</tex>, которая там сейчас хранится. В самих вершинах записаны соответствующие этим вершинам значения.
[[Файл:PersistentQueue_state0.png|500px|nothumb|left|]]
<br clear = "all"/>
Сделаем операцию <tex> push(1) </tex>, изначально режим обычный, так что элемент пойдет в стек <tex>L</tex>. Эта операция активирует режим перекопирования, в результате которого содержимое <tex>L</tex> переместится в стек <tex>R</tex>, после чего перекопирование завершится, стеки <tex>L, L'</tex> поменяются местами.
[[Файл:PersistentQueue_state1.png|500px|nothumb|left|]]
<br clear = "all"/>
Сделаем операцию <tex> push(2) </tex>, у нас обычный режим, поэтому элемент пойдет в стек <tex>L</tex>, перекопирование не активируется.
[[Файл:PersistentQueue_state2.png|500px|nothumb|left|]]
<br clear = "all"/>
Сделаем операцию <tex> push(3) </tex>, у нас обычный режим, поэтому элемент пойдет в стек <tex>L</tex>, активируется перекопирование, за три операции мы успеваем переложить элемент стека <tex>R</tex> в стек <tex>T</tex>, а также переложить два элемента стека <tex>L</tex> в стек <tex>R</tex>.
[[Файл:PersistentQueue_state3.png|500px|nothumb|left|]]
<br clear = "all"/>
Сделаем операцию <tex> push(4) </tex>, мы в режиме перекопирования, поэтому элемент пойдет в стек <tex>L'</tex>, далее мы успеваем перекопировать обратно элемент из стека <tex>T</tex> в стек <tex>R</tex>, перекопирование завершается, стеки <tex>L, L'</tex> меняются местами.
[[Файл:PersistentQueue_state4.png|500px|nothumb|left|]]
<br clear = "all"/>
Сделаем операцию <tex> push(5) </tex>, у нас обычный режим, поэтому элемент пойдет в стек <tex>L</tex>, перекопирование не активируется.
[[Файл:PersistentQueue_state5.png|500px|nothumb|left|]]
<br clear = "all"/>
Сделаем операцию <tex> push(6) </tex>, у нас обычный режим, поэтому элемент пойдет в стек <tex>L</tex>, перекопирование не активируется.
[[Файл:PersistentQueue_state6.png|500px|nothumb|left|]]
<br clear = "all"/>
Сделаем операцию <tex> push(7) </tex>, у нас обычный режим, поэтому элемент пойдет в стек <tex>L</tex>, перекопирование активируется, за три операции мы успеваем переместить содержимое стека <tex>R</tex> в стек <tex>T</tex>.
[[Файл:PersistentQueue_state7.png|500px|nothumb|left|]]
<br clear = "all"/>
Сделаем операцию <tex>pop</tex>, мы находимся в режиме перекопирования, так что элемент извлекается из <tex>R'</tex>. За три операции мы успеваем перекопировать три элемента стека <tex>L</tex> в стек <tex>R</tex>.
[[Файл:PersistentQueue_state8.png|500px|nothumb|left|]]
<br clear = "all"/>
Сделаем операцию <tex>pop</tex>, мы находимся в режиме перекопирования, так что элемент извлекается из <tex>R'</tex>. За три операции мы успеваем перекопировать один элемент стека <tex>L</tex> в стек <tex>R</tex>, а также извлечь два элемента стека <tex>T</tex>, с учетом <tex>toCopy</tex> только один элемент попадет в стек <tex>R</tex>.
[[Файл:PersistentQueue_State9.png|500px|nothumb|left|]]
<br clear = "all"/>
Сделаем операцию <tex>pop</tex>, мы находимся в режиме перекопирования, так что элемент извлекается из <tex>R'</tex>, но <tex>toCopy = 0</tex>, так что нам приходится извлечь еше один элемент
[[Файл:PersistentQueue_state10.png|500px|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]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]
