39
правок
Изменения
Дек
,Нет описания правки
== Реализации ==
Дек расходует только <tex>O(n)</tex> памяти, на хранение самих элементов.
Изначально переменные <tex> \mathtt{head} </tex> и <tex> \mathtt{tail} </tex> должны различаться на единицу, причем <tex> \mathtt{head = tail - 1} </tex>.
=== Простая реализация ===
Ключевые поля:
* <tex>\mathtt{d[0\dots 2 * n - 1]}</tex> {{---}} массив, с помощью которого реализуется дек, способный вместить не более <tex>n</tex> элементов,
* <tex>\mathtt{d.head}</tex> {{---}} индекс головы дека,
* <tex>\mathtt{d.tail}</tex> {{---}} индекс хвоста.
Дек состоит из элементов <tex>\mathtt {d[d.head\dots d.tail]}</tex>. Если происходит максимум n добавлений, то массив длины 2*n может вместить в себя все добавленные элементы. При этом <tex> \mathtt{d.head = n} </tex> и <tex> \mathtt{d.tail = n + 1} </tex>.
'''boolean''' empty():
'''return''' (d.head + 1) % n == 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"
d.tail = d.tail - 1
'''return''' d[d.tail]
'''function''' pushFront(x : '''T'''):
d[d.head] = x
d.head = d.head - 1
'''T''' popFront():
'''if''' (empty())
'''return''' <span style="color:red">error</span> "underflow"
d.head = d.head + 1
'''return''' d[d.head]
=== Циклический дек на массиве константной длины ===
Ключевые поля:
Дек состоит из элементов <tex>\mathtt {d[d.head\dots d.tail]}</tex> или <tex>\mathtt {d[0\dots d.tail]}</tex> и <tex>\mathtt {d[d.head\dots n-1]}</tex>. Всего он способен вместить не более <tex>n</tex> элементов. В данной реализации учитывается переполнение и правильно обрабатывается изъятие из пустого дека. Недостатком является константная длина массива, хранящего элементы. Все операции выполняются за <tex>O(1)</tex>.
'''function''' pushBack(x : '''T'''):
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]
