Персистентный стек

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

Алгоритм

Реализация на массиве

Заведем массив запросов, модифицирующих стек.

 struct Query:
   T value
   uint prev

У каждого элемента массива будет $2$ поля: значение в вершине стека и индекс предыдущей версии стека.
Тогда операции push и pop будут иметь следующий вид:

• $\mathrm{push}(i, x)$ — добавляет элемент $x$ в стек с номером $i$, результирующий стек будет иметь номер $n + 1$,

 function push(i : uint, x : T):
   s.top = s.top + 1
   s[s.top].value = x
   s[s.top].prev = i 

• $\mathrm{pop}(i)$ — возвращает значение, хранящееся в элементе с номером $i$ и копирует элемент, предыдущий для него, результирующий стек будет иметь номер $n + 1$.

 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

Будем хранить состояния в узлах. Будем возвращать пользователю информацию о текущей вершине.
У каждого узла будет $2$ поля: значение в вершине стека и ссылка на предыдущую версию стека.
Сам персистентный стек будет обозначаться $s$.

• $\mathrm{push}(i, x)$ — добавляет элемент $x$ в стек узла $i$,

 Stack push(i : Node, x : T):
   k.value = x
   k.prev = i
   s.top = k
   return s

• $\mathrm{pop}(i)$ — возвращает значение, хранящееся в узле $i$ и копирует элемент, предыдущий для него.

 pair<T, Stack> pop(i : Node):
   T val = i.value 
   i = i.prev
   return pair(val, s)

Пример

Пусть изначально у нас есть один пустой стек. Запишем его в массив.

index	1
value	$\mathtt{null}$
prev	$\mathtt{null}$

Далее выполним $\mathrm{push}(1, 3)$. Создается новая вершина со значением $3$, ссылающаяся на 1-ую, помещаем ее во 2-ую ячейку массива:

index	1	2
value	$\mathtt{null}$	3
prev	$\mathtt{null}$	1

Аналогично выполним $\mathrm{push}(2, 5)$:

index	1	2	3
value	$\mathtt{null}$	3	5
prev	$\mathtt{null}$	1	2

Выполним $\mathrm{pop}(3)$. Он возвращает $5$ и копирует 2-ую вершину.

index	1	2	3	4
value	$\mathtt{null}$	3	5	3
prev	$\mathtt{null}$	1	2	1

Так будет выглядеть массив после последовательности операций $\mathrm{push}(3, 6), \mathrm{push}(5, 1), \mathrm{pop}(4), \mathrm{pop}(5), \mathrm{push}(7, 9):$

index	1	2	3	4	5	6	7	8	9
value	$\mathtt{null}$	3	5	3	6	1	$\mathtt{null}$	5	9
prev	$\mathtt{null}$	1	2	1	3	5	$\mathtt{null}$	2	7

В итоге мы имеем доступ ко всем версиям стека за $O(1)$ времени и $O(n)$ памяти.

Применение

Используя персистентый стек, можно реализовать легко перстистентную очередь (если вспомнить её реализацию на двух стеках).
См. Персистентная очередь

См. также

• Стек
• Персистентный дек

Источники информации

• Habrahabr — Персистентный стек