Изменения

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

Во всех циклических реализациях изначально присвоены следующие значения <tex> \mathtt{d.head = 0} </tex> и <tex> \mathtt{d.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 {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)

newDeque[i] = d[d.head]

d.head = 0 d.tail = n - 1

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

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

d.head = 0 d.tail = size()

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

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

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

d.head = 0 d.tail = n - 1

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

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

d.head = 0 d.tail = size()

'''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 - 1

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