Подразделы

Другие разделы

Дата и время

01/04/2025 15:26:06

Авторизация

Зарегистрироваться
Восстановить пароль

Линейные АТД

Список Массив и Строка Стек Очередь Двухсторонняя очередь Очередь с приоритетами Множество Словарь

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

Двухсторонняя очередь или дек (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();`
`

Варианты реализации дека:

дек фиксированного размера – на основе массива
на основе двусвязного списка
в STL через нелинейную структуру данных, где данные делятся на куски по 16 Кбайт.

дек

deque в С++ поддерживает также интерфейсы АТД Список и АТД Массив. Добавление в начало происходит быстрее, чем у vector. Также быстрее выполняется добавление в конец (если у vector не сделано резервирование памяти).

width:500px|benchmark