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

Материал из Викиконспекты
Перейти к: навигация, поиск

!!не дописано!!

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


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


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

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

Пример:

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


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


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

nothumb





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


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





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

nothumb




См. также

Ссылки