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

TL;DR

Персистентный стек (persistent stack) — стек, хранящий все свои предыдущие версии: каждая операция не изменяет структуру, а создаёт новую версию, оставляя старые доступными. Реализуется как односвязный список: узел хранит значение и ссылку prev на предыдущую версию, а «текущая версия» — это просто ссылка на верхний узел. push создаёт один новый узел за [math]\displaystyle{ O(1) }[/math], pop возвращает значение и ссылку на предыдущую версию — тоже [math]\displaystyle{ O(1) }[/math] и без новых ячеек. [math]\displaystyle{ n }[/math] операций push создают ровно [math]\displaystyle{ n }[/math] новых узлов, а вместе с корнем в структуре [math]\displaystyle{ n + 1 }[/math] узел, потому что все версии разделяют общий хвост (sharing): память [math]\displaystyle{ O(n) }[/math], а не [math]\displaystyle{ O(n^2) }[/math]. Все узлы неизменяемы, поэтому персистентный стек — это функциональная персистентность; он служит строительным блоком для персистентной очереди (Очередь на шести стеках), версионирования и неизменяемых списков.

Свойство	Значение
Класс	Стек (LIFO) с полной персистентностью; функциональная структура данных
Версии	Хранятся все; доступ к версии по ссылке за [math]\displaystyle{ O(1) }[/math], материализация — [math]\displaystyle{ O(k) }[/math]
push	[math]\displaystyle{ O(1) }[/math] времени, [math]\displaystyle{ O(1) }[/math] новых ячеек
pop	[math]\displaystyle{ O(1) }[/math] времени, 0 новых ячеек (список) / 1 ячейка (массив)
Память	[math]\displaystyle{ O(V) }[/math] под [math]\displaystyle{ V }[/math] узлов; [math]\displaystyle{ n }[/math] операций push → [math]\displaystyle{ n }[/math] новых узлов (вместе с корнем [math]\displaystyle{ n + 1 }[/math])
Изменяемость	нет; узлы инициализируются один раз и не меняются
Представления	односвязный список ({value, prev}) или массив запросов
Разделение	версии делят общие хвосты; ветвление даёт дерево версий
Персистентность	функциональная (сильнейшая форма)
Где встречается	функциональные языки (списки), персистентная очередь, undo/redo, версионирование

Определения

Персистентная структура данных — структура, сохраняющая доступ ко всем предшествующим версиям при выполнении операций. Различают три уровня:

• частичная персистентность (partial): можно изменять только самую новую версию, но читать — любую;
• полная персистентность (full): изменять и читать можно любую версию;
• функциональная персистентность (functional): каждая ячейка памяти инициализируется один раз и больше не изменяется, поэтому версии разделяют неизменяемые данные.

Версия стека — конкретное состояние стека (упорядоченная последовательность элементов). В персистентном стеке версия отождествляется с узлом-вершиной.

Узел (node) — запись {value, prev}, где value — значение на вершине, а prev — ссылка на предыдущую версию (узел ниже) или null для пустой версии. Узел неизменяем.

Текущая вершина (top) — ссылка на узел, представляющий актуальную версию. Изменение стека не переписывает узлы, а лишь заменяет top.

Разделение хвоста (sharing) — ситуация, когда несколько версий ссылаются на один и тот же узел (и, следовательно, на общий остаток стека). Безопасно только при неизменяемости узлов.

Две реализации. Списковая: узлы связаны ссылками. Массивная (массив запросов): push добавляет ячейку {x, i}, а pop — копию версии s[i].prev (той, что лежит под вершиной); номер новой версии равен [math]\displaystyle{ n + 1 }[/math].

Обозначения. [math]\displaystyle{ n }[/math] — число элементов/операций; [math]\displaystyle{ V }[/math] — число версий; s[i] — ячейка массива запросов с номером [math]\displaystyle{ i }[/math]; [math]\displaystyle{ \log }[/math] — двоичный.

