Деком (англ. deque, от double-ended queue) называется структура данных, которая позволяет добавлять элементы и в конец, и в начало, а также удалять элементы из конца и из начала. Все эти операции реализованы за O(1), то есть выполняются быстро.
В STL есть специальный контейнер deque, который реализует подобную функциональность. Для его использования необходимо подключить заголовочный файл deque:
#include<deque>
Объявляется дек, например, целых чисел так:
deque <int> D;
Дек поддерживает следущие методы:
| Название метода | Описание |
| size() | Возвращает размер дека |
| empty() | Возвращает true, если дек пуста, или false, если непуст |
| clear() | Очищает дек |
| front() | Возвращает значение первого элемента в деке |
| back() | Возвращает значение последнего элемента в деке |
| pop_front() | Удаляет первый элемент из дека, не возвращает значение |
| pop_back() | Удаляет последний элемент из дека, не возвращает значение |
| push_front(elem) | Добавляет новый элемент elem в начало дека |
| push_back(elem) | Добавляет новый элемент elem в конец дека |
У дека есть много общего с векторами. Например, к элементам дека можно обращаться по индексу, при помощи [i] или метода at(i). Эти обращения выполняются быстро - реализация дека насколько хитра, что можно быстро добавлять элементы в начало и в конец, а также быстро обращаться к элементу по его номеру. У дека, как и у вектора, есть методы erase, insert и resize, но они работают за линейное время.
Также с объектами класса deque допустимы операции =, ==, !=, <, >, <=, >=.
Подробней о контейнере deque можно прочитать в документации.