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

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

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

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

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

Самое простое и очевидное решение этой задачи — симуляция описанного процесса, т.е. честное копирование стека при каждой операции.
Очевидно, что это не самое эффективное решение. Сложность одной операции составляет [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 и копирует элемент, предыдущий для него.

Результирующие стеки будут иметь номер n + 1.

Пример

Пусть изначально у нас есть один пустой стек. Для удобства, будем хранить его как «голову» с пометкой пустого стека:



Далее выполним [math]push(1, 5)[/math]. Создается новая вершина со значением 5, ссылающаяся на 1-ую:


Аналогично выполним [math]push(2, 10)[/math] и [math]push(1, 6)[/math]:

Очевидно, что все 4 стека сейчас верно построены и легко восстанавливаются. Давайте теперь попробуем выполнить последовательно операции [math]pop(2)[/math] и [math]pop(3)[/math]:

• [math]pop(2)[/math] возвращает 5 и копирует 1-ую вершину. Результирующий пятый стек — пустой.

• [math]pop(3)[/math] возвращает 10 и копирует 2-ую вершину: получаем шестой стек.

В итоге мы имеем доступ ко всем версиям стека за [math]O(1)[/math] времени и [math]O(n)[/math] памяти.

См. также

• Стек

Ссылки

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