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

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

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

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

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

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

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

Итак

См. также

• Стек

Ссылки

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