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