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