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

Определение:

Персистентными структурами данных мы будем называть такие структуры, что при всяком их изменении остается доступ ко всем предыдущим версиям этой структуры.

Рассмотрим такую структуру на примере стека.

Наивная реализация

Самое простое и очевидное решение этой задачи — симуляция описанного процесса, т.е. честное копирование стека при каждой операции.
Очевидно, что это не самое эффективное решение. Сложность одной операции составляет [math]O(n)[/math] и количество требуемой памяти — [math]O(n * n)[/math].

Нормальная реализация

Попробуем решить задачу эффективнее. Вместо n копий стека будем хранить n первых элементов. Тогда операции push и pop будут иметь следующий вид:

• [math]push(x, i)[/math] - создает новый элемент со значением x, который ссылается на элемент с номером i как на предыдущий элемент в стеке.
• [math]pop(i)[/math] - возвращает значение, хранящееся в элементе с номером i и копирует элемент, предыдущий для него.

См. также

• Стек

Ссылки

• Персистентный стек - статья на хабре