C++中的deque怎么使用

这篇文章主要介绍“C++中的deque怎么使用”的相关知识，小编通过实际案例向大家展示操作过程，操作方法简单快捷，实用性强，希望这篇“C++中的deque怎么使用”文章能帮助大家解决问题。

1）deque的定义及基本用法

要使用deque，我们需要包含头文件，定义deque对象如下：

#include <deque>
using namespace std;
deque<int> dq; // 定义deque对象dq，其中元素类型为int型

deque支持的基本操作如下：

• 在deque的队首插入元素：push_front()方法。

• 在deque的队尾插入元素：push_back()方法。

• 删除deque队首的元素：pop_front()方法。

• 删除deque队尾的元素：pop_back()方法。

• deque的长度：size()方法。

• 判断deque是否为空：empty()方法。

• 访问deque队首元素：front()方法。

• 访问deque队尾元素：back()方法。

示例代码如下：

#include <iostream>
#include <deque>

using namespace std;

int main()
{
    deque<int> dq;
    dq.push_front(1);   // 在队首插入元素1
    dq.push_back(2);    // 在队尾插入元素2
    dq.push_front(3);   // 在队首插入元素3
    dq.pop_back();      // 删除队尾元素2
    cout << "长度：" << dq.size() << endl;      // 打印长度
    while(!dq.empty()){
        cout << dq.front() << ' ';     // 打印队列中的每一个元素
        dq.pop_front();     // 删除队首元素
    }
    return 0;
}

执行结果：

长度：2
3 1

2）deque的迭代器

deque支持迭代器，可以按照指针的方式遍历deque中的所有元素。deque迭代器支持前向访问，但不支持随机访问，即不支持下标操作。deque迭代器又分为普通迭代器和反向迭代器，可以分别用begin()，end()，rbegin()，rend()方法来获取。

示例代码如下：

#include <iostream>
#include <deque>

using namespace std;

int main()
{
    deque<int> dq;
    dq.push_front(1);
    dq.push_back(2);
    dq.push_back(3);
    dq.push_front(4);
    cout << "正向遍历：";
    for(deque<int>::iterator it=dq.begin();it!=dq.end();it++)
        cout << *it << ' ';    // 打印所有元素
    cout << endl;
    cout << "反向遍历：";
    for(deque<int>::reverse_iterator it=dq.rbegin();it!=dq.rend();it++)
        cout << *it << ' ';    // 打印所有元素（反向）
    cout << endl;
    return 0;
}

执行结果：

正向遍历：4 1 2 3 
反向遍历：3 2 1 4 

3）deque的性能

对于在最差情况下，即内存池容量已满的情况，deque在表现上比较优，它的时间复杂度为O(1)，因为deque在前端和后端进行插入和删除的操作所需时间复杂度为O(1)，但如果在中间进行插入和删除，则时间复杂度为O(N)，因为因为需要把后面的元素往后移动。同时，它的空间复杂度为O(N)，其中N表示deque中元素的个数。

4）deque的应用：滑动窗口问题

滑动窗口问题是指在一个序列中找出所有长度为k的子序列，并且每次移动一个单位，重复执行这个操作，最终得到所有的子序列。这个问题在处理字符串问题，尤其是搜索问题中经常出现。我们可以用deque来解决这个问题，将待处理的数据元素存入到deque中，每次向右滑动窗口的时候从左边移除最先加入的元素，同时从右边添加一个新的元素。

示例代码如下：

#include <iostream>
#include <deque>

using namespace std;

void printMax(int arr[], int n, int k)
{
    deque<int> dq; // 存储元素下标，用于判断窗口是否失效，同时也维护了单调性
    for (int i=0; i<k; i++) {
        while (!dq.empty() && arr[i] >= arr[dq.back()])
            dq.pop_back();  // 维护单调性，删除队列中元素使其单调递增
        dq.push_back(i);    // 将元素下标存入队列
    }
    for (int i=k; i<n; i++) {
        cout << arr[dq.front()] << " ";    // 打印当前窗口中的最大值
        while (!dq.empty() && dq.front() <= i-k)
            dq.pop_front(); // 删除队首元素，判断队首元素是否已失效
        while (!dq.empty() && arr[i] >= arr[dq.back()])
            dq.pop_back();  // 维护单调性，删除队列中元素使其单调递增
        dq.push_back(i);    // 将元素下标存入队列
    }
    cout << arr[dq.front()] << endl;    // 打印最后一个窗口中的最大值
}

int main()
{
    int arr[] = {4, 3, 5, 4, 2, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    printMax(arr, n, k);
    return 0;
}

此示例代码中，我们定义了一个deque用于存储元素下标，同时维护单调性，使得队列中的元素单调递增。在每次可取的滑动窗口过程中，只需找到队列中的最大值。这个示例中的时间复杂度为O(N)。

关于“C++中的deque怎么使用”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识，可以关注亿速云行业资讯频道，小编每天都会为大家更新不同的知识点。