Изменения

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

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