Изменения

!!не дописано!!{{Определение|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

* <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

Самое простое и очевидное решение этой задачи — симуляция описанного процесса, т.е. честное копирование стека при каждой операции. <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>стек1.png|500px|nothumb|right|]]{| border = 1; cellspacing = 0; class="wikitable"|- align = "center"!index!1|-align = "center"!value* |<tex>push(x, i)\mathtt{null}</tex> |- создает новый элемент со значением x, который ссылается на элемент с номером i как на предыдущий элемент в стеке.align = "center"!prev* |<tex>pop(i)\mathtt{null}</tex> - возвращает значение, хранящееся в элементе с номером i и копирует элемент, предыдущий для него.|}

Пусть изначально у нас есть один пустой стек. Для удобства, будем хранить его как «голову» с пометкой пустого стека:Далее выполним <brtex>[[Файл:B5bb212f3702e565498c4412e13242a7.jpg|nothumb]]<br><br><br>Далее выполним \mathrm{push}(1, 53)</tex>. Создается новая вершина со значением 5<tex>3</tex>, ссылающаяся на 1-ую, помещаем ее во 2-ую ячейку массива:[[Файл:612b6fe1562242b3a455b2abb698dfc9стек2.jpgpng|500px|nothumb|right|]]{| border = 1; cellspacing = 0; class="wikitable"|- align = "center"!index!1!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;|-align = "center"!value|<brtex>\mathtt{null}<br/tex><br>|3|-align = "center"Аналогично выполним push(2, 10) и push(1, 6):!prev|<brtex>\mathtt{null}<br/tex>[[Файл:2beb71892fd79b675e095d5432827d03.jpg|nothumb]]1<br>|}

Аналогично выполним <brtex>\mathrm{push}(2, 5)<br/tex>:Очевидно, что все 4 стека сейчас верно построены и легко восстанавливаются[[Файл:стек3. Давайте теперь попробуем выполнить последовательно операции pop(png|500px|nothumb|right|]]{| border = 1; cellspacing = 0; class="wikitable"|- align = "center"!index!1!&nbsp;&nbsp;&nbsp;&nbsp;2) и pop(&nbsp;&nbsp;&nbsp;&nbsp;!&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;|-align = "center"!value|<tex>\mathtt{null}</tex>|3):|5|-align = "center"!prev|<tex>\mathtt{null}</tex>|1|2|}

Выполним <brtex>\mathrm{pop}(3)<br/tex>. Он возвращает <tex>5</tex> и копирует 2-ую вершину.[[Файл:стек4.png|500px|nothumb|right|]]{| border = 1; cellspacing = 0; class="wikitable"|- align = "center"!index!1!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;!&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;!&nbsp;&nbsp;&nbsp;&nbsp;4&nbsp;&nbsp;&nbsp;&nbsp;|-align = "center"!value|<tex>\mathtt{null}</tex>|3|5|3|-align = "center"!prev|<tex>\mathtt{null}</tex>|1|2|1|}

Так будет выглядеть массив после последовательности операций <tex>\mathrm{push}(3, 6), \mathrm{push}(5, 1), \mathrm{pop}(34), \mathrm{pop}(5), \mathrm{push}(7, 9) возвращает 10 и копирует 2-ую вершину: получаем шестой стек.<br><br/tex>[[Файл:Eced2ebbcee643d6c87576b0d3460785стек.jpgpng|500px|nothumb|right|]]{| border = 1; cellspacing = 0; class="wikitable"|- align = "center"!index!1!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;!&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;!&nbsp;&nbsp;&nbsp;&nbsp;4&nbsp;&nbsp;&nbsp;&nbsp;!&nbsp;&nbsp;&nbsp;&nbsp;5&nbsp;&nbsp;&nbsp;&nbsp;!&nbsp;&nbsp;&nbsp;&nbsp;6&nbsp;&nbsp;&nbsp;&nbsp;!&nbsp;&nbsp;&nbsp;&nbsp;7&nbsp;&nbsp;&nbsp;&nbsp;!&nbsp;&nbsp;&nbsp;&nbsp;8&nbsp;&nbsp;&nbsp;&nbsp;!&nbsp;&nbsp;&nbsp;&nbsp;9&nbsp;&nbsp;&nbsp;&nbsp;|-align = "center"!value|<tex>\mathtt{null}<br/tex>|3|5|3|6|1|<brtex>\mathtt{null}<br/tex>|5|9|-align = "center"!prev|<tex>\mathtt{null}<br/tex>|1|2|1|3|5|<tex>\mathtt{null}</tex>|2|7|}

== Ссылки Источники информации ==

* [http://habrahabr.ru/blogs/algorithm/113585/ Habrahabr {{---}} Персистентный стек - статья на хабре]

[[Категория: Амортизационный анализ]][[Категория: Структуры данных ]]