120
правок
Изменения
Уменьшены изображения
Пусть мы создали персистентную очередь. Будем изображать ее в виде пяти персистентных стеков, закрашенные вершины {{---}} текущие версии стеков, соответствующие текущему состоянию очереди; стрелка от стека <tex>R'</tex> указывает на ту версию стека <tex>R</tex>, которая там сейчас хранится. В самих вершинах записаны соответствующие этим вершинам значения.
[[Файл:PersistentQueue_state0.png|500px300px|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|500px300px|nothumb|left|]]
<br clear = "all"/>
Сделаем операцию <tex> push(2) </tex>, у нас обычный режим, поэтому элемент пойдет в стек <tex>L</tex>, перекопирование не активируется.
[[Файл:PersistentQueue_state2.png|500px300px|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|500px300px|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|500px300px|nothumb|left|]]
<br clear = "all"/>
Сделаем операцию <tex> push(5) </tex>, у нас обычный режим, поэтому элемент пойдет в стек <tex>L</tex>, перекопирование не активируется.
[[Файл:PersistentQueue_state5.png|500px300px|nothumb|left|]]
<br clear = "all"/>
Сделаем операцию <tex> push(6) </tex>, у нас обычный режим, поэтому элемент пойдет в стек <tex>L</tex>, перекопирование не активируется.
[[Файл:PersistentQueue_state6.png|500px300px|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|500px300px|nothumb|left|]]
<br clear = "all"/>
Сделаем операцию <tex>pop</tex>, мы находимся в режиме перекопирования, так что элемент извлекается из <tex>R'</tex>, <tex>toCopy = 2</tex>. За три операции мы успеваем перекопировать три элемента стека <tex>L</tex> в стек <tex>R</tex>.
[[Файл:PersistentQueue_state8.png|500px300px|nothumb|left|]]
<br clear = "all"/>
Сделаем операцию <tex>pop</tex>, мы находимся в режиме перекопирования, так что элемент извлекается из <tex>R'</tex>, <tex>toCopy = 1</tex>. За три операции мы успеваем перекопировать один элемент стека <tex>L</tex> в стек <tex>R</tex>, а также извлечь два элемента стека <tex>T</tex>, с учетом <tex>toCopy</tex> только один элемент попадет в стек <tex>R</tex>, <tex>toCopy = 0</tex>.
[[Файл:PersistentQueue_State9.png|500px300px|nothumb|left|]]
<br clear = "all"/>
Сделаем операцию <tex>pop</tex>, мы находимся в режиме перекопирования, так что элемент извлекается из <tex>R'</tex>, но <tex>toCopy = 0</tex>, так что нам приходится извлечь еше один элемент из стека <tex>R</tex>. Мы извлекаем один элемент из стека <tex>T</tex>, перекопирование заканчивается, стеки <tex>L, L'</tex> меняются местами.
[[Файл:PersistentQueue_state10.png|500px300px|nothumb|left|]]
<br clear = "all"/>
