Изменения

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

Изначально переменные <tex> \mathtt{head} </tex> и <tex> \mathtt{tail} </tex> должны различаться на единицу, причем <tex> \mathtt{head =tail - 1} </tex>.== На = Циклический дек на массиве константной длины ===

* <tex>\mathtt{d[10\dots n-1]}</tex> {{---}} массив, с помощью которого реализуется дек, способный вместить не более <tex>n</tex> элементов,

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

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

'''return''' <span style="color:red">error </span> "overflow"

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''' <span style="color:red">error </span> "overflow"

d.head = (d.head - 1 + n) % n + 1

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

=== На саморасширяющемся Циклический дек на динамическом массиве ===

* <tex>\mathtt{d[10\dots n-1]}</tex> {{---}} массив, в котором хранится дек,* <tex>\mathtt{newDeque[10\dots newSize]}</tex> {{---}} временный массив, где хранятся элементы после перекопирования,

Если реализовывать дек на динамическом массиве, то мы можем избежать ошибки переполнения. При выполнении операций <tex>\mathtt{pushBack}</tex> и <tex>\mathtt{pushFront}</tex> происходит проверка на переполнение и, если нужно, выделяется большее количество памяти под массив. Также происходит проверка на избыточность памяти, выделенной под дек при выполнении операций <tex>\mathtt{popBack}</tex> и <tex>\mathtt{popFront}</tex>. Если памяти слишком многопод дек выделено в четыре раза больше размера дека, то массив сокращаетсяв два раза. Для удобства выделим в отдельную функцию <tex>\mathtt{size}</tex> получение текущего размера дека.

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

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

newDeque[i] = d[d.tail head + 1] d.tail head = (d.tail head + 1) % n + 1

d.tail = capacity * 2- 1 d.head = capacity - 1* 2

d.tail = (d.tail - 2 + n1) % n + 1

'''return''' <span style="color:red">error </span> "underflow"

newDeque[i] = d[d.tail head + 1] d.tail head = (d.tail head + 1) % n + 1

d.tail head = capacity / 2- 1 d.head tail = size() + 1 d.tail = (d.tail - 1 + n) % n + 1

newDeque[i] = d[d.tail head + 1] d.tail head = (d.tail head + 1) % n + 1

d.tail = capacity * 2- 1 d.head = capacity - 1* 2

d.head = (d.head - 1 + n) % n + 1

'''return''' <span style="color:red">error </span> "underflow"

newDeque[i] = d[d.tail head + 1] d.tail head = (d.tail head + 1) % n + 1

d.tail head = capacity / 2- 1 d.head tail = size() + 1 d.head = (d.head - 2 + n1) % n + 1

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