C++如何实现一个双端队列(deque)_C++数据结构与双端队列实现

新闻中心 NEWS CENTER

您当前位置：首页 > 新闻中心 > 网络学院

C++如何实现一个双端队列(deque)_C++数据结构与双端队列实现

2025-11-11

浏览次数：次

返回列表

双端队列可通过动态数组实现，支持首尾插入删除。使用循环缓冲与自动扩容，关键操作均摊O(1)，但频繁扩容时性能低于STL的分段存储deque。

c++如何实现一个双端队列(deque)_c++数据结构与双端队列实现

双端队列（deque，全称 double-ended queue）是一种可以在两端进行插入和删除操作的线性数据结构。C++ 中标准库已经提供了 std::deque，但理解其底层实现有助于加深对数据结构和内存管理的理解。下面介绍如何手动实现一个简单的双端队列。

基本设计思路

为了高效地在前后两端插入和删除元素，我们可以使用动态数组+循环缓冲或分段连续存储的方式。这里采用简化版的动态数组实现，支持自动扩容。

关键成员变量包括：

data：指向动态分配的数组
capacity：当前数组容量
front_index：指向队首元素的索引
rear_index：指向队尾下一个空位的索引
size：当前元素个数

核心操作实现

以下是主要接口的实现逻辑：

1. 构造函数与析构函数

初始化数组空间并设置初始状态：

分配初始容量（如 8）的数组
front_index 和 rear_index 都设为 0
size 设为 0

2. push_front(T value)

在队首插入元素：

检查是否需要扩容
front_index 向前移动（模运算处理循环）
将元素放入 front_index 位置
size 加一

3. push_back(T value)

在队尾插入元素：

检查是否需要扩容
将元素放入 rear_index 位置
rear_index 向后移动（模 capacity）
size 加一

4. pop_front() 和 pop_back()

Perplexity

Perplexity是一个ChatGPT和谷歌结合的超级工具，可以让你在浏览互联网时提出问题或获得即时摘要

302 查看详情 Perplexity

分别删除队首和队尾元素：

检查队列是否为空
移动对应索引（front_index 或 rear_index）
size 减一

5. front() 和 back()

返回队首或队尾元素的引用：

不修改索引，只访问对应位置的数据

6. 扩容机制（resize）

当空间不足时，分配更大的数组（如原容量 × 2），然后将旧数据按顺序复制过去，注意 front_index 到 rear_index 的环绕情况。

代码框架示例

以下是一个简化的 C++ 实现框架：

template <typename T>
class Deque {
private:
    T* data;
    int capacity;
    int front_index;
    int rear_index;
    int size;
<pre class='brush:php;toolbar:false;'>void resize() {
    // 扩容并复制数据
    int new_capacity = capacity * 2;
    T* new_data = new T[new_capacity];
    int j = 0;
    for (int i = 0; i < size; ++i) {
        new_data[j++] = data[(front_index + i) % capacity];
    }
    delete[] data;
    data = new_data;
    front_index = 0;
    rear_index = size;
    capacity = new_capacity;
}

public: Deque(int cap = 8) : capacity(cap), front_index(0), rear_index(0), size(0) { data = new T[capacity]; }

~Deque() {
    delete[] data;
}

void push_front(const T& value) {
    if (size == capacity) resize();
    front_index = (front_index - 1 + capacity) % capacity;
    data[front_index] = value;
    ++size;
}

void push_back(const T& value) {
    if (size == capacity) resize();
    data[rear_index] = value;
    rear_index = (rear_index + 1) % capacity;
    ++size;
}

void pop_front() {
    if (empty()) throw std::runtime_error("Deque is empty");
    front_index = (front_index + 1) % capacity;
    --size;
}

void pop_back() {
    if (empty()) throw std::runtime_error("Deque is empty");
    rear_index = (rear_index - 1 + capacity) % capacity;
    --size;
}

T& front() {
    if (empty()) throw std::runtime_error("Deque is empty");
    return data[front_index];
}

T& back() {
    if (empty()) throw std::runtime_error("Deque is empty");
    return data[(rear_index - 1 + capacity) % capacity];
}

bool empty() const {
    return size == 0;
}

int get_size() const {
    return size;
}

};