21
правка
Изменения
→Очередь на двух стеках
Рассмотрим реализацию очереди на двух стеках. Пусть наши стеки имеют операции <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>.
