1632
правки
Изменения
Дек
,rollbackEdits.php mass rollback
'''if''' (size() < n / 4)
'''T''' newDeque[n / 2]
'''int''' deque_size dequeSize = size() '''for''' i = 0 '''to''' size dequeSize - 1
newDeque[i] = d[head]
head = (head + 1) % n
'''if''' (size() < n / 4)
'''T''' newDeque[n / 2]
'''int''' deque_size dequeSize = size() '''for''' i = 0 '''to''' size dequeSize - 1
newDeque[i] = d[head]
head = (head + 1) % n
leftStack.push(local.pop())
'''return''' rightStack.pop()
{{Лемма
|statement=Амортизированная стоимость операции в таком деке {{---}} <tex>O(1)</tex>.
|proof=Воспользуемся методом предоплаты для доказательства. Достаточно доказать, что между двумя балансировками происходит достаточно амортизирующих их операций.
Вначале в обоих стеках пусто, поэтому они сбалансированы. Рассмотрим дек после очередной балансировки, будем использовать две монеты для операций <tex>\mathtt{push}</tex> и <tex>\mathtt{pop}</tex> {{---}} одну для самой операции, а другую {{---}} в качестве резерва.
Разберем худший случай: после очередной балансировки происходит удаление всех элементов только из одного стека. В таком случае при удалении кладем одну резервную монету на элемент из другого стека. Тогда учетная стоимость следующей балансировки равна нулю, поскольку на всех элементах дека лежит по монете.
}}
== См. также ==
