Персистентный стек — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм)
м (rollbackEdits.php mass rollback)
 
(не показаны 4 промежуточные версии 3 участников)
Строка 6: Строка 6:
 
     '''T''' value
 
     '''T''' value
 
     '''uint''' prev
 
     '''uint''' prev
 
 
У каждого элемента массива будет <tex>2</tex> поля: значение в вершине стека и индекс предыдущей версии стека.<br>
 
У каждого элемента массива будет <tex>2</tex> поля: значение в вершине стека и индекс предыдущей версии стека.<br>
 
Тогда операции push и pop будут иметь следующий вид:<br>
 
Тогда операции push и pop будут иметь следующий вид:<br>
Строка 28: Строка 27:
 
Будем хранить состояния в узлах. Будем возвращать пользователю информацию о текущей вершине.<br>
 
Будем хранить состояния в узлах. Будем возвращать пользователю информацию о текущей вершине.<br>
 
У каждого узла будет <tex>2</tex> поля: значение в вершине стека и ссылка на предыдущую версию стека.<br>
 
У каждого узла будет <tex>2</tex> поля: значение в вершине стека и ссылка на предыдущую версию стека.<br>
Сам персистентный стек будет обозначатся <tex>s</tex>.<br>
+
Сам персистентный стек будет обозначаться <tex>s</tex>.<br>
  
 
* <tex> \mathrm{push}(i, x)</tex> {{---}} добавляет элемент <tex>x</tex> в стек узла <tex>i</tex>,
 
* <tex> \mathrm{push}(i, x)</tex> {{---}} добавляет элемент <tex>x</tex> в стек узла <tex>i</tex>,
Строка 99: Строка 98:
  
  
Выполним <tex>\mathrm{pop}(3)</tex>. он возвращает <tex>5</tex> и копирует 2-ую вершину.
+
Выполним <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"

Текущая версия на 19:33, 4 сентября 2022

Алгоритм

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

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

 struct Query:
   T value
   uint prev

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

  • [math] \mathrm{push}(i, x)[/math] — добавляет элемент [math]x[/math] в стек с номером [math]i[/math], результирующий стек будет иметь номер [math] n + 1 [/math],
 function push(i : uint, x : T):
   s.top = s.top + 1
   s[s.top].value = x
   s[s.top].prev = i 
  • [math]\mathrm{pop}(i)[/math] — возвращает значение, хранящееся в элементе с номером [math]i[/math] и копирует элемент, предыдущий для него, результирующий стек будет иметь номер [math] n + 1 [/math].
 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

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

  • [math] \mathrm{push}(i, x)[/math] — добавляет элемент [math]x[/math] в стек узла [math]i[/math],
 Stack push(i : Node, x : T):
   k.value = x
   k.prev = i
   s.top = k
   return s
  • [math]\mathrm{pop}(i)[/math] — возвращает значение, хранящееся в узле [math]i[/math] и копирует элемент, предыдущий для него.
 pair<T, Stack> pop(i : Node):
   T val = i.value 
   i = i.prev
   return pair(val, s)

Пример

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

Стек1.png
index 1
value [math]\mathtt{null}[/math]
prev [math]\mathtt{null}[/math]


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

Стек2.png
index 1     2    
value [math]\mathtt{null}[/math] 3
prev [math]\mathtt{null}[/math] 1


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

Стек3.png
index 1     2         3    
value [math]\mathtt{null}[/math] 3 5
prev [math]\mathtt{null}[/math] 1 2


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

Стек4.png
index 1     2         3         4    
value [math]\mathtt{null}[/math] 3 5 3
prev [math]\mathtt{null}[/math] 1 2 1


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

Стек.png
index 1     2         3         4         5         6         7         8         9    
value [math]\mathtt{null}[/math] 3 5 3 6 1 [math]\mathtt{null}[/math] 5 9
prev [math]\mathtt{null}[/math] 1 2 1 3 5 [math]\mathtt{null}[/math] 2 7


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

Применение

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

См. также

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