Персистентный стек — различия между версиями
(→Эффективная реализация) |
м (rollbackEdits.php mass rollback) |
||
(не показаны 34 промежуточные версии 5 участников) | |||
Строка 1: | Строка 1: | ||
− | == | + | == Алгоритм == |
− | + | === Реализация на массиве === | |
− | У каждого элемента массива будет 2 поля: значение в вершине стека и индекс предыдущей версии стека.<br> | + | Заведем массив запросов, модифицирующих стек.<br> |
+ | '''struct''' '''Query''': | ||
+ | '''T''' value | ||
+ | '''uint''' prev | ||
+ | У каждого элемента массива будет <tex>2</tex> поля: значение в вершине стека и индекс предыдущей версии стека.<br> | ||
Тогда операции push и pop будут иметь следующий вид:<br> | Тогда операции push и pop будут иметь следующий вид:<br> | ||
− | * <tex> \mathrm{push}(i, x)</tex> {{---}} добавляет элемент | + | * <tex> \mathrm{push}(i, x)</tex> {{---}} добавляет элемент <tex>x</tex> в стек с номером <tex>i</tex>, результирующий стек будет иметь номер <tex> n + 1 </tex>, |
− | function push(i : uint, x : T): | + | '''function''' push(i : '''uint''', x : '''T'''): |
− | s.top = s.top + 1 | + | s.top = s.top + 1 |
− | s[s.top].value = x | + | s[s.top].value = x |
− | s[s.top].prev = i | + | s[s.top].prev = i |
− | * <tex>\mathrm{pop}(i)</tex> {{---}} возвращает значение, хранящееся в элементе с номером i и копирует элемент, предыдущий для него | + | * <tex>\mathrm{pop}(i)</tex> {{---}} возвращает значение, хранящееся в элементе с номером <tex>i</tex> и копирует элемент, предыдущий для него, результирующий стек будет иметь номер <tex> n + 1 </tex>. |
− | результирующий стек будет иметь номер <tex> n + 1 </tex>. | + | '''T''' pop(i : '''uint'''): |
− | T pop(i : uint): | + | '''Query''' k = s[i] |
− | + | k = s[k.prev] | |
− | k = s[k.prev] | + | push(k.prev, k.value) |
− | push(k.prev, k.value) | + | '''return''' s[i].value |
+ | |||
+ | === Реализация на списке === | ||
+ | Будем использовать узел, у которого будет значение и ссылка на прошлую версию стека. При этом сам узел - это версия стека. | ||
+ | '''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 | ||
+ | |||
+ | * <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) | ||
== Пример == | == Пример == | ||
− | + | Пусть изначально у нас есть один пустой стек. Запишем его в массив. | |
[[Файл:стек1.png|500px|nothumb|right|]] | [[Файл:стек1.png|500px|nothumb|right|]] | ||
{| border = 1; cellspacing = 0; class="wikitable" | {| border = 1; cellspacing = 0; class="wikitable" | ||
Строка 26: | Строка 52: | ||
|-align = "center" | |-align = "center" | ||
!value | !value | ||
− | |<tex>null</tex> | + | |<tex>\mathtt{null}</tex> |
|-align = "center" | |-align = "center" | ||
!prev | !prev | ||
− | |<tex>null</tex> | + | |<tex>\mathtt{null}</tex> |
|} | |} | ||
− | + | Далее выполним <tex>\mathrm{push}(1, 3)</tex>. Создается новая вершина со значением <tex>3</tex>, ссылающаяся на 1-ую, помещаем ее во 2-ую ячейку массива: | |
[[Файл:стек2.png|500px|nothumb|right|]] | [[Файл:стек2.png|500px|nothumb|right|]] | ||
{| border = 1; cellspacing = 0; class="wikitable" | {| border = 1; cellspacing = 0; class="wikitable" | ||
Строка 42: | Строка 68: | ||
|-align = "center" | |-align = "center" | ||
!value | !value | ||
− | |<tex>null</tex> | + | |<tex>\mathtt{null}</tex> |
|3 | |3 | ||
|-align = "center" | |-align = "center" | ||
!prev | !prev | ||
− | |<tex>null</tex> | + | |<tex>\mathtt{null}</tex> |
|1 | |1 | ||
|} | |} | ||
− | + | Аналогично выполним <tex>\mathrm{push}(2, 5)</tex>: | |
[[Файл:стек3.png|500px|nothumb|right|]] | [[Файл:стек3.png|500px|nothumb|right|]] | ||
{| border = 1; cellspacing = 0; class="wikitable" | {| border = 1; cellspacing = 0; class="wikitable" | ||
Строка 61: | Строка 87: | ||
|-align = "center" | |-align = "center" | ||
!value | !value | ||
− | |<tex>null</tex> | + | |<tex>\mathtt{null}</tex> |
|3 | |3 | ||
|5 | |5 | ||
|-align = "center" | |-align = "center" | ||
!prev | !prev | ||
− | |<tex>null</tex> | + | |<tex>\mathtt{null}</tex> |
|1 | |1 | ||
|2 | |2 | ||
Строка 72: | Строка 98: | ||
− | + | Выполним <tex>\mathrm{pop}(3)</tex>. Он возвращает <tex>5</tex> и копирует 2-ую вершину. | |
[[Файл:стек4.png|500px|nothumb|right|]] | [[Файл:стек4.png|500px|nothumb|right|]] | ||
{| border = 1; cellspacing = 0; class="wikitable" | {| border = 1; cellspacing = 0; class="wikitable" | ||
Строка 83: | Строка 109: | ||
|-align = "center" | |-align = "center" | ||
!value | !value | ||
− | |<tex>null</tex> | + | |<tex>\mathtt{null}</tex> |
|3 | |3 | ||
|5 | |5 | ||
Строка 89: | Строка 115: | ||
|-align = "center" | |-align = "center" | ||
!prev | !prev | ||
− | |<tex>null</tex> | + | |<tex>\mathtt{null}</tex> |
|1 | |1 | ||
|2 | |2 | ||
Строка 96: | Строка 122: | ||
− | + | Так будет выглядеть массив после последовательности операций <tex>\mathrm{push}(3, 6), \mathrm{push}(5, 1), \mathrm{pop}(4), \mathrm{pop}(5), \mathrm{push}(7, 9):</tex> | |
[[Файл:стек.png|500px|nothumb|right|]] | [[Файл:стек.png|500px|nothumb|right|]] | ||
{| border = 1; cellspacing = 0; class="wikitable" | {| border = 1; cellspacing = 0; class="wikitable" | ||
Строка 112: | Строка 138: | ||
|-align = "center" | |-align = "center" | ||
!value | !value | ||
− | |<tex>null</tex> | + | |<tex>\mathtt{null}</tex> |
|3 | |3 | ||
|5 | |5 | ||
Строка 118: | Строка 144: | ||
|6 | |6 | ||
|1 | |1 | ||
− | |<tex>null</tex> | + | |<tex>\mathtt{null}</tex> |
|5 | |5 | ||
|9 | |9 | ||
|-align = "center" | |-align = "center" | ||
!prev | !prev | ||
− | |<tex>null</tex> | + | |<tex>\mathtt{null}</tex> |
|1 | |1 | ||
|2 | |2 | ||
Строка 129: | Строка 155: | ||
|3 | |3 | ||
|5 | |5 | ||
− | |<tex>null</tex> | + | |<tex>\mathtt{null}</tex> |
|2 | |2 | ||
|7 | |7 | ||
Строка 137: | Строка 163: | ||
В итоге мы имеем доступ ко всем версиям стека за <tex>O(1)</tex> времени и <tex>O(n)</tex> памяти. | В итоге мы имеем доступ ко всем версиям стека за <tex>O(1)</tex> времени и <tex>O(n)</tex> памяти. | ||
− | + | == Применение == | |
+ | Используя персистентый стек, можно реализовать легко перстистентную очередь (если вспомнить её реализацию на двух стеках). <br> | ||
+ | См. [[Персистентная очередь]] | ||
== См. также== | == См. также== | ||
Строка 146: | Строка 174: | ||
== Источники информации == | == Источники информации == | ||
− | * [http://habrahabr.ru/blogs/algorithm/113585/ Habrahabr - Персистентный стек] | + | * [http://habrahabr.ru/blogs/algorithm/113585/ Habrahabr {{---}} Персистентный стек] |
[[Категория:Дискретная математика и алгоритмы]] | [[Категория:Дискретная математика и алгоритмы]] | ||
[[Категория: Амортизационный анализ]] | [[Категория: Амортизационный анализ]] | ||
+ | [[Категория: Структуры данных]] |
Текущая версия на 19:33, 4 сентября 2022
Содержание
Алгоритм
Реализация на массиве
Заведем массив запросов, модифицирующих стек.
struct Query: T value uint prev
У каждого элемента массива будет
Тогда операции push и pop будут иметь следующий вид:
- — добавляет элемент в стек с номером , результирующий стек будет иметь номер ,
function push(i : uint, x : T): s.top = s.top + 1 s[s.top].value = x s[s.top].prev = i
- — возвращает значение, хранящееся в элементе с номером и копирует элемент, предыдущий для него, результирующий стек будет иметь номер .
T pop(i : uint): Query k = s[i] k = s[k.prev] push(k.prev, k.value) return s[i].value
Реализация на списке
Будем использовать узел, у которого будет значение и ссылка на прошлую версию стека. При этом сам узел - это версия стека.
struct Node: T value Node prev
Будем хранить состояния в узлах. Будем возвращать пользователю информацию о текущей вершине.
У каждого узла будет поля: значение в вершине стека и ссылка на предыдущую версию стека.
Сам персистентный стек будет обозначаться .
- — добавляет элемент в стек узла ,
Stack push(i : Node, x : T): k.value = x k.prev = i s.top = k return s
- — возвращает значение, хранящееся в узле и копирует элемент, предыдущий для него.
pair<T, Stack> pop(i : Node): T val = i.value i = i.prev return pair(val, s)
Пример
Пусть изначально у нас есть один пустой стек. Запишем его в массив.
index | 1 |
---|---|
value | |
prev |
Далее выполним . Создается новая вершина со значением , ссылающаяся на 1-ую, помещаем ее во 2-ую ячейку массива:
index | 1 | 2 |
---|---|---|
value | 3 | |
prev | 1 |
Аналогично выполним :
index | 1 | 2 | 3 |
---|---|---|---|
value | 3 | 5 | |
prev | 1 | 2 |
Выполним . Он возвращает и копирует 2-ую вершину.
index | 1 | 2 | 3 | 4 |
---|---|---|---|---|
value | 3 | 5 | 3 | |
prev | 1 | 2 | 1 |
Так будет выглядеть массив после последовательности операций
index | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
value | 3 | 5 | 3 | 6 | 1 | 5 | 9 | ||
prev | 1 | 2 | 1 | 3 | 5 | 2 | 7 |
В итоге мы имеем доступ ко всем версиям стека за времени и памяти.
Применение
Используя персистентый стек, можно реализовать легко перстистентную очередь (если вспомнить её реализацию на двух стеках).
См. Персистентная очередь