*Двухсторонняя очередь* или дек (deque — double ended queue) - это список,
в котором элементы можно добавлять и удалять как в начало, так и в конец.
Базовые операции для дека:
Операция|Эффективность|Вызов
--|--|--
конструктор (пустой набор) |`O(1)`| ``std::queue<int> s;``
количество и/или проверка на пустоту |`O(1)`| ``int len=s.size();``\
``if(s.empty())...``
добавить значение в начало, в конец |`O(1)`| ``s.push_front(x);``\
``s.push_back(x);``
первый (последний) элемент |`O(1)`| ``int t=s.front();``\
``t=s.back();``
убрать первый, последний |`O(1)`| ``s.pop_front();``\
``s.pop_back();``
```
--
Варианты реализации дека:
* дек фиксированного размера -- на основе массива
* на основе [двусвязного списка](viz/deque.html)
* в STL через нелинейную структуру данных, где данные делятся на куски по 16 Кбайт.
``deque`` в С++ поддерживает также интерфейсы АТД Список и АТД Массив.
Добавление в начало происходит быстрее, чем у ``vector``. Также быстрее выполняется добавление в конец (если у ``vector`` не сделано резервирование памяти).
Линейные АТД
Начало
Учебные материалы