Дек

2016-01-11T00:10:20Z

178.71.133.19:

== Определение ==
[[Файл:deque1.png|thumb|right|200px|Дек]]
'''Дек''' (от англ. ''deque'' {{---}} double ended queue) {{---}} структура данных, представляющая из себя список элементов, в которой добавление новых элементов и удаление существующих производится с обоих концов. Эта структура поддерживает как FIFO, так и LIFO, поэтому на ней можно реализовать как [[Стек | стек]], так и [[Очередь | очередь]]. В первом случае нужно использовать только методы головы или хвоста, во втором {{---}} методы push и pop двух разных концов. Дек можно воспринимать как двустороннюю очередь. Он имеет следующие операции:
* <tex> \mathtt{empty} </tex> {{---}} проверка на наличие элементов,
* <tex> \mathtt{pushBack} </tex> (запись в конец) {{---}} операция вставки нового элемента в конец,
* <tex> \mathtt{popBack} </tex> (снятие с конца) {{---}} операция удаления конечного элемента,
* <tex> \mathtt{pushFront} </tex> (запись в начало) {{---}} операция вставки нового элемента в начало,
* <tex> \mathtt{popFront} </tex> (снятие с начала) {{---}} операция удаления начального элемента.

== Реализации ==
Дек расходует только <tex>O(n)</tex> памяти, на хранение самих элементов.
=== Простая реализация ===
В данной реализации изначально <tex> \mathtt{head = n - 1} </tex> и <tex> \mathtt{tail = n - 1} </tex>.
Ключевые поля:
* <tex>\mathtt{d[0\dots 2 \times n - 1]}</tex> {{---}} массив, с помощью которого реализуется дек, способный вместить не более <tex>n</tex> элементов,
* <tex>\mathtt{head}</tex> {{---}} индекс головы дека,
* <tex>\mathtt{tail}</tex> {{---}} индекс хвоста.

Дек состоит из элементов <tex>\mathtt {d[head\dots tail - 1]}</tex>. Если происходит максимум <tex>\mathtt {n}</tex> добавлений, то массив длины <tex>\mathtt {2 \times n}</tex> может вместить в себя все добавленные элементы.

'''boolean''' empty():
'''return''' head == tail

'''function''' pushBack(x : '''T'''):
d[tail++] = x

'''T''' popBack():
'''if''' (empty())
'''return''' error "underflow"
'''return''' d[--tail]

'''function''' pushFront(x : '''T'''):
d[--head] = x

'''T''' popFront():
'''if''' (empty())
'''return''' error "underflow"
'''return''' d[head++]

=== Циклический дек на массиве константной длины ===
Во всех циклических реализациях изначально присвоены следующие значения <tex> \mathtt{head = 0} </tex> и <tex> \mathtt{tail = 0} </tex>.
Ключевые поля:
* <tex>\mathtt{d[0\dots n-1]}</tex> {{---}} массив, с помощью которого реализуется дек, способный вместить не более <tex>n</tex> элементов,
* <tex>\mathtt{head}</tex> {{---}} индекс головы дека,
* <tex>\mathtt{tail}</tex> {{---}} индекс хвоста.

Дек состоит из элементов <tex>\mathtt {d[head\dots tail-1]}</tex> или <tex>\mathtt {d[0\dots tail-1]}</tex> и <tex>\mathtt {d[head\dots n-1]}</tex>. Всего он способен вместить не более <tex>n</tex> элементов. В данной реализации учитывается переполнение и правильно обрабатывается изъятие из пустого дека. Недостатком является константная длина массива, хранящего элементы. Все операции выполняются за <tex>O(1)</tex>.

'''function''' pushBack(x : '''T'''):
'''if''' (head == (tail + 1) % n)
'''return''' error "overflow"
d[tail] = x
tail = (tail + 1) % n

'''T''' popBack():
'''if''' (empty())
'''return''' error "underflow"
tail = (tail - 1 + n) % n
'''return''' d[tail]

'''function''' pushFront(x : '''T'''):
'''if''' (head == (tail + 1) % n)
'''return''' error "overflow"
head = (head - 1 + n) % n
d[head] = x

'''T''' popFront():
'''if''' (empty())
'''return''' error "underflow"
'''T''' ret = d[head]
head = (head + 1) % n
'''return''' ret

=== Циклический дек на динамическом массиве ===
Ключевые поля:
* <tex>\mathtt{n}</tex> {{---}} размер массива,
* <tex>\mathtt{d[0\dots n-1]}</tex> {{---}} массив, в котором хранится дек,
* <tex>\mathtt{newDeque[0\dots newSize]}</tex> {{---}} временный массив, где хранятся элементы после перекопирования,
* <tex>\mathtt{head}</tex> {{---}} индекс головы дека,
* <tex>\mathtt{tail}</tex> {{---}} индекс хвоста.

Дек состоит из элементов <tex>\mathtt {d[head\dots tail-1]}</tex> или <tex>\mathtt {d[0\dots tail-1]}</tex> и <tex>\mathtt {d[head\dots n-1]}</tex>. Если реализовывать дек на [[Динамический_массив | динамическом массиве]], то мы можем избежать ошибки переполнения. При выполнении операций <tex>\mathtt{pushBack}</tex> и <tex>\mathtt{pushFront}</tex> происходит проверка на переполнение и, если нужно, выделяется большее количество памяти под массив. Также происходит проверка на избыточность памяти, выделенной под дек при выполнении операций <tex>\mathtt{popBack}</tex> и <tex>\mathtt{popFront}</tex>. Если памяти под дек выделено в четыре раза больше размера дека, то массив сокращается в два раза. Для удобства выделим в отдельную функцию <tex>\mathtt{size}</tex> получение текущего размера дека.

