52
правки
Изменения
→Эффективная реализация
== Эффективная реализация ==
У каждого элемента массива будет <tex>2</tex> поля: значение в вершине стека и индекс предыдущей версии стека.<br>
Тогда операции push и pop будут иметь следующий вид:<br>
* <tex> \mathrm{push}(i, x)</tex> {{---}} добавляет элемент х <tex>x</tex> в стек с номером <tex>i</tex>, результирующий стек будет иметь номер <tex> n + 1 </tex>.
'''function''' push(i : '''uint''', x : '''T'''):
s.top = s.top + 1
s[s.top].value = x
s[s.top].prev = i
* <tex>\mathrm{pop}(i)</tex> {{---}} возвращает значение, хранящееся в элементе с номером <tex>i </tex> и копирует элемент, предыдущий для него.,
результирующий стек будет иметь номер <tex> n + 1 </tex>.
'''T''' pop(i : '''uint'''):
