Что такое deque?

Sobes Copilot

Получайте ответы в реальном времени

Ответ от нейросети

sobes.tech AI

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

Её основные характеристики:

Динамический размер: Размер может меняться во время выполнения.
Случайный доступ: Элементы можно получить по индексу за время O(1).
Эффективное добавление/удаление: Операции push_front, pop_front, push_back, pop_back выполняются в среднем за время O(1).
Непрерывная память: В отличие от std::vector, элементы std::deque не обязательно хранятся в едином непрерывном блоке памяти. Он обычно реализован как последовательность блоков фиксированного размера.

Сравнение с std::vector и std::list:

Характеристика	`std::vector`	`std::deque`	`std::list`
Доступ по индексу	O(1)	O(1)	O(n)
Вставка/удаление в начале	O(n)	O(1)	O(1)
Вставка/удаление в конце	Амортизированно O(1)	O(1)	O(1)
Вставка/удаление в середине	O(n)	O(n) (в среднем)	O(1) (по итератору)
Занимаемая память	Непрерывный блок, возможен оверхед	Несколько блоков, возможен оверхед	Каждый элемент с указателями

#include <deque>
#include <iostream>

int main() {
    std::deque<int> dq;

    // Добавление в конец
    dq.push_back(10);
    dq.push_back(20);

    // Добавление в начало
    dq.push_front(5);
    dq.push_front(0);

    // Доступ по индексу
    std::cout << "Element at index 2: " << dq[2] << std::endl; // Вывод: 10

    // Удаление с начала
    dq.pop_front(); // Удален 0

    // Удаление с конца
    dq.pop_back(); // Удален 20

    // Итерация
    std::cout << "Deque elements: ";
    for (int val : dq) {
        std::cout << val << " "; // Вывод: 5 10
    }
    std::cout << std::endl;

    return 0;
}

Используется, когда требуется частая вставка или удаление элементов с обоих концов очереди и при этом нужен эффективный доступ по индексу.