Изменения

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

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