1. 双端队列 (Deque) 概述

双端队列（Double-Ended Queue，简称 deque）是一种允许在其两端进行高效插入和删除操作的数据结构。与普通队列（只允许在一端插入和另一端删除）相比，双端队列更为灵活。

C++ 标准库中已经提供了 std::deque，但通过自行实现一个双端队列，可以更好地理解其内部机制和迭代器的工作原理。

2. 实现思路

为了实现一个高效的双端队列，我们需要考虑以下几点：

1. 动态数组：使用动态数组（如环形缓冲区）来存储元素，以便支持在两端进行常数时间的插入和删除。
2. 头尾指针：维护头部和尾部的索引，以便快速访问两端。
3. 自动扩展：当容量不足时，自动调整内部缓冲区的大小。
4. 迭代器支持：定义一个迭代器类，允许用户使用像 begin() 和 end() 这样的函数进行遍历。

接下来，我们将一步步实现这些功能。

3. 详细实现

3.1 内部数据结构

我们将使用一个动态分配的数组作为内部缓冲区，并通过头尾索引来管理队列的前后端。为了支持在两端高效插入和删除，我们将采用环形缓冲区的概念，即当索引达到数组的末端时，自动回绕到数组的开头。

3.2 Deque 类

下面是 Deque 类的基本结构和关键成员：

#include <iostream>
#include <stdexcept>
#include <iterator>

template <typename T>
class Deque {
private:
    T* buffer;               // 内部缓冲区
    size_t capacity;         // 缓冲区容量
    size_t front_idx;        // 头部索引
    size_t back_idx;         // 尾部索引
    size_t count;            // 当前元素数量

    // 调整容量
    void resize(size_t new_capacity) {
        T* new_buffer = new T[new_capacity];
        // 重新排列元素
        for (size_t i = 0; i < count; ++i) {
            new_buffer[i] = buffer[(front_idx + i) % capacity];
        }
        delete[] buffer;
        buffer = new_buffer;
        capacity = new_capacity;
        front_idx = 0;
        back_idx = count;
    }

public:
    // 构造函数
    Deque(size_t initial_capacity = 8)
        : capacity(initial_capacity), front_idx(0), back_idx(0), count(0) {
        buffer = new T[capacity];
    }

    // 析构函数
    ~Deque() {
        delete[] buffer;
    }

    // 复制构造函数和赋值运算符（省略，为简洁起见）

    // 检查是否为空
    bool empty() const {
        return count == 0;
    }

    // 获取大小
    size_t size() const {
        return count;
    }

    // 在前面插入元素
    void push_front(const T& value) {
        if (count == capacity) {
            resize(capacity * 2);
        }
        front_idx = (front_idx == 0) ? capacity - 1 : front_idx - 1;
        buffer[front_idx] = value;
        ++count;
    }

    // 在后面插入元素
    void push_back(const T& value) {
        if (count == capacity) {
            resize(capacity * 2);
        }
        buffer[back_idx] = value;
        back_idx = (back_idx + 1) % capacity;
        ++count;
    }

    // 从前面删除元素
    void pop_front() {
        if (empty()) {
            throw std::out_of_range("Deque is empty");
        }
        front_idx = (front_idx + 1) % capacity;
        --count;
    }

    // 从后面删除元素
    void pop_back() {
        if (empty()) {
            throw std::out_of_range("Deque is empty");
        }
        back_idx = (back_idx == 0) ? capacity - 1 : back_idx - 1;
        --count;
    }

    // 获取前端元素
    T& front() {
        if (empty()) {
            throw std::out_of_range("Deque is empty");
        }
        return buffer[front_idx];
    }

    const T& front() const {
        if (empty()) {
            throw std::out_of_range("Deque is empty");
        }
        return buffer[front_idx];
    }

    // 获取后端元素
    T& back() {
        if (empty()) {
            throw std::out_of_range("Deque is empty");
        }
        size_t last_idx = (back_idx == 0) ? capacity - 1 : back_idx - 1;
        return buffer[last_idx];
    }

