Дек

Определение

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

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

Реализация на двусвязном списке

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