3622
правки
Изменения
→Стек с multipop
При выполнении операции <tex>\mathrm{push}{}</tex> будем использовать две монеты {{---}} одну для самой операции, а вторую {{---}} в качестве резерва. Тогда для операций <tex>\mathrm{pop}{}</tex> и <tex>\mathrm{multipop}{}</tex> учётную стоимость можно принять равной нулю и использовать для удаления элемента монету, оставшуюся после операции <tex>\mathrm{push}{}</tex>.
Таким образом, для каждой операции требуется <tex>O(1)</tex> монет, а значит, средняя амортизационная стоимость операций <tex>a = O(1)</tex>.
=====Очередь на двух стеках=====
