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