Изменения

'''Дек''' (от англ. ''deque'' {{---}} double ended queue) {{---}} структура данных, представляющая из себя список элементов, в которой добавление новых элементов и удаление существующих производится с обоих концов. Эта структура поддерживает как FIFO, так и LIFO, поэтому на ней можно реализовать как [[Стек | стек]], так и [[Очередь | очередь]]. В первом случае нужно использовать только методы головы или хвоста, во втором {{---}} методы push и pop двух разных концов. Дек можно воспринимать как двустороннюю очередь или двусторонний стек. Он имеет следующие операции:

==Реализации==Дек расходует только <tex>O(n)</tex> памяти, на хранение самих элементов.=== На массиве Простая реализация ===В данной реализации изначально <tex> \mathtt{head = n - 1} </tex> и <tex> \mathtt{tail = n - 1} </tex>.

* <tex>\mathtt{d[10\dots 2 \times n- 1]}</tex> {{---}} массив, с помощью которого реализуется дек, способный вместить не более <tex>n</tex> элементов,* <tex>\mathtt{d.head}</tex> {{---}} индекс головы дека,* <tex>\mathtt{d.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''' <span style="color:red">error</span> "underflow" '''return''' d[--tail\dots ]  '''function''' pushFront(x : '''T'''): d[--head] = x  '''T''' popFront(): '''if''' (empty()) '''return''' <span style="color:red">error</span> "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> {{---}} индекс хвоста.

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

'''if''' (d.head == d.(tail+ 1) % n) '''return''' <span style="color:red">error </span> "overflow" d[d.tail] = x d.tail = (d.tail - 2 + n1) % n + 1

'''return''' <span style="color:red">error </span> "underflow" d.tail = d.(tail - 1 + n) % n + 1 '''return''' d[d.tail]

'''if''' (d.head == d.(tail+ 1) % n) '''return''' <span style="color:red">error </span> "overflow" d[d.head] = x(head - 1 + n) % n d.[head ] = d.head % n + 1x

'''return''' <span style="color:red">error </span> "underflow" '''T''' ret = d.[head] head = (d.head - 2 + n1) % n + 1 '''return''' d[d.head]ret

Все операции выполняются за <tex>O(1)</tex>.=== На саморасширяющемся Циклический дек на динамическом массиве ===

* <tex>\mathtt{n}</tex> {{---}} размер массива,* <tex>\mathtt{d[10\dots n-1]}</tex> {{---}} массив, в котором хранится дек,* <tex>\mathtt{newDeque[10\dots newSize]}</tex> {{---}} временный массив, где хранятся элементы после перекопирования,* <tex>\mathtt{d.head}</tex> {{---}} индекс головы дека,* <tex>\mathtt{d.tail}</tex> {{---}} индекс хвоста дека,* <tex>\mathtt{capacity}</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> получение текущего размера дека.

'''if''' d.tail > d.head '''return''' n - d.head + tail + d.head - 1

'''return''' d.head - d.tail - 1head

'''if''' (d.head == d.(tail+ 1) % n) '''T''' newDeque[capacity n * 2] '''for''' i = 1 0 '''to''' capacity n - 12 newDeque[i] = d[d.tail + 1head] d.tail head = d.tail (head + 1) % n + 1

d.tail head = capacity * 20 d.head tail = capacity n - 1 capacity n *= capacity * 2 d[d.tail] = x d.tail = (d.tail - 2 + n1) % n + 1

'''return''' <span style="color:red">error </span> "underflow" '''if''' (size() < capacity n / 4) '''T''' newDeque[capacity n / 2] '''int''' dequeSize = size() '''for''' i = 1 0 '''to''' size()dequeSize - 1 newDeque[i] = d[d.tail + 1head] d.tail head = d.tail (head + 1) % n + 1

d.head = 0 tail = capacity / 2dequeSize d.head n /= size() + 12 d.tail = d.(tail - 1 + n) % n + 1 '''return''' d[d.tail]

'''if''' (d.head == d.(tail+ 1) % n) '''T''' newDeque[capacity n * 2] '''for''' i = 1 0 '''to''' capacity n - 12 newDeque[i] = d[d.tail + 1head] d.tail head = d.tail (head + 1) % n + 1

d.head = 0 tail = capacity n - 1 n * = 2 d. head = capacity (head - 1+ n) % n d[d.head] = x d.head = d.head % n + 1

'''return''' <span style="color:red">error </span> "underflow" '''if''' (size() < capacity n / 4) '''T''' newDeque[capacity n / 2] '''int''' dequeSize = size() '''for''' i = 1 0 '''to''' size()dequeSize - 1 newDeque[i] = d[d.tail + 1head] d.tail head = d.tail (head + 1) % n + 1

d.head = 0 tail = capacity dequeSize n / = 2 '''T''' ret = d.[head = size() + 1] d.head = (d.head - 2 + n1) % n + 1 '''return''' d[d.head]ret

Дек очень просто реализуется на [[Список | двусвязном списке]]. Он состоит из элементов <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

tail head = ListItem(x, tailhead, ''null'') tailhead.next.prev = tailhead

data = tailhead.data tail head = tailhead.next

head tail = ListItem(x, ''null'', fronttail) headtail.prev.next = headtail

data = headtail.data head tail = headtail.prev

Храним два [[Стек | стека - ]] — <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>.

==Источники информации==* [[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] [[Категория: Дискретная математика и алгоритмы]][[Категория: Амортизационный анализ]]