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