Мотивация и интуиция

Обычный стек из Стек хранит одно состояние: push записывает элемент в ячейку, pop её очищает. Прошлые состояния теряются. Если нужно вернуться к предыдущему состоянию — приходится заранее копировать стек целиком, а это [math]\displaystyle{ \Theta(n) }[/math] времени и памяти на каждую версию и [math]\displaystyle{ \Theta(n^2) }[/math] суммарно. См. рис. 1.

Рис. 1. Мутирующий стек хранит единственное состояние: push(d) теряет прежнюю версию; персистентный добавляет новый узел, сохраняя старые версии.

Списковая структура стека подсказывает решение. Стек — это цепочка «верх → … → дно». Добавление элемента можно представить не как запись в общую память, а как новую голову цепочки: новый узел хранит добавленное значение и ссылку на прежнюю голову. Тогда старая цепочка никуда не девается — на неё просто никто не указывает как на текущую. Аналогично pop не удаляет узел, а возвращает ссылку на следующий узел цепочки. Такой стек никогда ничего не перезаписывает.

Ключевая идея в одном абзаце: вершина — это всего лишь указатель на узел, а узел неизменяем; поэтому «изменение» сводится к замене указателя, а вся история сохраняется как цепочка (точнее — дерево) узлов, делящих общие хвосты. Отсюда [math]\displaystyle{ O(1) }[/math] на операцию и [math]\displaystyle{ O(n) }[/math] суммарной памяти.

Устройство

Персистентный стек состоит из узлов {value, prev} и ссылки top на текущую вершину (см. рис. 2). Пустая версия — это специальный корневой узел без значения; в массиве его роль играет sentinel null.

Рис. 2. Версия = узел; push добавляет узел перед текущим, pop возвращает предыдущий узел.

Версии образуют связную структуру: цепочка prev-ссылок из любого узла ведёт вниз, к корню. Несколько версий могут указывать на один узел — это разделение хвостов. Ветвление (например, два push от одной и той же версии) превращает линию версий в дерево версий; именно так устроены история в редакторах и снапшоты в базах данных.

Есть два эквивалентных представления (см. рис. 3):

• Список. Узел хранит value и prev; ссылка на узел — это версия. push создаёт узел за [math]\displaystyle{ O(1) }[/math]; pop возвращает пару (value, prev) и не создаёт узлов.
• Массив запросов. Ячейка s[i] хранит {value, prev} — значение вершины версии [math]\displaystyle{ i }[/math] и индекс её предыдущей версии. push(i, x) добавляет ячейку {x, i} и возвращает её индекс [math]\displaystyle{ n + 1 }[/math]; pop(i) возвращает значение s[i].value и создаёт новую версию — копию версии s[i].prev, лежащей под вершиной.

Рис. 3. Массив запросов: каждая ячейка = {value, prev}; операция добавляет ровно одну ячейку.

Массивное представление удобно, когда версии нумеруются подряд и нужен быстрый доступ по индексу; списковое — когда версии передаются как ссылки, а структура используется как неизменяемое значение (например, список в функциональном языке).

Операции и алгоритмы

Операция: Push

Идея. Создать новый узел со значением [math]\displaystyle{ x }[/math] и ссылкой на текущую вершину; объявить его новой вершиной. Прежняя версия сохраняется без изменений.

Пошаговое описание (список):

1. Создать узел [math]\displaystyle{ k }[/math] со значением [math]\displaystyle{ x }[/math] и ссылкой prev ← top.
2. Присвоить top ← k.
3. Вернуть новую вершину (новую версию).

Инвариант. Цепочка prev-ссылок из top перечисляет элементы стека сверху вниз; все ранее созданные узлы сохраняют свои поля.

Операция Push(s, x)
Вход:  персистентный стек s (ссылка top на вершину); x — элемент
Выход: новая версия стека (ссылка на новый узел)
Инвариант: элементы версии = цепочка top → prev → … → корень
Сложность: O(1) времени, O(1) новых ячеек