    const T& back() const {
        if (empty()) {
            throw std::out_of_range("Deque is empty");
        }
        size_t last_idx = (back_idx == 0) ? capacity - 1 : back_idx - 1;
        return buffer[last_idx];
    }

    // 迭代器类将放在这里（见下一部分）

    // 迭代器类定义
    class Iterator {
    private:
        Deque<T>* deque_ptr;
        size_t index;
        size_t pos;

    public:
        using iterator_category = std::bidirectional_iterator_tag;
        using value_type        = T;
        using difference_type   = std::ptrdiff_t;
        using pointer           = T*;
        using reference         = T&;

        Iterator(Deque<T>* deque, size_t position)
            : deque_ptr(deque), pos(position) {}

        // 解引用操作
        reference operator*() const {
            size_t real_idx = (deque_ptr->front_idx + pos) % deque_ptr->capacity;
            return deque_ptr->buffer[real_idx];
        }

        pointer operator->() const {
            size_t real_idx = (deque_ptr->front_idx + pos) % deque_ptr->capacity;
            return &(deque_ptr->buffer[real_idx]);
        }

        // 前置递增
        Iterator& operator++() {
            ++pos;
            return *this;
        }

        // 后置递增
        Iterator operator++(int) {
            Iterator temp = *this;
            ++pos;
            return temp;
        }

        // 前置递减
        Iterator& operator--() {
            --pos;
            return *this;
        }

        // 后置递减
        Iterator operator--(int) {
            Iterator temp = *this;
            --pos;
            return temp;
        }

        // 比较操作
        bool operator==(const Iterator& other) const {
            return (deque_ptr == other.deque_ptr) && (pos == other.pos);
        }

        bool operator!=(const Iterator& other) const {
            return !(*this == other);
        }
    };

    // 获取 begin 迭代器
    Iterator begin() {
        return Iterator(this, 0);
    }

    // 获取 end 迭代器
    Iterator end() {
        return Iterator(this, count);
    }
};

3.3 迭代器类

在上面的 Deque 类中，我们定义了一个嵌套的 Iterator 类。这个迭代器支持前向和后向遍历，并且可以与标准的 C++ 迭代器兼容。

关键点解释：

1. 成员变量：
   • deque_ptr：指向包含此迭代器的 Deque 实例。
   • pos：相对于队列头部的位置。
2. 重载运算符：
   • operator* 和 operator->：用于访问当前元素。
   • operator++ 和 operator--：前置和后置递增和递减，用于移动迭代器。
   • operator== 和 operator!=：用于比较两个迭代器是否相同。
3. 注意事项：
   • 迭代器并不管理元素的生命周期，只是提供遍历接口。
   • 迭代器的有效性依赖于队列的修改操作（如插入和删除）。在实际应用中，需要注意迭代器失效的问题。

4. 使用示例

下面是一个使用上述 Deque 类及其迭代器的示例程序：

#include <iostream>
#include <string>

// 假设 Deque 类已经定义在这里

