1632
правки
Изменения
Дек
,rollbackEdits.php mass rollback
Дек расходует только <tex>O(n)</tex> памяти, на хранение самих элементов.
=== Простая реализация ===
В данной реализации изначально <tex> \mathtt{d.head = n- 1} </tex> и <tex> \mathtt{d.tail = n- 1} </tex>.
Ключевые поля:
* <tex>\mathtt{d[0\dots 2 \times n - 1]}</tex> {{---}} массив, с помощью которого реализуется дек, способный вместить не более <tex>n</tex> элементов,
'''function''' pushBack(x : '''T'''):
d[tail++] = x tail++
'''T''' popBack():
'''if''' (empty())
'''return''' <span style="color:red">error</span> "underflow"
'''function''' pushFront(x : '''T'''):
'''T''' popFront():
'''if''' (empty())
'''return''' <span style="color:red">error</span> "underflow"
'''Treturn''' ret = d[head] head++ '''return''' ret]
=== Циклический дек на массиве константной длины ===
'''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
d = newDeque
head = 0
tail = deque_sizedequeSize
n /= 2
tail = (tail - 1 + n) % 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
d = newDeque
head = 0
tail = deque_sizedequeSize
n /= 2
'''T''' ret = d[head]
leftStack.push(local.pop())
'''return''' rightStack.pop()
{{Лемма
|statement=Амортизированная стоимость операции в таком деке {{---}} <tex>O(1)</tex>.
|proof=Воспользуемся методом предоплаты для доказательства. Достаточно доказать, что между двумя балансировками происходит достаточно амортизирующих их операций.
Вначале в обоих стеках пусто, поэтому они сбалансированы. Рассмотрим дек после очередной балансировки, будем использовать две монеты для операций <tex>\mathtt{push}</tex> и <tex>\mathtt{pop}</tex> {{---}} одну для самой операции, а другую {{---}} в качестве резерва.
Разберем худший случай: после очередной балансировки происходит удаление всех элементов только из одного стека. В таком случае при удалении кладем одну резервную монету на элемент из другого стека. Тогда учетная стоимость следующей балансировки равна нулю, поскольку на всех элементах дека лежит по монете.
}}
== См. также ==