1  k ← новый узел
2  k.value ← x
3  k.prev ← s.top
4  s.top ← k
5  return k

Массивная версия:

Операция Push-Array(s, i, x)
Вход:  массив s запросов; i — номер версии, от которой добавляем; x — элемент
Выход: номер новой версии
Сложность: O(1)

1  s.top ← s.top + 1
2  s[s.top].value ← x
3  s[s.top].prev ← i
4  return s.top

Разбор. Стек, представленный версией 2 (value = 3, prev = 1), при push(2, 5) получает ячейку 3 (value = 5, prev = 2). Версия 2 не изменилась: s[2] по-прежнему {3, 1}.

Сложность. [math]\displaystyle{ O(1) }[/math] и на списке, и на массиве: одна запись, одна ссылка.

Крайние случаи. push в пустую версию даёт узел со ссылкой на корень. Если требуется добавить элемент в прошлую версию, создаётся ветвь — текущая линия не затрагивается.

См. рис. 1 и рис. 2.

Операция: Pop

Идея. Вернуть значение текущей вершины и «перейти» на предыдущую версию. В списковой реализации это просто возврат ссылки prev; в массивной — запись новой ячейки, повторяющей предыдущую версию (см. рис. 4).

Пошаговое описание (список):

1. Если стек пуст — ошибка underflow.
2. Запомнить значение x ← top.value.
3. Перейти к предыдущей версии: top ← top.prev.
4. Вернуть пару (x, top) — значение и новую версию.

Инвариант. Новая версия содержит все элементы исходной, кроме верхнего; исходная версия остаётся доступной по прежней ссылке.

Операция Pop(s)
Вход:  персистентный стек s (top ≠ корень)
Выход: пара (x, s) — верхний элемент и новая версия s
Сложность: O(1) времени, 0 новых ячеек

1  if s.top = корень
2      error "попытка pop из пустого стека"
3  x ← s.top.value
4  s.top ← s.top.prev
5  return (x, s)

Массивная версия (копирует предыдущую ячейку):

Операция Pop-Array(s, i)
Вход:  массив s; i — номер версии (i ≠ корень)
Выход: (значение, номер новой версии)
Сложность: O(1)

1  if s[i].prev = null
2      error "pop из пустого стека"
3  x ← s[i].value
4  k ← s[s[i].prev]                 # узел под вершиной
5  Push-Array(s, k.prev, k.value)   # новая ячейка = копия версии под i
6  return (x, s.top)

Здесь null — sentinel пустой версии (в C++-реализации ниже он кодируется индексом 0). Поэтому pop от версии из одного элемента создаёт новую пустую ячейку с prev = null (в трассировке — ячейка 7).

Разбор. Для s = [a, b, c] (вершина c) операция Pop вернёт c и версию [a, b]; версия [a, b, c] сохраняется. В массивной версии pop(3) для ячейки 3 вернул 5 и завёл ячейку 4, повторяющую версию 2.

Сложность. [math]\displaystyle{ O(1) }[/math]; в списке ноль новых ячеек, в массиве — ровно одна.

Крайние случаи. pop из пустой версии — ошибка. Если pop применяется к «прошлой» версии, новые ячейки пишутся в конец массива, а прежние ветви остаются нетронутыми.

Рис. 4. pop не удаляет данные: он лишь указывает на предыдущую версию.

Операция: Top и Empty

Идея. Вершина и признак пустоты — чтение за [math]\displaystyle{ O(1) }[/math].

Операция Top(s)
Вход:  персистентный стек s
Выход: значение верхнего элемента
Инвариант: s.top — вершина текущей версии
Сложность: O(1) времени, O(1) памяти

1  if s.top = корень
2      error "вершина пустого стека не определена"
3  return s.top.value

