Персистентный стек
!!не дописано!!
| Определение: |
| Персистентными структурами данных мы будем называть такие структуры, что при всяком их изменении остается доступ ко всем предыдущим версиям этой структуры. |
Рассмотрим такую структуру на примере стека.
Наивная реализация
Самое простое и очевидное решение этой задачи — симуляция описанного процесса, т.е. честное копирование стека при каждой операции.
Очевидно, что это не самое эффективное решение. Сложность одной операции составляет и количество требуемой памяти — .
Нормальная реализация
Попробуем решить задачу эффективнее. Вместо n копий стека будем хранить n первых элементов. Тогда операции push и pop будут иметь следующий вид:
- - создает новый элемент со значением x, который ссылается на элемент с номером i как на предыдущий элемент в стеке.
- - возвращает значение, хранящееся в элементе с номером i и копирует элемент, предыдущий для него.
Пример:
Пусть изначально у нас есть один пустой стек. Для удобства, будем хранить его как «голову» с пометкой пустого стека:
Далее выполним push(1, 5). Создается новая вершина со значением 5, ссылающаяся на 1-ую:
Аналогично выполним push(2, 10) и push(1, 6):
Очевидно, что все 4 стека сейчас верно построены и легко восстанавливаются. Давайте теперь попробуем выполнить последовательно операции pop(2) и pop(3):
pop(2) возвращает 5 и копирует 1-ую вершину. Результирующий пятый стек — пустой.
pop(3) возвращает 10 и копирует 2-ую вершину: получаем шестой стек.
