215
правок
Изменения
→pop
'''return''' popRight()
При выполнении операции <texmath>\mathrm {push} </texmath> будем использовать три монеты: одну для самой операции, вторую в качестве резерва на операцию <texmath>\mathrm {pop} </texmath> из первого стека, третью во второй стек на финальный <texmath>\mathrm {pop} </texmath>. Тогда для операций <texmath>\mathrm {pop} </texmath> учётную стоимость можно принять равной нулю и использовать для операции монеты, оставшиеся после операции <texmath>\mathrm {push} </texmath>.
Таким образом, для каждой операции требуется <tex>O(1)</tex> монет, а значит, амортизационная стоимость операций <tex>O(1)</tex>.
'''Минусы:'''
* Если <tex>leftStack</tex> не пуст, то операция <texmath>\mathrm {pop} </texmath> может выполняться <tex>O(n)</tex> времени, в отличии от других реализаций, где <texmath>\mathrm {pop} </texmath> всегда выполняется за <tex>O(1)</tex>
== Реализация на шести стеках ==
