1632
правки
Изменения
Дек
,rollbackEdits.php mass rollback
Вначале в обоих стеках пусто, поэтому они сбалансированы. Рассмотрим дек после очередной балансировки, будем использовать две монеты для операций <tex>\mathtt{push}</tex> и <tex>\mathtt{pop}</tex> {{---}} одну для самой операции, а другую {{---}} в качестве резерва.
Разберем худший случай: после очередной балансировки происходит удаление всех элементов только из одного стека. В таком случае при удалении кладем одну резервную монету на элемент из другого стека. Тогда учетная стоимость следующей балансировки равна нулю, поскольку на всех элементах дека лежит по монете. Ч. т. д.
}}