Операция Empty(s)
Вход:  персистентный стек s
Выход: true, если текущая версия пуста
Сложность: O(1) времени, O(1) памяти

1  return (s.top = корень)

Крайние случаи. Top пустой версии — ошибка; Empty для корня возвращает true.

Доступ к произвольной версии

Идея. Версия — это ссылка (или индекс), поэтому «переход» к ней бесплатен. Материализация (выписывание всех элементов версии) стоит [math]\displaystyle{ O(k) }[/math] для версии из [math]\displaystyle{ k }[/math] элементов.

Операция To-List(v)                 # материализация версии v
Вход:  вершина v (версия стека)
Выход: список значений сверху вниз
Инвариант: v — ещё не пройденная часть версии
Сложность: O(k) времени и O(k) памяти для k элементов

1  out ← пустой список
2  while v ≠ корень
3      out.append(v.value)
4      v ← v.prev
5  return out

Сложность. [math]\displaystyle{ O(k) }[/math] для [math]\displaystyle{ k }[/math] элементов; при этом версии не мешают друг другу.

Сводная таблица сложности

Операция	Время	Новых ячеек	Память
Push	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]	+1 узел
Pop	[math]\displaystyle{ O(1) }[/math]	0 (список) / 1 (массив)	0 (список) / 1 ячейка (массив)
Top	[math]\displaystyle{ O(1) }[/math]	0	0
Empty	[math]\displaystyle{ O(1) }[/math]	0	0
Доступ к версии	[math]\displaystyle{ O(1) }[/math]	0	0
Материализация версии из [math]\displaystyle{ k }[/math] элементов	[math]\displaystyle{ O(k) }[/math]	[math]\displaystyle{ O(k) }[/math]	[math]\displaystyle{ O(k) }[/math]
[math]\displaystyle{ n }[/math] операций push	[math]\displaystyle{ O(n) }[/math] суммарно	—	[math]\displaystyle{ O(n) }[/math] узлов

Оговорка: в списковой и массивной моделях амортизация не нужна — каждая операция уже [math]\displaystyle{ O(1) }[/math] в худшем случае. В C++-реализации ниже используется std::vector: его push_back даёт амортизированный [math]\displaystyle{ O(1) }[/math], поэтому для строгого худшего случая нужен заранее выделенный пул с резервом. Суммарная память пропорциональна числу созданных версий, а не их размерам, потому что версии делят общие хвосты.

Трассировка примера

Повторим последовательность из источника для массивной реализации: push(1, 3), push(2, 5), pop(3), push(3, 6), push(5, 1), pop(4), pop(5), push(7, 9).

index	value	prev	Операция
1	null	null	начальная пустая версия
2	3	1	push(1, 3)
3	5	2	push(2, 5)
4	3	1	pop(3): вернул 5, скопировал версию 2
5	6	3	push(3, 6)
6	1	5	push(5, 1)
7	null	null	pop(4): вернул 3, скопировал версию 1 (пустую)
8	5	2	pop(5): вернул 6, скопировал версию 3
9	9	7	push(7, 9)

Разберём строку 4: pop(3) читает ячейку 3 (value = 5, prev = 2), возвращает 5, а новой версией делает копию ячейки под ней — ячейка 4 повторяет версию 2 (value = 3, prev = 1). Строка 7: pop(4) возвращает 3, а новой версией становится пустая (ячейка 7 повторяет корень). Все прошлые ячейки (1–6) остаются доступными: в массиве запросов ничего не перезаписывается.

Корректность и оценка сложности

Инвариант

Инвариант. Для любого узла [math]\displaystyle{ v }[/math] цепочка [math]\displaystyle{ v, \mathrm{prev}(v), \mathrm{prev}^2(v), \dots }[/math] заканчивается корнем, и значения узлов вдоль цепочки образуют содержимое версии [math]\displaystyle{ v }[/math] сверху вниз.

База. Корень — пустая версия, цепочка длины 0.

