234
правки
Изменения
Нет описания правки
{{Определение
|definition=Персистентными структурами данных мы будем называть такие структуры, что при всяком их изменении остается доступ ко всем предыдущим версиям этой структуры.
* <tex>push(x, i)</tex> - создает новый элемент со значением x, который ссылается на элемент с номером i как на предыдущий элемент в стеке.
* <tex>pop(i)</tex> - возвращает значение, хранящееся в элементе с номером i и копирует элемент, предыдущий для него.
Результирующие стеки будут иметь номер n + 1.
== Пример:==
Пусть изначально у нас есть один пустой стек. Для удобства, будем хранить его как «голову» с пометкой пустого стека:
<br>
<br>
Далее выполним <tex>push(1, 5)</tex>. Создается новая вершина со значением 5, ссылающаяся на 1-ую:<br>
[[Файл:612b6fe1562242b3a455b2abb698dfc9.jpg|nothumb]]<br>
<br>
Аналогично выполним <brtex>Аналогично выполним push(2, 10) </tex> и <tex>push(1, 6)</tex>:
<br><br>
[[Файл:2beb71892fd79b675e095d5432827d03.jpg|nothumb]]
<br>
<br>
* <tex>pop(2) </tex> возвращает 5 и копирует 1-ую вершину. Результирующий пятый стек — пустой.
<br>
[[Файл:3ab7456751529d76c5f1392d5d3b5fcb.jpg|nothumb]]
<br><br>
* <brtex><br> pop(3) </tex> возвращает 10 и копирует 2-ую вершину: получаем шестой стек.
<br><br>
[[Файл:Eced2ebbcee643d6c87576b0d3460785.jpg|nothumb]]<br>
В итоге мы имеем доступ ко всем версиям стека за <tex>O(1)</tex> времени и <tex>O(n)</tex> памяти.
== См. также==
