Дек

Определение

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

• [math] \mathtt{empty} [/math] — проверка на наличие элементов,
• [math] \mathtt{pushBack} [/math] (запись в конец) — операция вставки нового элемента в конец,
• [math] \mathtt{popBack} [/math] (снятие с конца) — операция удаления конечного элемента,
• [math] \mathtt{pushFront} [/math] (запись в начало) — операция вставки нового элемента в начало,
• [math] \mathtt{popFront} [/math] (снятие с начала) — операция вставки начального элемента.

Реализации

Дек расходует только [math]O(n)[/math] памяти, на хранение самих элементов.

На массиве

Ключевые поля:

• [math]\mathtt{d[1\dots n]} [/math] — массив, с помощью которого реализуется дек, способный вместить не более [math]n[/math] элементов,
• [math]\mathtt{d.head}[/math] — индекс головы дека,
• [math]\mathtt{d.tail}[/math] — индекс хвоста дека.

Дек состоит из элементов [math]\mathtt {s[d.tail\dots d.head]}[/math]. Если очень много раз добавлять в начало и столько же раз удалять конечные элементы, то скоро мы дойдем до границы, имея немного элементов, при этом добавление в начало вызовет переполнение. Поэтому имеет смысл брать индексы по модулю [math] \mathtt{n} [/math] и следить, чтобы они были не меньше единицы. Если происходит изъятие и стека, в котором индексы равны