Переход push. Новый узел [math]\displaystyle{ k }[/math] указывает на прежнюю вершину [math]\displaystyle{ v }[/math], поэтому цепочка из [math]\displaystyle{ k }[/math] есть [math]\displaystyle{ k }[/math] + цепочка из [math]\displaystyle{ v }[/math]; значения — [math]\displaystyle{ x }[/math] + содержимое [math]\displaystyle{ v }[/math], что и требуется. Ни один старый узел не изменён.

Переход pop. Новая вершина — [math]\displaystyle{ \mathrm{prev}(v) }[/math]; её цепочка есть содержимое версии без верхнего элемента. Исходная ссылка [math]\displaystyle{ v }[/math] сохраняет старый стек.

Отсюда Top возвращает верхний элемент, Empty корректно распознаёт корень, а любая версия читается за [math]\displaystyle{ O(1) }[/math] по ссылке (переход к прошлому состоянию — операция над указателем).

Оценка памяти: разделение хвостов

Каждый push создаёт ровно один новый узел; pop в списковой реализации не создаёт узлов вовсе. Значит, после [math]\displaystyle{ n }[/math] операций push в структуре [math]\displaystyle{ n + 1 }[/math] узел (включая корень), то есть [math]\displaystyle{ O(n) }[/math] памяти — независимо от того, сколько версий сохранено и каковы их размеры (см. рис. 5). Если бы каждая версия хранилась отдельным массивом, суммарная память была бы [math]\displaystyle{ 1 + 2 + \dots + n = \Theta(n^2) }[/math].

Рис. 5. Ветви делят общий хвост: [math]\displaystyle{ n }[/math] операций push дают [math]\displaystyle{ n + 1 }[/math] узел, а не [math]\displaystyle{ \Theta(n^2) }[/math] памяти.

Время

Push, Pop, Top, Empty выполняют постоянное число операций над указателями и записями — [math]\displaystyle{ O(1) }[/math] в худшем случае. Материализация версии из [math]\displaystyle{ k }[/math] элементов требует прохода по [math]\displaystyle{ k }[/math] узлам — [math]\displaystyle{ O(k) }[/math]; это неизбежно, поскольку выписываются [math]\displaystyle{ k }[/math] значений.

Сравнение с альтернативами

Структура	push	pop	Доступ к версиям	Память под [math]\displaystyle{ n }[/math] версий
Обычный стек (Стек)	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]	нет (одно состояние)	[math]\displaystyle{ O(n) }[/math]
Обычный стек + полное копирование	[math]\displaystyle{ O(1) }[/math] + [math]\displaystyle{ \Theta(n) }[/math] копия	[math]\displaystyle{ O(1) }[/math]	да	[math]\displaystyle{ \Theta(n^2) }[/math]
Персистентный стек (список)	[math]\displaystyle{ O(1) }[/math], 1 узел	[math]\displaystyle{ O(1) }[/math], 0 узлов	да, [math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(n) }[/math]
Персистентный стек (массив запросов)	[math]\displaystyle{ O(1) }[/math], 1 ячейка	[math]\displaystyle{ O(1) }[/math], 1 ячейка	да, [math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(n) }[/math]
Персистентная очередь (Очередь на шести стеках)	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]	да, [math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(n) }[/math] суммарно ([math]\displaystyle{ O(1) }[/math] новых на операцию)

Вердикт. Нужны прошлые состояния стека — только персистентная реализация; копирование неприемлемо из-за [math]\displaystyle{ \Theta(n^2) }[/math]. Между списком и массивом выбор по стилю: список удобнее для функционального кода и передачи версий как значений, массив — для нумерованных версий и индексного доступа. Персистентная очередь — следующий шаг: стек — её элементарный кирпич.

Где применяется

