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

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

Персистентными структурами данных называются такие структуры, хранящие все свои промежуточные версии.

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

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

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

Эффективная реализация

Попробуем решить задачу эффективнее. Заведем массив запросов, модифицирующих стек.

У каждого элемента массива будет 2 поля: значение в вершине стека и индекс предыдущей версии стека.

Тогда операции push и pop будут иметь следующий вид:

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

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

Пример

Пусть изначально у нас есть один пустой стек. Запишем его в массив.

index	1
value	[math]null[/math]
prev	[math]null[/math]

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

index	1	2
value	[math]null[/math]	3
prev	[math]null[/math]	1

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

index	1	2	3
value	[math]null[/math]	3	5
prev	[math]null[/math]	1	2

• Выполним [math]pop(3)[/math]. он возвращает 5 и копирует 2ю вершину.

index	1	2	3	4
value	[math]null[/math]	3	5	3
prev	[math]null[/math]	1	2	1

Так будет выглядеть массив после последовательности операций [math]push(3, 6), push(5, 1), pop(4), pop(5), push(7, 9):[/math]

index	1	2	3	4	5	6	7	8	9
value	[math]null[/math]	3	5	3	6	1	[math]null[/math]	5	9
prev	[math]null[/math]	1	2	1	3	5	[math]null[/math]	2	7

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

См. также

• Стек
• Персистентный дек

Ссылки

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