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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Источники информации)
(Эффективная реализация)
Строка 1: Строка 1:
 
== Эффективная реализация ==
 
== Эффективная реализация ==
  
Попробуем решить задачу эффективнее. Заведем массив запросов, модифицирующих стек.<br>
+
Заведем массив запросов, модифицирующих стек.<br>
 
У каждого элемента массива будет <tex>2</tex> поля: значение в вершине стека и индекс предыдущей версии стека.<br>
 
У каждого элемента массива будет <tex>2</tex> поля: значение в вершине стека и индекс предыдущей версии стека.<br>
 
Тогда операции push и pop будут иметь следующий вид:<br>
 
Тогда операции push и pop будут иметь следующий вид:<br>
* <tex> \mathrm{push}(i, x)</tex> {{---}} добавляет элемент х в стек с номером i, результирующий стек будет иметь номер <tex> n + 1 </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'''):

Версия 21:29, 5 июня 2015

Эффективная реализация

Заведем массив запросов, модифицирующих стек.
У каждого элемента массива будет [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):
   T k = s[i]
   k = s[k.prev]
   push(k.prev, k.value)

Пример

  • Пусть изначально у нас есть один пустой стек. Запишем его в массив.
Стек1.png
index 1
value [math]null[/math]
prev [math]null[/math]


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


  • Аналогично выполним [math]\mathrm{push}(2, 5)[/math]:
Стек3.png
index 1     2         3    
value [math]null[/math] 3 5
prev [math]null[/math] 1 2


  • Выполним [math]\mathrm{pop}(3)[/math]. он возвращает [math]5[/math] и копирует 2-ую вершину.
Стек4.png
index 1     2         3         4    
value [math]null[/math] 3 5 3
prev [math]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]null[/math] 3 5 3 6 1 [math]null[/math] 5 9
prev [math]null[/math] 1 2 1 3 5 [math]null[/math] 2 7


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

См. также

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