1. Функциональные языки и неизменяемые списки. Односвязный список в LISP, Haskell, OCaml, Standard ML — это персистентный стек: добавление в голову за [math]\displaystyle{ O(1) }[/math], хвосты разделяются. Почему: скрытая мутация в чистом функциональном языке невозможна, а неизменяемый список её и не требует [2][3].

1. Персистентная очередь и другие персистентные структуры. Делая стек персистентным, мы получаем строительный блок для очереди (Очередь на шести стеках), дека и приоритетной очереди. Почему: многие структуры сводятся к комбинации стеков/списков [1][2].

1. Undo/redo и версионирование. Редакторы, СУБД с MVCC, системы контроля версий и транзакционные снапшоты хранят историю как версии структуры; откат — переход по ссылке без копирования данных [3][4].

1. Обход и разбор с ветвлением. В backtracking, разборе выражений и DFS путь можно хранить как персистентный стек: каждое ветвление — новая версия, а возврат в точку выбора — переход по сохранённой ссылке. Почему: состояние стека восстанавливается за [math]\displaystyle{ O(1) }[/math] [2].

1. Параллельные и распределённые вычисления. Неизменяемые данные естественно разделяются между потоками и репликами без блокировок: структура, разделяемая несколькими потребителями, не может быть испорчена мутацией [3][4].

Обзор основных областей — на рис. 6.

Рис. 6. Персистентная очередь, версионирование и undo, функциональные списки, история обхода и разбора, параллельные вычисления — пять областей, где персистентный стек служит фундаментом.

Историческая справка

Идея функциональных списков-стеков восходит к языку LISP (Джон Маккарти, 1958–1960): операции cons, car, cdr строят разделяемые неизменяемые цепочки — фактически персистентный стек [2]. Термин «персистентные структуры данных» и систематическое изучение методов (путь-копирование, fat nodes, node-copying) ввели Дрисколл, Сарнак, Слитор и Тарьян в работе Making Data Structures Persistent (STOC 1986; журнальная версия — JCSS, 1989) [4]. Формальный амортизированный анализ, которым описывают стоимость операций, развил Роберт Тарьян («Amortized Computational Complexity», 1985) [5].

Учебное изложение персистентного стека (список и массив запросов) — конспект кафедры компьютерных технологий ИТМО на «Викиконспектах» [1]; оттуда же распространён разбор персистентной очереди. Понятие «функциональная персистентность» и коллекция персистентных структур систематизированы Крисом Окасаки в книге Purely Functional Data Structures (Cambridge University Press, 1998) [3].

Типичные ошибки и подводные камни

• Путать персистентность со снапшотом-копией. Персистентный стек не копирует содержимое при каждой версии: узлы общие, копируется только «верх» (один узел).
• Мутировать узел. Изменение value/prev существующего узла немедленно испортит все версии, которые через него проходят. Узлы обязаны быть неизменяемыми.
• Освобождать память «оптимизацией». Удаление узлов из-под старых версий ломает персистентность; сборка мусора нужна, но только когда на узел не ссылается ни одна версия.
• Считать память пропорциональной числу версий, умноженному на их размер. Правильная оценка — [math]\displaystyle{ O(\text{число операций}) }[/math] благодаря разделению хвостов.
• Ожидать [math]\displaystyle{ O(1) }[/math] от pop в массивной реализации без учёта новой ячейки. В массиве pop добавляет запись; это всё ещё [math]\displaystyle{ O(1) }[/math], но память растёт на каждую модификацию.
• Переполнение/уход индексов в массиве запросов. Версии нумеруются монотонно; смешение «номера версии» и «индекса ячейки» при ветвлении приводит к ошибкам.
• Смешивать current и версию. Возвращая из операции узел, а не пару «результат + новая версия», легко потерять возможность продолжать от прежней версии.
• Забыть про корень. Пустая версия должна быть корректным состоянием: без корня pop до конца и Empty работают неверно.
• Ожидать, что To-List бесплатен. Материализация версии — [math]\displaystyle{ O(k) }[/math]; путать её с [math]\displaystyle{ O(1) }[/math] доступом к самой версии нельзя.
• Полагать, что персистентность автоматически даёт быстрый произвольный pop. Для очереди на двух стеках этого мало — требуется дробление переноса (см. Очередь на шести стеках).

