Изменения

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

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

356 байт добавлено, 12:16, 10 июня 2013
Добавлен пример последовательности операций с персистентной очередью
<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|500px|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|500px|nothumb|left|]]
<br clear = "all"/>
Сделаем операцию <tex>pop</tex>, мы находимся в режиме перекопирования, так что элемент извлекается из <tex>R'</tex>, <tex>toCopy = 2</tex>. За три операции мы успеваем перекопировать три элемента стека <tex>L</tex> в стек <tex>R</tex>.
[[Файл:PersistentQueue_state8.png|500px|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|500px|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|500px|nothumb|left|]]
120
правок

Навигация