Изменения

Перейти к: навигация, поиск

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

56 байт добавлено, 09:46, 11 июня 2013
Пример
= Пример =
Пусть мы создали персистентную очередь. Будем изображать ее в виде пяти деревьев версий персистентных стеков, закрашенные вершины {{---}} текущие версии стеков, соответствующие текущему состоянию очереди; стрелка от стека <tex>R'</tex> указывает на ту версию стека <tex>R</tex>, которая там сейчас хранится. В самих вершинах записаны соответствующие этим вершинам значения.
[[Файл:PersistentQueue_state0.png|300px|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|300px|nothumb|left|]]
<br clear = "all"/>
Сделаем операцию <tex> push(3) </tex>, у нас обычный режим, поэтому элемент пойдет в стек <tex>L</tex>, активируется перекопирование, <tex>R' = R</tex>, за три операции мы успеваем переложить перекопировать элемент стека <tex>R</tex> в стек <tex>T</tex>, а также переложить перекопировать два элемента стека <tex>L</tex> в стек <tex>R</tex>.
[[Файл:PersistentQueue_state3.png|300px|nothumb|left|]]
<br clear = "all"/>
Сделаем операцию <tex> push(7) </tex>, у нас обычный режим, поэтому элемент пойдет в стек <tex>L</tex>, перекопирование активируется, <tex>R' = R</tex>, <tex>toCopy=3</tex>, за три операции мы успеваем переместить перекопировать содержимое стека <tex>R</tex> в стек <tex>T</tex>.
[[Файл:PersistentQueue_state7.png|300px|nothumb|left|]]
120
правок

Навигация