Задачи для практики

1. Базовые операции. Реализуйте персистентный стек на списке (value, prev) с push, pop, top, empty. Ограничение: узлы неизменяемы. Подсказка: pop возвращает пару «значение + новая версия».

1. Ветвление. В списковой реализации от версии [a, b, c] примените pop, затем push(d), затем ещё раз pop. Сколько версий существует и какие у них содержимые? Подсказка: постройте дерево версий.

1. Память. Для списковой реализации докажите, что [math]\displaystyle{ n }[/math] операций push и любые pop порождают не более [math]\displaystyle{ n + 1 }[/math] узлов. Подсказка: каждый push добавляет ровно один узел, pop — ноль.

1. Массив запросов. Реализуйте массивную версию и воспроизведите трассировку из раздела «Трассировка примера». Сверьте значения value и prev.

1. Материализация. Напишите To-List(v) и оцените время; добейтесь [math]\displaystyle{ O(k) }[/math] для версии из [math]\displaystyle{ k }[/math] элементов. Подсказка: идти по prev от вершины к корню.

1. Общий хвост. Для двух версий найдите длину общего хвоста, используя только поля {value, prev}; добейтесь времени [math]\displaystyle{ O(\ell_1 + \ell_2) }[/math], где [math]\displaystyle{ \ell_i }[/math] — длины версий. Дополнительно: добавьте depth и двоичные подъёмы (binary lifting); оцените preprocessing и время запроса LCA. Подсказка: без глубины сначала найдите глубины, затем выровняйте вершины и идите вверх вместе.

1. Персистентная очередь. Используя персистентный стек, постройте персистентную очередь и оцените худшее время push/pop. Подсказка: два стека; обсудите, почему нужен [math]\displaystyle{ O(1) }[/math] в худшем случае.

1. Сравнение. Сравните сумму памяти для [math]\displaystyle{ n }[/math] версий при (а) полном копировании, (б) списковой персистентности, (в) массивной. Приведите асимптотики и пример численно при [math]\displaystyle{ n = 1000 }[/math].

Связанные темы

• Стек — базовый LIFO-стек; мутирующая реализация.
• Персистентная очередь — персистентность очереди целиком.
• Очередь на шести стеках — очередь реального времени на шести стеках.
• Асимптотическая сложность — оценки [math]\displaystyle{ O }[/math], амортизация, худший случай.
• Персистентные структуры данных — общая теория: путь-копирование, fat nodes.
• Декартово дерево — персистентный treap; ещё один пример персистентности.
• Двоичное дерево поиска — персистентные структуры на деревьях.

Источники

1. Викиконспекты ИТМО: Персистентный стек (реализации на массиве и на списке, пример). URL: https://neerc.ifmo.ru/wiki/index.php?title=Персистентный_стек.
2. McCarthy J. Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I // Communications of the ACM. — 1960. — Vol. 3, № 4 (основы LISP и списков).
3. Okasaki C. Purely Functional Data Structures. — Cambridge University Press, 1998.
4. Driscoll J. R., Sarnak N., Sleator D. D., Tarjan R. E. Making Data Structures Persistent // STOC 1986; журнальная версия: Journal of Computer and System Sciences. — 1989. — Vol. 38.
5. Tarjan R. E. Amortized Computational Complexity // SIAM J. Algebraic and Discrete Methods. — 1985. — Vol. 6, № 2.
6. Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms (CLRS). 3rd ed. — MIT Press, 2009. — Гл. 10 (элементарные структуры: стек, список).
7. Хабрахабр. Персистентные структуры, часть 1: персистентный стек (пост 113585). URL: https://habr.com/ru/post/113585/.