Изменения

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

В даннн данной реализации изначально <tex> \mathtt{d.head = n- 1} </tex> и <tex> \mathtt{d.tail = n- 1} </tex>.

* <tex>\mathtt{d.head}</tex> {{---}} индекс головы дека,* <tex>\mathtt{d.tail}</tex> {{---}} индекс хвоста.

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

'''return''' d.head == d.tail

d[d.tail++] = x d.tail = d.tail + 1

d.tail = d.tail - 1 '''return''' d[d.--tail]

d.head = d.head [-- 1 d[d.head] = x

'''Treturn''' ret = d[d.head++] d.head = d.head + 1 '''return''' ret

Во всех циклических реализациях изначально присвоены следующие значения <tex> \mathtt{head = 0} </tex> и <tex> \mathtt{tail = 0} </tex>.

* <tex>\mathtt{d.head}</tex> {{---}} индекс головы дека,* <tex>\mathtt{d.tail}</tex> {{---}} индекс хвоста.

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

'''if''' (d.head == (d.tail + 1) % n)

d[d.tail] = x d.tail = (d.tail + 1) % n

d.tail = (d.tail - 1 + n) % n '''return''' d[d.tail]

'''if''' (d.head == (d.tail + 1) % n)

d.head = (d.head - 1 + n) % n d[d.head] = x

'''T''' ret = d[d.head] d.head = (d.head + 1) % n

* <tex>\mathtt{d.head}</tex> {{---}} индекс головы дека,* <tex>\mathtt{d.tail}</tex> {{---}} индекс хвоста,* <tex>\mathtt{capacity}</tex> {{---}} размер массива.

Дек состоит из элементов <tex>\mathtt {d[d.head\dots d.tail-1]}</tex> или <tex>\mathtt {d[0\dots d.tail-1]}</tex> и <tex>\mathtt {d[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 + d.tail

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

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

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

'''if''' (size() < capacity n / 4) '''T''' newDeque[capacity n / 2] '''int''' dequeSize = size() '''for''' i = 0 '''to''' size()dequeSize - 1 newDeque[i] = d[d.head] d.head = (d.head + 1) % n

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

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

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

'''if''' (size() < capacity n / 4) '''T''' newDeque[capacity n / 2] '''int''' dequeSize = size() '''for''' i = 0 '''to''' size()dequeSize - 1 newDeque[i] = d[d.head] d.head = (d.head + 1) % n

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

Храним два [[Стек | стека]] — <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>, однако, амортизационная стоимость операции — <tex>O(1)</tex>.

'''for''' i = 0 '''to''' size / 2

'''for''' i = 0 '''to''' size / 2

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