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