[数据结构与算法]c++顺序容器-双端队列deque

概念

双端队列是一个类模板，其由若干个块构成，每个块中元素的地址是连续的，块之间的地址是不连续的。用户可以从前端或后端快速地插入与删除元素，并可以快速地随机访问元素，但在中间位置插入和删除元素速度较慢。deque不像vector一样将所有元素存放在一个连续的内存块，而是采用多个连续的存储块存放数据，由于重新分配空间后原有的元素不需要复制，所以空间的重新分配要快于vector。

声明

#include <iostream>
#include <deque>
using namespace std;
int main(void){
    deque<int> dq1; // 声明空（整型）双端队列（以下简称队列）
    
    deque<int> dq2a = deque<int>(10); // 声明初始空间大小为10的整型队列
    deque<int> de2b(10); // 同上
    
    deque<int> dq3a = deque<int>(5,1); // 声明初始空间大小为5，默认值为1的整型队列
    deque<int> dq3b(5,1); // 同上
    
    int arr[] = { 1,2,3,4,5 };
    deque<int> dq4 = deque<int>(arr, arr + 5); // 通过数组首尾指针顺序填充初始化队列
    
    deque<int> dq5 = deque<int>(dq3b); // 拷贝构造
    return 0;
}

使用

常用方法

1. empty(): 队列判空
2. size(): 返回队列元素个数
3. front(): 取队头元素
4. back(): 取队尾元素
5. push_front(value): 在队头插入元素value
6. push_back(value): 在队尾插入元素value
7. pop_front(): 删除队头元素
8. pop_back(): 删除队尾元素
9. clear(): 清空队列
10. begin(): 返回指向第一个元素的正向迭代器
11. end(): 返回指向最后一个元素的后一个位置的正向迭代器
12. rbegin(): 返回指向最后一个元素的逆向迭代器
13. rend(): 返回指向第一个元素前一个元素的逆向迭代器

Example

#include <iostream>
#include <deque>
using namespace std;
int main(void) {

    deque<int> dq = deque<int>();
    
    dq.push_back(5); // 队头插入元素
    dq.push_back(10);
    dq.push_front(1); // 队尾插入元素
    dq.push_front(0);

    cout << dq.empty() << endl; // 队列判空

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

    cout << dq.size() << endl; // 输出队列元素个数

    int a = dq[0]; // 通过索引获取元素

    for (auto each : dq) // for-each迭代遍历队列
        cout << each << ends;
    cout << endl;

    deque<int>::iterator itr; // 声明队列正向迭代器
    for (itr = dq.begin(); itr != dq.end(); itr++) // 正向遍历队列
        cout << *itr << ends;
    cout << endl;

    deque<int>::reverse_iterator ritr; // 声明队列逆向迭代器
    for (ritr = dq.rbegin(); ritr != dq.rend(); ritr++) // 逆向遍历队列
        cout << *ritr << ends;
    cout << endl;

    cout << dq[0] << endl;

    dq.clear(); // 清空队列

    return 0;
}