Что такое Deque?

Deque в C++

Deque (Double-Ended Queue) — это контейнер из стандартной библиотеки C++ (STL), который позволяет эффективно добавлять и удалять элементы как в начало, так и в конец контейнера. Название происходит от англ. "двусторонняя очередь". Deque находится в заголовочном файле <deque>.

Основные характеристики

Структура данных: Deque обычно реализуется как двусвязный список блоков (chunks) памяти, а не как одно сплошное выделение, как в vector. Это позволяет ему избежать дорогостоящего переаллокирования при добавлении элементов с обеих сторон.

Сложность операций:

• push_front() / push_back() — O(1) амортизированная
• pop_front() / pop_back() — O(1)
• Доступ к элементу по индексу — O(1)
• Вставка/удаление в середину — O(n)

Основные методы

#include <deque>
#include <iostream>

std::deque<int> dq;

// Добавление элементов
dq.push_back(1);    // Добавить в конец
dq.push_back(2);
dq.push_front(0);   // Добавить в начало

// Удаление элементов
dq.pop_back();      // Удалить с конца
dq.pop_front();     // Удалить с начала

// Доступ к элементам
int first = dq.front();  // Первый элемент
int last = dq.back();    // Последний элемент
int elem = dq[1];        // Доступ по индексу

// Размер и проверка
size_t size = dq.size();
bool empty = dq.empty();

// Итерация
for (int val : dq) {
    std::cout << val << " ";
}

// Очистка
dq.clear();

Различия между Deque и Vector

Практические примеры

Пример 1: Реализация очереди (FIFO)

class Queue {
private:
    std::deque<int> data;
public:
    void enqueue(int val) {
        data.push_back(val);
    }
    
    int dequeue() {
        int val = data.front();
        data.pop_front();
        return val;
    }
    
    bool isEmpty() const {
        return data.empty();
    }
};

Пример 2: Скользящее окно (Sliding Window)

std::vector<int> maxSlidingWindow(const std::vector<int>& nums, int k) {
    std::deque<int> dq;  // Хранит индексы
    std::vector<int> result;
    
    for (int i = 0; i < nums.size(); i++) {
        // Удалить элементы вне окна
        while (!dq.empty() && dq.front() < i - k + 1) {
            dq.pop_front();
        }
        
        // Удалить меньшие элементы
        while (!dq.empty() && nums[dq.back()] < nums[i]) {
            dq.pop_back();
        }
        
        dq.push_back(i);
        
        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);
        }
    }
    
    return result;
}

Пример 3: Проверка палиндрома

bool isPalindrome(const std::string& s) {
    std::deque<char> dq;
    
    for (char c : s) {
        if (std::isalnum(c)) {
            dq.push_back(std::tolower(c));
        }
    }
    
    while (dq.size() > 1) {
        if (dq.front() != dq.back()) {
            return false;
        }
        dq.pop_front();
        dq.pop_back();
    }
    
    return true;
}

Когда использовать Deque

• Очереди — когда нужны операции с обоих концов
• Скользящие окна — эффективная работа с дейзвовыми операциями
• Двусторонние очереди — когда нужны операции enqueue/dequeue с обоих концов
• Конвейеры обработки — когда нужны быстрые операции с началом и концом

Недостатки

• Хуже кэш-локальность по сравнению с vector
• Фрагментированная память может привести к дополнительным обращениям
• Если нужен только push_back и pop_back, vector эффективнее

Deque — мощный инструмент для задач, требующих двусторонней работы с очередями, и он часто встречается в системном программировании и алгоритмах обработки потоков данных.