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