手写双端对列

1
#include <iostream>
2
#include <string>
3

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

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

9
    // 在后面插入元素
10
    dq.push_back("Apple");
11
    dq.push_back("Banana");
12
    dq.push_back("Cherry");
13

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

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

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

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

32
    // 删除元素
33
    dq.pop_front();
34
    dq.pop_back();
35

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

43
    return 0;
44
}

1
#include <iostream>
2
#include <stdexcept>
3
#include <iterator>
4

5
// Deque 类定义
6
template <typename T>
7
class Deque {
8
private:
9
    T* buffer;               // 内部缓冲区
10
    size_t capacity;         // 缓冲区容量
11
    size_t front_idx;        // 头部索引
12
    size_t back_idx;         // 尾部索引
13
    size_t count;            // 当前元素数量
14

15
    // 调整容量
16
    void resize(size_t new_capacity) {
17
        T* new_buffer = new T[new_capacity];
18
        // 重新排列元素
19
        for (size_t i = 0; i < count; ++i) {
20
            new_buffer[i] = buffer[(front_idx + i) % capacity];
21
        }
22
        delete[] buffer;
23
        buffer = new_buffer;
24
        capacity = new_capacity;
25
        front_idx = 0;
26
        back_idx = count;
27
    }
28

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

36
    // 析构函数
37
    ~Deque() {
38
        delete[] buffer;
39
    }
40

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

45
    // 检查是否为空
46
    bool empty() const {
47
        return count == 0;
48
    }
49

50
    // 获取大小
51
    size_t size() const {
52
        return count;
53
    }
54

55
    // 在前面插入元素
56
    void push_front(const T& value) {
57
        if (count == capacity) {
58
            resize(capacity * 2);
59
        }
60
        front_idx = (front_idx == 0) ? capacity - 1 : front_idx - 1;
61
        buffer[front_idx] = value;
62
        ++count;
63
    }
64

65
    // 在后面插入元素
66
    void push_back(const T& value) {
67
        if (count == capacity) {
68
            resize(capacity * 2);
69
        }
70
        buffer[back_idx] = value;
71
        back_idx = (back_idx + 1) % capacity;
72
        ++count;
73
    }
74

75
    // 从前面删除元素
76
    void pop_front() {
77
        if (empty()) {
78
            throw std::out_of_range("Deque is empty");
79
        }
80
        front_idx = (front_idx + 1) % capacity;
81
        --count;
82
    }
83

84
    // 从后面删除元素
85
    void pop_back() {
86
        if (empty()) {
87
            throw std::out_of_range("Deque is empty");
88
        }
89
        back_idx = (back_idx == 0) ? capacity - 1 : back_idx - 1;
90
        --count;
91
    }
92

93
    // 获取前端元素
94
    T& front() {
95
        if (empty()) {
96
            throw std::out_of_range("Deque is empty");
97
        }
98
        return buffer[front_idx];
99
    }
100

101
    const T& front() const {
102
        if (empty()) {
103
            throw std::out_of_range("Deque is empty");
104
        }
105
        return buffer[front_idx];
106
    }
107

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

117
    const T& back() const {
118
        if (empty()) {
119
            throw std::out_of_range("Deque is empty");
120
        }
121
        size_t last_idx = (back_idx == 0) ? capacity - 1 : back_idx - 1;
122
        return buffer[last_idx];
123
    }
124

125
    // 迭代器类定义
126
    class Iterator {
127
    private:
128
        Deque<T>* deque_ptr;
129
        size_t pos;
130

131
    public:
132
        using iterator_category = std::bidirectional_iterator_tag;
133
        using value_type        = T;
134
        using difference_type   = std::ptrdiff_t;
135
        using pointer           = T*;
136
        using reference         = T&;
137

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

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

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

152
        // 前置递增
153
        Iterator& operator++() {
154
            ++pos;
155
            return *this;
156
        }
157

158
        // 后置递增
159
        Iterator operator++(int) {
160
            Iterator temp = *this;
161
            ++pos;
162
            return temp;
163
        }
164

165
        // 前置递减
166
        Iterator& operator--() {
167
            --pos;
168
            return *this;
169
        }
170

171
        // 后置递减
172
        Iterator operator--(int) {
173
            Iterator temp = *this;
174
            --pos;
175
            return temp;
176
        }
177

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

183
        bool operator!=(const Iterator& other) const {
184
            return !(*this == other);
185
        }
186
    };
187

188
    // 获取 begin 迭代器
189
    Iterator begin() {
190
        return Iterator(this, 0);
191
    }
192

193
    // 获取 end 迭代器
194
    Iterator end() {
195
        return Iterator(this, count);
196
    }
197
};
198

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

203
    // 在后面插入元素
204
    dq.push_back("Apple");
205
    dq.push_back("Banana");
206
    dq.push_back("Cherry");
207

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

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

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

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

226
    // 删除元素
227
    dq.pop_front();
228
    dq.pop_back();
229

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

237
    return 0;
238
}