Изменения

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

 Попробуем решить задачу эффективнее. Заведем массив запросов, модифицирующих стек. <br>У каждого элемента массива будет 2 поля: значение в вершине стека и индекс предыдущей версии стека.<br>

* <tex>push(i, x)</tex> — добавляет элемент х к стеку в стек с номером i, результирующий стек будет иметь номер <tex> n + 1</tex>.

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

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

|!1

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

|!1|!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;

<br>* Аналогично выполним <tex>push(2, 5)</tex>:<br>

|!1|!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;|!&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;

<br>* Выполним <tex>pop(3)</tex>. он возвращает 5 и копирует 2ю 2-ую вершину.<br>

|!1|!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;|!&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;|!&nbsp;&nbsp;&nbsp;&nbsp;4&nbsp;&nbsp;&nbsp;&nbsp;

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

|!1|!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;|!&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;|!&nbsp;&nbsp;&nbsp;&nbsp;4&nbsp;&nbsp;&nbsp;&nbsp;|!&nbsp;&nbsp;&nbsp;&nbsp;5&nbsp;&nbsp;&nbsp;&nbsp;|!&nbsp;&nbsp;&nbsp;&nbsp;6&nbsp;&nbsp;&nbsp;&nbsp;|!&nbsp;&nbsp;&nbsp;&nbsp;7&nbsp;&nbsp;&nbsp;&nbsp;|!&nbsp;&nbsp;&nbsp;&nbsp;8&nbsp;&nbsp;&nbsp;&nbsp;|!&nbsp;&nbsp;&nbsp;&nbsp;9&nbsp;&nbsp;&nbsp;&nbsp;

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