手写双端队列

Posted on | In

1. 双端队列 (Deque) 概述

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

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

2. 实现思路

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

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

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

3. 详细实现

3.1 内部数据结构

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

3.2 Deque 类

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
#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 类及其迭代器的示例程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#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;
}

预期输出

1
2
3
4
5
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 类及其使用示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
#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++ 编译器进行编译和运行：

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

预期输出

1
2
3
4
5
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：访问队列的前端和后端元素。