int main() {
    Deque<std::string> dq;

    // 在后面插入元素
    dq.push_back("Apple");
    dq.push_back("Banana");
    dq.push_back("Cherry");

    // 在前面插入元素
    dq.push_front("Date");
    dq.push_front("Elderberry");

    // 显示队列大小
    std::cout << "Deque 大小: " << dq.size() << std::endl;

    // 使用迭代器进行遍历
    std::cout << "Deque 元素: ";
    for (auto it = dq.begin(); it != dq.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 访问前端和后端元素
    std::cout << "前端元素: " << dq.front() << std::endl;
    std::cout << "后端元素: " << dq.back() << std::endl;

    // 删除元素
    dq.pop_front();
    dq.pop_back();

    // 再次遍历
    std::cout << "删除元素后的 Deque: ";
    for (auto it = dq.begin(); it != dq.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

预期输出

Deque 大小: 5
Deque 元素: Elderberry Date Apple Banana Cherry 
前端元素: Elderberry
后端元素: Cherry
删除元素后的 Deque: Date Apple Banana

解释：

1. 插入操作：
   • 使用 push_back 在队列的后端插入 "Apple", "Banana", "Cherry"。
   • 使用 push_front 在队列的前端插入 "Date", "Elderberry"。
   • 最终队列顺序为：Elderberry, Date, Apple, Banana, Cherry
2. 遍历操作：
   • 使用迭代器从 begin() 到 end() 遍历并打印所有元素。
3. 访问元素：
   • 使用 front() 获取队列前端的元素。
   • 使用 back() 获取队列后端的元素。
4. 删除操作：
   • 使用 pop_front 删除前端元素（"Elderberry"）。
   • 使用 pop_back 删除后端元素（"Cherry"）。
   • 删除后，队列顺序为：Date, Apple, Banana

5. 完整代码

以下是完整的 Deque 类及其使用示例代码：

#include <iostream>
#include <stdexcept>
#include <iterator>

// Deque 类定义
template <typename T>
class Deque {
private:
    T* buffer;               // 内部缓冲区
    size_t capacity;         // 缓冲区容量
    size_t front_idx;        // 头部索引
    size_t back_idx;         // 尾部索引
    size_t count;            // 当前元素数量

    // 调整容量
    void resize(size_t new_capacity) {
        T* new_buffer = new T[new_capacity];
        // 重新排列元素
        for (size_t i = 0; i < count; ++i) {
            new_buffer[i] = buffer[(front_idx + i) % capacity];
        }
        delete[] buffer;
        buffer = new_buffer;
        capacity = new_capacity;
        front_idx = 0;
        back_idx = count;
    }

public:
    // 构造函数
    Deque(size_t initial_capacity = 8)
        : capacity(initial_capacity), front_idx(0), back_idx(0), count(0) {
        buffer = new T[capacity];
    }

    // 析构函数
    ~Deque() {
        delete[] buffer;
    }

    // 禁用复制构造函数和赋值运算符（为了简洁，可根据需要实现）
    Deque(const Deque& other) = delete;
    Deque& operator=(const Deque& other) = delete;

    // 检查是否为空
    bool empty() const {
        return count == 0;
    }

    // 获取大小
    size_t size() const {
        return count;
    }

    // 在前面插入元素
    void push_front(const T& value) {
        if (count == capacity) {
            resize(capacity * 2);
        }
        front_idx = (front_idx == 0) ? capacity - 1 : front_idx - 1;
        buffer[front_idx] = value;
        ++count;
    }

    // 在后面插入元素
    void push_back(const T& value) {
        if (count == capacity) {
            resize(capacity * 2);
        }
        buffer[back_idx] = value;
        back_idx = (back_idx + 1) % capacity;
        ++count;
    }

    // 从前面删除元素
    void pop_front() {
        if (empty()) {
            throw std::out_of_range("Deque is empty");
        }
        front_idx = (front_idx + 1) % capacity;
        --count;
    }

    // 从后面删除元素
    void pop_back() {
        if (empty()) {
            throw std::out_of_range("Deque is empty");
        }
        back_idx = (back_idx == 0) ? capacity - 1 : back_idx - 1;
        --count;
    }

    // 获取前端元素
    T& front() {
        if (empty()) {
            throw std::out_of_range("Deque is empty");
        }
        return buffer[front_idx];
    }

    const T& front() const {
        if (empty()) {
            throw std::out_of_range("Deque is empty");
        }
        return buffer[front_idx];
    }

    // 获取后端元素
    T& back() {
        if (empty()) {
            throw std::out_of_range("Deque is empty");
        }
        size_t last_idx = (back_idx == 0) ? capacity - 1 : back_idx - 1;
        return buffer[last_idx];
    }

    const T& back() const {
        if (empty()) {
            throw std::out_of_range("Deque is empty");
        }
        size_t last_idx = (back_idx == 0) ? capacity - 1 : back_idx - 1;
        return buffer[last_idx];
    }

    // 迭代器类定义
    class Iterator {
    private:
        Deque<T>* deque_ptr;
        size_t pos;

    public:
        using iterator_category = std::bidirectional_iterator_tag;
        using value_type        = T;
        using difference_type   = std::ptrdiff_t;
        using pointer           = T*;
        using reference         = T&;

        Iterator(Deque<T>* deque, size_t position)
            : deque_ptr(deque), pos(position) {}

        // 解引用操作
        reference operator*() const {
            size_t real_idx = (deque_ptr->front_idx + pos) % deque_ptr->capacity;
            return deque_ptr->buffer[real_idx];
        }

        pointer operator->() const {
            size_t real_idx = (deque_ptr->front_idx + pos) % deque_ptr->capacity;
            return &(deque_ptr->buffer[real_idx]);
        }

        // 前置递增
        Iterator& operator++() {
            ++pos;
            return *this;
        }

        // 后置递增
        Iterator operator++(int) {
            Iterator temp = *this;
            ++pos;
            return temp;
        }

        // 前置递减
        Iterator& operator--() {
            --pos;
            return *this;
        }

        // 后置递减
        Iterator operator--(int) {
            Iterator temp = *this;
            --pos;
            return temp;
        }

        // 比较操作
        bool operator==(const Iterator& other) const {
            return (deque_ptr == other.deque_ptr) && (pos == other.pos);
        }

        bool operator!=(const Iterator& other) const {
            return !(*this == other);
        }
    };

    // 获取 begin 迭代器
    Iterator begin() {
        return Iterator(this, 0);
    }

    // 获取 end 迭代器
    Iterator end() {
        return Iterator(this, count);
    }
};

// 使用示例
int main() {
    Deque<std::string> dq;

    // 在后面插入元素
    dq.push_back("Apple");
    dq.push_back("Banana");
    dq.push_back("Cherry");

    // 在前面插入元素
    dq.push_front("Date");
    dq.push_front("Elderberry");

    // 显示队列大小
    std::cout << "Deque 大小: " << dq.size() << std::endl;

    // 使用迭代器进行遍历
    std::cout << "Deque 元素: ";
    for (auto it = dq.begin(); it != dq.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 访问前端和后端元素
    std::cout << "前端元素: " << dq.front() << std::endl;
    std::cout << "后端元素: " << dq.back() << std::endl;

    // 删除元素
    dq.pop_front();
    dq.pop_back();

    // 再次遍历
    std::cout << "删除元素后的 Deque: ";
    for (auto it = dq.begin(); it != dq.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

编译和运行

保存上述代码到一个文件，例如 DequeWithIterator.cpp，然后使用 C++ 编译器进行编译和运行：

g++ -std=c++11 -o DequeWithIterator DequeWithIterator.cpp
./DequeWithIterator

预期输出

Deque 大小: 5
Deque 元素: Elderberry Date Apple Banana Cherry 
前端元素: Elderberry
后端元素: Cherry
删除元素后的 Deque: Date Apple Banana

6. 总结

通过上述步骤，我们成功实现了一个支持双端插入和删除的双端队列（deque），并添加了迭代器支持，使其能够与标准的 C++ 迭代器接口兼容。这个实现包含了以下关键点：

1. 内部缓冲区管理：
   • 使用动态数组并采用环形缓冲区的方式，支持高效的双端操作。
   • 自动调整缓冲区的容量，确保在元素数量增加时仍能保持高效。
2. 迭代器实现：
   • 定义了一个嵌套的 Iterator 类，支持前向和后向遍历。
   • 重载了必要的运算符（如 *, ->, ++, --, ==, !=），以实现与标准迭代器的兼容。
3. 基本操作：
   • push_front 和 push_back：分别在队列的前端和后端插入元素。
   • pop_front 和 pop_back：分别从队列的前端和后端删除元素。
   • front 和 back：访问队列的前端和后端元素。