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