Изменения

# Переместить содержимое <tex>L</tex> в <tex>R</tex>, <tex>n+1</tex>времени, <tex>n+1</tex>памяти.# Переместить первые <tex>toCopy</tex> элементов из стека <tex>T</tex> в стек <tex>R</tex>, остальные выкинуть, <tex>n</tex> времени, <tex>n</tex> памяти. # Поменять ролями стеки <tex>L, L'</tex>, <tex>1</tex> времени. Таким образом, мы получили <tex>3 \cdot n + 2</tex> времени и <tex>3 \cdot n + 1</tex> памяти на <tex>n + 1</tex> операцию, то есть <tex>3=O(1)</tex> времени и памяти на операцию. Совершая три дополнительных действия вместе с каждой операцией <tex>push, pop</tex> в режиме перекопирования мы гарантируем, что перекопирование завершится до опустошения стека <tex>R'</tex>. Теперь проверим корректность условия активации. Пусть среди <tex>n</tex> следующих за активацией операций <tex>push, pop</tex> присуствует <tex>x</tex> операций <tex>pop</tex> и <tex>n - x</tex> операций <tex>push</tex>.Тогда, очевидно, в стеке <tex>R</tex> окажется <tex>2 \cdot n + 1 - x</tex> элементов, а в стеке <tex>L</tex> станет <tex>n - x</tex> элементов, то есть на <tex>n + 1</tex> элемент меньше, чем в стеке <tex>R</tex>, а значит до следующего перекопирования <tex>n+2</tex> операции.