Изменения

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

'''booleanT''' popFront(): '''if''' (empty()) '''return''' <span style="color:red">error</span> "underflow" '''return''' d.[head % n + 1 +] === Циклический дек на массиве константной длины ===Во всех циклических реализациях изначально присвоены следующие значения <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>.

'''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>\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]