Изменения

Перейти к: навигация, поиск

Персистентный стек

8 байт добавлено, 15:00, 9 мая 2015
Эффективная реализация
У каждого элемента массива будет 2 поля: значение в вершине стека и индекс предыдущей версии стека.<br>
Тогда операции push и pop будут иметь следующий вид:<br>
* <tex>push(i, x)</tex> {{---}} добавляет элемент х в стек с номером i, результирующий стек будет иметь номер <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>pop(i)</tex> {{---}} возвращает значение, хранящееся в элементе с номером i и копирует элемент, предыдущий для него.
результирующий стек будет иметь номер <tex> n + 1 </tex>.
T pop(i : uint):
Анонимный участник

Навигация