Двусторонняя очередь

Дек или двусторонняя очередь (double-ended queue) - это линейный список, в котором все операции вставки и удаления (и, как правило, операции доступа к данным) выполняются на обоих концах списка.

Дек является более общим вариантом стека или очереди. Кроме того, следует различать деки с ограниченным выводом (output-restricted deque) и с ограниченным вводом (input-restricted deque), в которых операции удаления и вставки элементов соответственно выполняются только на одном из концов.

При работе с деками используют понятия левый (left) и правый (right) концы.

Ссылки:

• Donald E. Knuth - The Art of Computer Programming, section 2.2.1