这篇文章主要介绍“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)。