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> элементов,
* <tex>\mathtt{d.head}</tex> {{---}} индекс головы дека,* <tex>\mathtt{d.tail}</tex> {{---}} индекс хвоста.
Дек состоит из элементов <tex>\mathtt {d[d.head\dots d.tail - 1]}</tex>. Если происходит максимум <tex>\mathtt {n}</tex> добавлений, то массив длины <tex>\mathtt {2 \times n}</tex> может вместить в себя все добавленные элементы.
'''boolean''' empty():
'''return''' d.head == d.tail
'''function''' pushBack(x : '''T'''):
d[d.tail++] = x d.tail = d.tail + 1
'''T''' popBack():
'''if''' (empty())
'''return''' <span style="color:red">error</span> "underflow"
'''function''' pushFront(x : '''T'''):
d.head = d.head [-- 1 d[d.head] = x
'''T''' popFront():
'''if''' (empty())
'''return''' <span style="color:red">error</span> "underflow"
'''Treturn''' ret = d[d.head++] d.head = d.head + 1 '''return''' ret
=== Циклический дек на массиве константной длины ===
'''function''' pushBack(x : '''T'''):
'''if''' (d.head == (tail + 1) % n)
'''return''' <span style="color:red">error</span> "overflow"
d[tail] = x
'''for''' i = 0 '''to''' n - 2
newDeque[i] = d[head]
d = newDeque
head = 0
tail = n - 1
n *= n * 2
d[tail] = x
tail = (tail + 1) % n
'''if''' (size() < n / 4)
'''T''' newDeque[n / 2]
'''int''' size dequeSize = size() '''for''' i = 0 '''to''' size dequeSize - 1
newDeque[i] = d[head]
head = (head + 1) % n
d = newDeque
head = 0
tail = sizedequeSize n /= n / 2
tail = (tail - 1 + n) % n
'''return''' d[tail]
head = 0
tail = n - 1
n *= n * 2
head = (head - 1 + n) % n
d[head] = x
'''if''' (size() < n / 4)
'''T''' newDeque[n / 2]
'''int''' size dequeSize = size() '''for''' i = 0 '''to''' size dequeSize - 1 newDeque[i] = d[d.head]
head = (head + 1) % n
d = newDeque
head = 0
tail = sizedequeSize n /= n / 2
'''T''' ret = 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> {{---}} одну для самой операции, а другую {{---}} в качестве резерва.
Разберем худший случай: после очередной балансировки происходит удаление всех элементов только из одного стека. В таком случае при удалении кладем одну резервную монету на элемент из другого стека. Тогда учетная стоимость следующей балансировки равна нулю, поскольку на всех элементах дека лежит по монете.
}}
== См. также ==
