21
правка
Изменения
→Очередь на двух стеках
В лучшем случае (последовательность операций {{---}} добавить элемент и сразу же удалить его из очереди) мы тратим по монете непосредственно на <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>.