'''int''' size()
'''if''' tail > head
'''return''' n - head + tail
'''else'''
'''return''' tail - head

'''function''' pushBack(x : '''T'''):
'''if''' (head == (tail + 1) % n)
'''T''' newDeque[n * 2]
'''for''' i = 0 '''to''' n - 2
newDeque[i] = d[head]
head = (head + 1) % n
d = newDeque
head = 0
tail = n - 1
n *= 2
d[tail] = x
tail = (tail + 1) % n

'''T''' popBack():
'''if''' (empty())
'''return''' error "underflow"
'''if''' (size() < n / 4)
'''T''' newDeque[n / 2]
'''int''' dequeSize = size()
'''for''' i = 0 '''to''' dequeSize - 1
newDeque[i] = d[head]
head = (head + 1) % n
d = newDeque
head = 0
tail = dequeSize
n /= 2
tail = (tail - 1 + n) % n
'''return''' d[tail]

'''function''' pushFront(x : '''T'''):
'''if''' (head == (tail + 1) % n)
'''T''' newDeque[n * 2]
'''for''' i = 0 '''to''' n - 2
newDeque[i] = d[head]
head = (head + 1) % n
d = newDeque
head = 0
tail = n - 1
n *= 2
head = (head - 1 + n) % n
d[head] = x

'''T''' popFront():
'''if''' (empty())
'''return''' error "underflow"
'''if''' (size() < n / 4)
'''T''' newDeque[n / 2]
'''int''' dequeSize = size()
'''for''' i = 0 '''to''' dequeSize - 1
newDeque[i] = d[head]
head = (head + 1) % n
d = newDeque
head = 0
tail = dequeSize
n /= 2
'''T''' ret = d[head]
head = (head + 1) % n
'''return''' ret

=== На списке ===
Ключевые поля:
* <code>ListItem(data : '''T''', next : '''ListItem''', prev : '''ListItem''')</code> {{---}} конструктор,
* <tex>\mathtt{tail}</tex> {{---}} ссылка на хвост,
* <tex>\mathtt{head}</tex> {{---}} ссылка на голову.

Дек очень просто реализуется на [[Список | двусвязном списке]]. Он состоит из элементов <tex>\mathtt {head\dots tail}</tex>. Элементы всегда добавляются либо в <tex>\mathtt{tail.prev}</tex>, либо в <tex>\mathtt{head.next}</tex>. В данной реализации не учитывается изъятие из пустого дека.

'''function''' initialize():
head = ListItem(''null'', ''null'', ''null'')
tail = ListItem(''null'', ''null'', head)
head.next = tail

'''function''' pushBack(x : '''T'''):
head = ListItem(x, head, ''null'')
head.next.prev = head

'''T''' popBack():
data = head.data
head = head.next
'''return''' data

'''function''' pushFront(x : '''T'''):
tail = ListItem(x, ''null'', tail)
tail.prev.next = tail

'''T''' popFront():
data = tail.data
tail = tail.prev
'''return''' data

=== На двух стеках ===
Ключевые поля:
* <tex>\mathtt{leftStack}</tex> {{---}} ссылка на хвост,
* <tex>\mathtt{rightStack}</tex> {{---}} ссылка на голову.

Храним два [[Стек | стека]] — <tex>\mathtt{leftStack}</tex> и <tex>\mathtt{rightStack}</tex>. Левый стек используем для операций <tex>\mathtt{popBack}</tex> и <tex>\mathtt{pushBack}</tex>, правый — для <tex>\mathtt{popFront}</tex> и <tex>\mathtt{pushFront}</tex>. Если мы хотим работать с левым стеком и при этом он оказывается пустым, то достаем нижнюю половину элементов из правого и кладем в левый, воспользовавшись при этом локальным стеком. Аналогично с правым стеком. Худшее время работы — <tex>O(n)</tex>.

'''function''' pushBack(x : '''T'''):
leftStack.push(x)

'''T''' popBack():
'''if''' '''not''' leftStack.empty()
'''return''' leftStack.pop()
'''else'''
'''int''' size = rightStack.size()
'''Stack<T>''' local
'''for''' i = 0 '''to''' size / 2
local.push(rightStack.pop())
'''while''' '''not''' rightStack.empty()
leftStack.push(rightStack.pop())
'''while''' '''not''' local.empty()
rightStack.push(local.pop())
'''return''' leftStack.pop()

'''function''' pushFront(x : '''T'''):
rightStack.push(x)

'''T''' popFront():
'''if''' '''not''' rightStack.empty()
'''return''' rightStack.pop()
'''else'''
'''int''' size = leftStack.size()
'''Stack<T>''' local
'''for''' i = 0 '''to''' size / 2
local.push(leftStack.pop())
'''while''' '''not''' leftStack.empty()
rightStack.push(leftStack.pop())
'''while''' '''not''' local.empty()
leftStack.push(local.pop())
'''return''' rightStack.pop()

== См. также ==
* [[Стек]]
* [[Очередь]]
* [[Персистентный дек]]

== Источники информации ==
* [[wikipedia:ru:Двусвязная_очередь|Википедия {{---}} Дек]]
* [[wikipedia:en:Deque|Wikipedia {{---}} Deque]]
* [http://opendatastructures.org/ods-cpp/2_5_Building_Deque_from_Two.html Open Data Structures {{---}} Building a Deque from Two Stacks]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]

Викиконспекты - Вклад участника [ru]

Дек