24
правки
Изменения
м
'''struct''' '''Node''': '''T''' value // Значение в узле '''Node''' prev // Ссылка на прошлую версию
Персистентный Используя персистентый стек используется не очень часто, так как сложные задачи с ним не придумать из-за его примитивностиможно реализовать легко перстистентную очередь (если вспомнить её реализацию на двух стеках). В основном используется когда нужно быстрое обращение по результатам команд добавить/удалить<br>См.[[Персистентная очередь]]
Правка орфографии
== Алгоритм ==
=== Реализация на массиве ===
Заведем массив запросов, модифицирующих стек.<br>
'''struct''' '''Query''':
'''T''' value
'''uint''' prev
У каждого элемента массива будет <tex>2</tex> поля: значение в вершине стека и индекс предыдущей версии стека.<br>
Тогда операции push и pop будут иметь следующий вид:<br>
* <tex>\mathrm{pop}(i)</tex> {{---}} возвращает значение, хранящееся в элементе с номером <tex>i</tex> и копирует элемент, предыдущий для него, результирующий стек будет иметь номер <tex> n + 1 </tex>.
'''T''' pop(i : '''uint'''):
'''NodeQuery''' k = s[i]
k = s[k.prev]
push(k.prev, k.value)
=== Реализация на списке ===
Будем использовать узел, у которого будет значение и ссылка на прошлую версию стека. При этом сам узел - это версия стека. '''struct''' '''Node''': '''T''' value '''Node''' prev
Будем хранить состояния в узлах. Будем возвращать пользователю информацию о текущей вершине.<br>
У каждого узла будет <tex>2</tex> поля: значение в вершине стека и ссылка на предыдущую версию стека.<br>
Сам персистентный стек будет обозначатся обозначаться <tex>s</tex>.<br>
* <tex> \mathrm{push}(i, x)</tex> {{---}} добавляет элемент <tex>x</tex> в стек узла <tex>i</tex>,
* <tex>\mathrm{pop}(i)</tex> {{---}} возвращает значение, хранящееся в узле <tex>i</tex> и копирует элемент, предыдущий для него.
'''pair<T, Stack>''' pop(i : '''Node'''):
'''NodeT''' k val = i.prevvalue push(ki = i.prev, k.value) '''return''' pair(i.valueval, s)
== Пример ==
Выполним <tex>\mathrm{pop}(3)</tex>. он Он возвращает <tex>5</tex> и копирует 2-ую вершину.
[[Файл:стек4.png|500px|nothumb|right|]]
{| border = 1; cellspacing = 0; class="wikitable"
== Применение ==
== См. также==
