1632
правки
Изменения
м
{{Определение|definition=Персистентными структурами данных называются такие структуры, что при всяком их изменении остается доступ ко всем предыдущим версиям этой структуры.}}= Алгоритм ==
Рассмотрим такую структуру === Реализация на примере массиве ===Заведем массив запросов, модифицирующих стек.<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'''): '''Query''' k = s[i] k = s[k.prev] push(k.prev, k.value) '''return''' s[i].value
Самое простое и очевидное решение этой задачи — честное копирование стека при каждой операции. <br>Очевидно, что это не самое эффективное решение. Сложность одной операции составляет * <tex>O\mathrm{pop}(ni)</tex> и количество требуемой памяти — {{---}} возвращает значение, хранящееся в узле <tex>O(n * n)i</tex>и копирует элемент, предыдущий для него. '''pair<T, Stack>''' pop(i : '''Node'''): '''T''' val = i.value i = i.prev '''return''' pair(val, s)
Попробуем решить задачу эффективнее. Заведем массив указателей, ссылающихся на каждую версию стека.
Вместо n копий стека будем хранить n первых элементов. Тогда операции push и pop будут иметь следующий вид:<br>* Далее выполним <tex>\mathrm{push}(x1, i3)</tex> - создает новый элемент . Создается новая вершина со значением x<tex>3</tex>, который ссылается ссылающаяся на элемент с номером i как на предыдущий элемент в стеке1-ую, помещаем ее во 2-ую ячейку массива:[[Файл:стек2.png|500px|nothumb|right|]]{| border = 1; cellspacing = 0; class="wikitable"* |- align = "center"!index!1! 2 |-align = "center"!value|<tex>pop(i)\mathtt{null}</tex> |3|- возвращает значение, хранящееся в элементе с номером i и копирует элемент, предыдущий для него.align = "center"!prev|<tex>\mathtt{null}</tex>Результирующие стеки будут иметь номер n + |1.|}
== Пример ==
Пусть изначально у нас есть один пустой стек. Для удобства, будем хранить его как «голову» с пометкой пустого стека:Выполним <brtex>[[Файл:B5bb212f3702e565498c4412e13242a7.jpg|Картинка]]\mathrm{pop}(3)<br/tex><br><br>Далее выполним . Он возвращает <tex>push(1, 5)</tex>. Создается новая вершина со значением 5, ссылающаяся на 1и копирует 2-ую:<br>вершину.[[Файл:612b6fe1562242b3a455b2abb698dfc9стек4.jpgpng|500px|nothumb|right|]]<br><br>{| border = 1; cellspacing = 0; class="wikitable"|- align = "center"!index!1! 2 ! 3 ! 4 |-align = "center"!valueАналогично выполним |<tex>push(2, 10)\mathtt{null}</tex> и |3|5|3|-align = "center"!prev|<tex>push(1, 6)\mathtt{null}</tex>:<br><br>|1|2[[Файл:2beb71892fd79b675e095d5432827d03.jpg|nothumb]]1<br>|}
Очевидно, что все 4 стека сейчас верно построены и легко восстанавливаются. Давайте теперь попробуем выполнить последовательно операции <tex>pop(2)</tex> и <tex>pop(3)</tex>:
<br>* Так будет выглядеть массив после последовательности операций <tex>\mathrm{push}(3, 6), \mathrm{push}(5, 1), \mathrm{pop}(24), \mathrm{pop}(5), \mathrm{push}(7, 9):</tex> возвращает 5 и копирует 1-ую вершину. Результирующий пятый стек — пустой.<br>[[Файл:3ab7456751529d76c5f1392d5d3b5fcbстек.jpgpng|500px|nothumb|right|]]{| border = 1; cellspacing = 0; class="wikitable"|- align = "center"!index!1! 2 ! 3 ! 4 ! 5 ! 6 ! 7 ! 8 ! 9 |-align = "center"!value|<tex>\mathtt{null}</tex>|3|5|3|6|1|<tex>\mathtt{null}</tex>|5|9|-align = "center"!prev|<tex>\mathtt{null}</tex>|1|2|1|3|5|<tex>\mathtt{null}</tex>|2|7|}
<br><br>
* В итоге мы имеем доступ ко всем версиям стека за <tex>popO(31)</tex> возвращает 10 времени и копирует 2-ую вершину: получаем шестой стек.<brtex>O(n)<br/tex>[[Файл:Eced2ebbcee643d6c87576b0d3460785памяти.jpg|nothumb]]<br><br>
В итоге мы имеем доступ ко всем версиям стека за <tex>O== Применение ==Используя персистентый стек, можно реализовать легко перстистентную очередь (1если вспомнить её реализацию на двух стеках). </tex> времени и <texbr>O(n)</tex> памяти (массив длины n и n самих "стеков")См.[[Персистентная очередь]]
rollbackEdits.php mass rollback
=== Реализация на списке ===
Будем использовать узел, у которого будет значение и ссылка на прошлую версию стека. При этом сам узел - это версия стека.
'''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>, '''Stack''' push(i : '''Node''', x : '''T'''): k.value =x k.prev = Наивная реализация =i s.top =k '''return''' s
== Эффективная реализация Пример ==
Пусть изначально у нас есть один пустой стек. Запишем его в массив.
[[Файл:стек1.png|500px|nothumb|right|]]
{| border = 1; cellspacing = 0; class="wikitable"
|- align = "center"
!index
!1
|-align = "center"
!value
|<tex>\mathtt{null}</tex>
|-align = "center"
!prev
|<tex>\mathtt{null}</tex>
|}
Аналогично выполним <tex>\mathrm{push}(2, 5)</tex>:
[[Файл:стек3.png|500px|nothumb|right|]]
{| border = 1; cellspacing = 0; class="wikitable"
|- align = "center"
!index
!1
! 2
! 3
|-align = "center"
!value
|<tex>\mathtt{null}</tex>
|3
|5
|-align = "center"
!prev
|<tex>\mathtt{null}</tex>
|1
|2
|}
== См. также==
* [[Персистентный дек]]
== Ссылки Источники информации ==
* [http://habrahabr.ru/blogs/algorithm/113585/ Habrahabr {{---}} Персистентный стек - статья на хабре]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]][[Категория: Структуры данных ]]
