234
правки
Изменения
Нет описания правки
== Эффективная реализация ==
Попробуем решить задачу эффективнее. Заведем массив указателей, ссылающихся на каждую версию стека. Вместо n копий стека будем хранить n первых элементов. Тогда операции push и pop будут иметь следующий вид:<br>
* <tex>push(x, i)</tex> - создает новый элемент со значением x, который ссылается на элемент с номером i как на предыдущий элемент в стеке.
* <tex>pop(i)</tex> - возвращает значение, хранящееся в элементе с номером i и копирует элемент, предыдущий для него.
Результирующие стеки будут иметь номер n + 1.
== Пример ==
<br>
В итоге мы имеем доступ ко всем версиям стека за <tex>O(1)</tex> времени и <tex>O(n)</tex> памяти(массив длины n и n самих "стеков").
== См. также==
