在 C STL 中deque是一个非常重要的顺序容器。它的全称是double-ended queue中文通常翻译为双端队列。所谓“双端”指的是它可以在容器的头部和尾部都进行高效的插入和删除操作。相比vector、queue、list等容器deque的使用场景更加灵活尤其适合处理滑动窗口、单调队列、广度优先搜索等问题。一、什么是 dequedeque是 C 标准模板库 STL 提供的一种容器定义在头文件#include deque它可以像数组一样存储一组连续逻辑上的元素也可以像队列一样在两端进行操作。定义一个dequedequeint dq;这个dq表示一个存储int类型数据的双端队列。deque的最大特点是可以在队头插入元素 可以在队尾插入元素 可以从队头删除元素 可以从队尾删除元素也就是说deque既不像普通队列那样只能一端进、一端出也不像vector那样主要适合在尾部操作。二、deque 的基本特点deque主要有以下几个特点第一支持随机访问。cout dq[0] endl; cout dq[1] endl;这点和vector类似。第二支持头尾高效插入和删除。dq.push_front(10); dq.push_back(20); dq.pop_front(); dq.pop_back();第三不适合在中间频繁插入和删除。虽然deque支持在中间插入元素但效率通常不如list。第四空间结构不是完全连续的。vector底层通常是一整块连续内存而deque底层一般是由多段连续内存组成。因此deque的随机访问效率略低于vector但它在头部插入和删除方面比vector更有优势。三、deque 的常用操作下面介绍deque最常用的几个成员函数。1. push_back尾部插入元素dq.push_back(10); dq.push_back(20); dq.push_back(30);此时队列内容为10 20 30push_back表示从队尾加入元素。2. push_front头部插入元素dq.push_front(5);如果原来队列是10 20 30插入后变成5 10 20 30这就是deque相比vector的优势之一。vector如果在头部插入元素后面的元素通常都要整体后移效率较低。而deque在头部插入元素效率较高。3. pop_back删除尾部元素dq.pop_back();如果队列原来是5 10 20 30执行后变成5 10 20注意pop_back()只删除元素不返回被删除的值。如果想先获取尾部元素再删除需要这样写int x dq.back(); dq.pop_back();4. pop_front删除头部元素dq.pop_front();如果队列原来是5 10 20执行后变成10 20同样pop_front()只删除元素不返回元素值。如果需要获取队头元素int x dq.front(); dq.pop_front();5. front访问队头元素cout dq.front() endl;front()用来访问队列最前面的元素。例如dequeint dq; dq.push_back(10); dq.push_back(20); dq.push_back(30); cout dq.front() endl;输出106. back访问队尾元素cout dq.back() endl;例如dequeint dq; dq.push_back(10); dq.push_back(20); dq.push_back(30); cout dq.back() endl;输出307. empty判断是否为空if (dq.empty()) { cout deque 为空 endl; }在使用front()、back()、pop_front()、pop_back()之前最好先判断队列是否为空。错误写法dequeint dq; cout dq.front() endl;如果dq是空的直接访问front()会导致未定义行为。正确写法if (!dq.empty()) { cout dq.front() endl; }8. size获取元素个数cout dq.size() endl;例如dequeint dq; dq.push_back(1); dq.push_back(2); dq.push_back(3); cout dq.size() endl;输出39. clear清空 dequedq.clear();清空后dq.size() 0 dq.empty() true10. 使用下标访问元素deque支持像数组一样通过下标访问元素dequeint dq {10, 20, 30, 40}; cout dq[0] endl; cout dq[2] endl;输出10 30不过要注意下标不能越界。例如cout dq[100] endl;这是错误的。四、deque 的完整基础示例#include iostream #include deque using namespace std; int main() { dequeint dq; dq.push_back(10); dq.push_back(20); dq.push_back(30); dq.push_front(5); dq.push_front(1); cout 当前 deque 中的元素 endl; for (int i 0; i dq.size(); i) { cout dq[i] ; } cout endl; cout 队头元素 dq.front() endl; cout 队尾元素 dq.back() endl; dq.pop_front(); dq.pop_back(); cout 删除队头和队尾之后 endl; for (int x : dq) { cout x ; } cout endl; return 0; }运行结果当前 deque 中的元素 1 5 10 20 30 队头元素1 队尾元素30 删除队头和队尾之后 5 10 20五、deque 和 vector 的区别vector和deque都属于顺序容器都可以用下标访问元素。但是它们的使用场景不同。1. vector 的特点vector适合尾部插入 随机访问 数据连续存储例如vectorint v; v.push_back(10); v.push_back(20);vector在尾部插入效率很高但是在头部插入和删除效率较低。比如v.erase(v.begin());这个操作会导致后面的元素整体向前移动。2. deque 的特点deque适合头部插入 尾部插入 头部删除 尾部删除 随机访问例如dequeint dq; dq.push_front(10); dq.push_back(20); dq.pop_front(); dq.pop_back();如果程序中需要频繁操作容器两端那么deque通常比vector更合适。3. vector 和 deque 对比表对比项vectordeque头部插入慢快尾部插入快快头部删除慢快尾部删除快快随机访问快较快内存连续性完全连续分段连续适合场景动态数组双端队列、滑动窗口六、deque 和 queue 的区别queue是普通队列遵循先进先出原则。queueint q; q.push(10); q.push(20); q.pop();queue只能从队尾插入从队头删除。但是deque可以从两端插入和删除dequeint dq; dq.push_front(10); dq.push_back(20); dq.pop_front(); dq.pop_back();所以deque比queue更灵活。实际上在 C STL 中queue默认底层容器就是deque。也就是说普通队列queue很多时候是基于deque实现的。七、deque 的时间复杂度deque常见操作的时间复杂度如下操作时间复杂度push_back()O(1)push_front()O(1)pop_back()O(1)pop_front()O(1)front()O(1)back()O(1)operator[]O(1)中间插入O(n)中间删除O(n)从这个表可以看出deque最擅长的就是两端操作。但是如果经常在中间插入或删除元素deque并不是最好的选择。八、deque 的底层原理简单理解从逻辑上看deque像是一个可以从两端扩展的数组。但是从底层实现上看deque通常不是一整块连续内存而是由多个小块连续内存组成。可以简单理解为deque 多个小数组拼接起来例如[块1] [块2] [块3] [块4]每个块内部是连续的但是整个deque不一定是完全连续的。这样设计的好处是头部扩展方便 尾部扩展方便 不需要像 vector 那样频繁整体搬迁数据这也是为什么deque可以高效地在头部和尾部插入、删除元素。但是因为它不是完全连续内存所以在访问速度和缓存友好性方面通常不如vector。九、deque 的典型应用场景1. 普通双端队列当我们需要两端都可以进出时可以使用deque。例如dequeint dq; dq.push_back(1); dq.push_back(2); dq.push_front(0); dq.pop_front(); dq.pop_back();2. 滑动窗口最大值这是deque最经典的算法应用。题目要求给定一个数组nums和窗口大小k窗口每次向右移动一位求每个窗口中的最大值。例如nums [1, 3, -1, -3, 5, 3, 6, 7] k 3窗口变化[1, 3, -1] 最大值 3 [3, -1, -3] 最大值 3 [-1, -3, 5] 最大值 5 [-3, 5, 3] 最大值 5 [5, 3, 6] 最大值 6 [3, 6, 7] 最大值 7结果[3, 3, 5, 5, 6, 7]这个问题可以用deque维护一个单调递减队列。十、结合滑动窗口理解 deque下面是滑动窗口最大值的核心代码class Solution { public: vectorint maxSlidingWindow(vectorint nums, int k) { vectorint result; dequeint dq; for (int i 0; i nums.size(); i) { while (!dq.empty() dq.front() i - k 1) { dq.pop_front(); } while (!dq.empty() nums[dq.back()] nums[i]) { dq.pop_back(); } dq.push_back(i); if (i k - 1) { result.push_back(nums[dq.front()]); } } return result; } };这段代码中dequeint dq;保存的不是元素值而是元素下标。也就是说dq里面存的是0, 1, 2, 3 ...而不是nums[0], nums[1], nums[2] ...为什么要存下标因为下标可以判断元素是否已经离开窗口。例如当前窗口范围是[i - k 1, i]如果队头下标小于窗口左边界dq.front() i - k 1说明这个元素已经不在窗口中了需要删除dq.pop_front();十一、单调队列思想在滑动窗口最大值中deque维护的是一个单调递减队列。也就是说队列中下标对应的元素值满足nums[dq[0]] nums[dq[1]] nums[dq[2]]这样一来队头元素永远是当前窗口中的最大值。例如nums [1, 3, -1]处理完这个窗口后队列中可能保存dq [1, 2]对应的值是nums[1] 3 nums[2] -1由于3在队头所以当前窗口最大值就是nums[dq.front()] 3十二、为什么要从队尾删除较小元素看这段代码while (!dq.empty() nums[dq.back()] nums[i]) { dq.pop_back(); }含义是如果当前元素nums[i]比队尾元素大那么队尾元素以后不可能再成为最大值。原因有两个第一当前元素比它大。第二当前元素比它更靠右会更晚离开窗口。所以队尾这个较小元素已经没有价值可以直接删除。例如nums [1, 3]当遍历到3的时候前面的1就没有必要保留。因为只要3还在窗口中1永远不可能是最大值。十三、为什么时间复杂度是 O(n)虽然代码中有while循环while (!dq.empty() dq.front() i - k 1) { dq.pop_front(); } while (!dq.empty() nums[dq.back()] nums[i]) { dq.pop_back(); }但是每个元素最多只会入队一次 出队一次一个下标进入deque后之后要么从队头弹出要么从队尾弹出不会反复进出。所以总时间复杂度是O(n)空间复杂度是O(k)因为队列中保存的是当前窗口附近的元素下标。十四、deque 的优点deque的主要优点包括第一头尾操作效率高。push_front() push_back() pop_front() pop_back()这些操作通常都是 O(1)。第二支持随机访问。dq[i]第三比queue更灵活。queue只能队尾进、队头出而deque两端都可以进出。第四适合实现单调队列。在滑动窗口问题中deque是非常常用的容器。十五、deque 的缺点deque也不是万能的。它有几个缺点第一缓存性能通常不如vector。因为vector是连续内存而deque是分段连续内存。第二中间插入和删除效率不高。例如dq.insert(dq.begin() 2, 100); dq.erase(dq.begin() 3);这类操作可能需要移动元素时间复杂度通常是 O(n)。第三使用上比vector稍微复杂。尤其是在算法题中deque经常和下标、窗口边界、单调性结合使用对初学者来说需要多练习。十六、deque 适合什么时候使用如果你的程序需要频繁在两端进行插入和删除操作优先考虑deque。适合使用deque的情况需要从队头删除元素 需要从队尾删除元素 需要从队头插入元素 需要从队尾插入元素 需要维护滑动窗口 需要维护单调队列不太适合使用deque的情况只需要尾部插入和随机访问 需要极高的遍历效率 需要连续内存 需要频繁在中间插入和删除如果只是在尾部插入、遍历和随机访问一般vector更合适。如果需要频繁在中间插入和删除一般list更合适。如果需要普通先进先出队列可以使用queue。如果需要两端操作就使用deque。十七、常见易错点1. 空队列不能直接访问 front 和 back错误写法dequeint dq; cout dq.front() endl;正确写法if (!dq.empty()) { cout dq.front() endl; }2. pop_front 和 pop_back 不返回元素错误理解int x dq.pop_front();这是错误的。正确写法int x dq.front(); dq.pop_front();3. 下标访问不能越界错误写法cout dq[100] endl;如果dq没有这么多元素会发生错误。4. 滑动窗口中通常存下标不是存值在滑动窗口最大值中建议存下标dequeint dq;因为下标可以判断元素是否过期。如果只存值很难判断某个值是否已经离开窗口。十八、总结deque是 C STL 中非常重要的容器它的核心特点是可以在头部和尾部高效插入、删除元素 支持随机访问 适合实现双端队列和单调队列与vector相比deque的头部操作更高效。与queue相比deque的操作更加灵活。在算法题中deque最经典的应用就是滑动窗口最大值。通过维护一个单调递减队列可以把原本 O(n * k) 的暴力算法优化为 O(n)。可以用一句话概括dequedeque 是一种既像数组、又像队列的 STL 容器它兼具随机访问能力和双端高效操作能力特别适合处理滑动窗口、单调队列等问题。
C++ STL 双端队列 deque 详细介绍
在 C STL 中deque是一个非常重要的顺序容器。它的全称是double-ended queue中文通常翻译为双端队列。所谓“双端”指的是它可以在容器的头部和尾部都进行高效的插入和删除操作。相比vector、queue、list等容器deque的使用场景更加灵活尤其适合处理滑动窗口、单调队列、广度优先搜索等问题。一、什么是 dequedeque是 C 标准模板库 STL 提供的一种容器定义在头文件#include deque它可以像数组一样存储一组连续逻辑上的元素也可以像队列一样在两端进行操作。定义一个dequedequeint dq;这个dq表示一个存储int类型数据的双端队列。deque的最大特点是可以在队头插入元素 可以在队尾插入元素 可以从队头删除元素 可以从队尾删除元素也就是说deque既不像普通队列那样只能一端进、一端出也不像vector那样主要适合在尾部操作。二、deque 的基本特点deque主要有以下几个特点第一支持随机访问。cout dq[0] endl; cout dq[1] endl;这点和vector类似。第二支持头尾高效插入和删除。dq.push_front(10); dq.push_back(20); dq.pop_front(); dq.pop_back();第三不适合在中间频繁插入和删除。虽然deque支持在中间插入元素但效率通常不如list。第四空间结构不是完全连续的。vector底层通常是一整块连续内存而deque底层一般是由多段连续内存组成。因此deque的随机访问效率略低于vector但它在头部插入和删除方面比vector更有优势。三、deque 的常用操作下面介绍deque最常用的几个成员函数。1. push_back尾部插入元素dq.push_back(10); dq.push_back(20); dq.push_back(30);此时队列内容为10 20 30push_back表示从队尾加入元素。2. push_front头部插入元素dq.push_front(5);如果原来队列是10 20 30插入后变成5 10 20 30这就是deque相比vector的优势之一。vector如果在头部插入元素后面的元素通常都要整体后移效率较低。而deque在头部插入元素效率较高。3. pop_back删除尾部元素dq.pop_back();如果队列原来是5 10 20 30执行后变成5 10 20注意pop_back()只删除元素不返回被删除的值。如果想先获取尾部元素再删除需要这样写int x dq.back(); dq.pop_back();4. pop_front删除头部元素dq.pop_front();如果队列原来是5 10 20执行后变成10 20同样pop_front()只删除元素不返回元素值。如果需要获取队头元素int x dq.front(); dq.pop_front();5. front访问队头元素cout dq.front() endl;front()用来访问队列最前面的元素。例如dequeint dq; dq.push_back(10); dq.push_back(20); dq.push_back(30); cout dq.front() endl;输出106. back访问队尾元素cout dq.back() endl;例如dequeint dq; dq.push_back(10); dq.push_back(20); dq.push_back(30); cout dq.back() endl;输出307. empty判断是否为空if (dq.empty()) { cout deque 为空 endl; }在使用front()、back()、pop_front()、pop_back()之前最好先判断队列是否为空。错误写法dequeint dq; cout dq.front() endl;如果dq是空的直接访问front()会导致未定义行为。正确写法if (!dq.empty()) { cout dq.front() endl; }8. size获取元素个数cout dq.size() endl;例如dequeint dq; dq.push_back(1); dq.push_back(2); dq.push_back(3); cout dq.size() endl;输出39. clear清空 dequedq.clear();清空后dq.size() 0 dq.empty() true10. 使用下标访问元素deque支持像数组一样通过下标访问元素dequeint dq {10, 20, 30, 40}; cout dq[0] endl; cout dq[2] endl;输出10 30不过要注意下标不能越界。例如cout dq[100] endl;这是错误的。四、deque 的完整基础示例#include iostream #include deque using namespace std; int main() { dequeint dq; dq.push_back(10); dq.push_back(20); dq.push_back(30); dq.push_front(5); dq.push_front(1); cout 当前 deque 中的元素 endl; for (int i 0; i dq.size(); i) { cout dq[i] ; } cout endl; cout 队头元素 dq.front() endl; cout 队尾元素 dq.back() endl; dq.pop_front(); dq.pop_back(); cout 删除队头和队尾之后 endl; for (int x : dq) { cout x ; } cout endl; return 0; }运行结果当前 deque 中的元素 1 5 10 20 30 队头元素1 队尾元素30 删除队头和队尾之后 5 10 20五、deque 和 vector 的区别vector和deque都属于顺序容器都可以用下标访问元素。但是它们的使用场景不同。1. vector 的特点vector适合尾部插入 随机访问 数据连续存储例如vectorint v; v.push_back(10); v.push_back(20);vector在尾部插入效率很高但是在头部插入和删除效率较低。比如v.erase(v.begin());这个操作会导致后面的元素整体向前移动。2. deque 的特点deque适合头部插入 尾部插入 头部删除 尾部删除 随机访问例如dequeint dq; dq.push_front(10); dq.push_back(20); dq.pop_front(); dq.pop_back();如果程序中需要频繁操作容器两端那么deque通常比vector更合适。3. vector 和 deque 对比表对比项vectordeque头部插入慢快尾部插入快快头部删除慢快尾部删除快快随机访问快较快内存连续性完全连续分段连续适合场景动态数组双端队列、滑动窗口六、deque 和 queue 的区别queue是普通队列遵循先进先出原则。queueint q; q.push(10); q.push(20); q.pop();queue只能从队尾插入从队头删除。但是deque可以从两端插入和删除dequeint dq; dq.push_front(10); dq.push_back(20); dq.pop_front(); dq.pop_back();所以deque比queue更灵活。实际上在 C STL 中queue默认底层容器就是deque。也就是说普通队列queue很多时候是基于deque实现的。七、deque 的时间复杂度deque常见操作的时间复杂度如下操作时间复杂度push_back()O(1)push_front()O(1)pop_back()O(1)pop_front()O(1)front()O(1)back()O(1)operator[]O(1)中间插入O(n)中间删除O(n)从这个表可以看出deque最擅长的就是两端操作。但是如果经常在中间插入或删除元素deque并不是最好的选择。八、deque 的底层原理简单理解从逻辑上看deque像是一个可以从两端扩展的数组。但是从底层实现上看deque通常不是一整块连续内存而是由多个小块连续内存组成。可以简单理解为deque 多个小数组拼接起来例如[块1] [块2] [块3] [块4]每个块内部是连续的但是整个deque不一定是完全连续的。这样设计的好处是头部扩展方便 尾部扩展方便 不需要像 vector 那样频繁整体搬迁数据这也是为什么deque可以高效地在头部和尾部插入、删除元素。但是因为它不是完全连续内存所以在访问速度和缓存友好性方面通常不如vector。九、deque 的典型应用场景1. 普通双端队列当我们需要两端都可以进出时可以使用deque。例如dequeint dq; dq.push_back(1); dq.push_back(2); dq.push_front(0); dq.pop_front(); dq.pop_back();2. 滑动窗口最大值这是deque最经典的算法应用。题目要求给定一个数组nums和窗口大小k窗口每次向右移动一位求每个窗口中的最大值。例如nums [1, 3, -1, -3, 5, 3, 6, 7] k 3窗口变化[1, 3, -1] 最大值 3 [3, -1, -3] 最大值 3 [-1, -3, 5] 最大值 5 [-3, 5, 3] 最大值 5 [5, 3, 6] 最大值 6 [3, 6, 7] 最大值 7结果[3, 3, 5, 5, 6, 7]这个问题可以用deque维护一个单调递减队列。十、结合滑动窗口理解 deque下面是滑动窗口最大值的核心代码class Solution { public: vectorint maxSlidingWindow(vectorint nums, int k) { vectorint result; dequeint dq; for (int i 0; i nums.size(); i) { while (!dq.empty() dq.front() i - k 1) { dq.pop_front(); } while (!dq.empty() nums[dq.back()] nums[i]) { dq.pop_back(); } dq.push_back(i); if (i k - 1) { result.push_back(nums[dq.front()]); } } return result; } };这段代码中dequeint dq;保存的不是元素值而是元素下标。也就是说dq里面存的是0, 1, 2, 3 ...而不是nums[0], nums[1], nums[2] ...为什么要存下标因为下标可以判断元素是否已经离开窗口。例如当前窗口范围是[i - k 1, i]如果队头下标小于窗口左边界dq.front() i - k 1说明这个元素已经不在窗口中了需要删除dq.pop_front();十一、单调队列思想在滑动窗口最大值中deque维护的是一个单调递减队列。也就是说队列中下标对应的元素值满足nums[dq[0]] nums[dq[1]] nums[dq[2]]这样一来队头元素永远是当前窗口中的最大值。例如nums [1, 3, -1]处理完这个窗口后队列中可能保存dq [1, 2]对应的值是nums[1] 3 nums[2] -1由于3在队头所以当前窗口最大值就是nums[dq.front()] 3十二、为什么要从队尾删除较小元素看这段代码while (!dq.empty() nums[dq.back()] nums[i]) { dq.pop_back(); }含义是如果当前元素nums[i]比队尾元素大那么队尾元素以后不可能再成为最大值。原因有两个第一当前元素比它大。第二当前元素比它更靠右会更晚离开窗口。所以队尾这个较小元素已经没有价值可以直接删除。例如nums [1, 3]当遍历到3的时候前面的1就没有必要保留。因为只要3还在窗口中1永远不可能是最大值。十三、为什么时间复杂度是 O(n)虽然代码中有while循环while (!dq.empty() dq.front() i - k 1) { dq.pop_front(); } while (!dq.empty() nums[dq.back()] nums[i]) { dq.pop_back(); }但是每个元素最多只会入队一次 出队一次一个下标进入deque后之后要么从队头弹出要么从队尾弹出不会反复进出。所以总时间复杂度是O(n)空间复杂度是O(k)因为队列中保存的是当前窗口附近的元素下标。十四、deque 的优点deque的主要优点包括第一头尾操作效率高。push_front() push_back() pop_front() pop_back()这些操作通常都是 O(1)。第二支持随机访问。dq[i]第三比queue更灵活。queue只能队尾进、队头出而deque两端都可以进出。第四适合实现单调队列。在滑动窗口问题中deque是非常常用的容器。十五、deque 的缺点deque也不是万能的。它有几个缺点第一缓存性能通常不如vector。因为vector是连续内存而deque是分段连续内存。第二中间插入和删除效率不高。例如dq.insert(dq.begin() 2, 100); dq.erase(dq.begin() 3);这类操作可能需要移动元素时间复杂度通常是 O(n)。第三使用上比vector稍微复杂。尤其是在算法题中deque经常和下标、窗口边界、单调性结合使用对初学者来说需要多练习。十六、deque 适合什么时候使用如果你的程序需要频繁在两端进行插入和删除操作优先考虑deque。适合使用deque的情况需要从队头删除元素 需要从队尾删除元素 需要从队头插入元素 需要从队尾插入元素 需要维护滑动窗口 需要维护单调队列不太适合使用deque的情况只需要尾部插入和随机访问 需要极高的遍历效率 需要连续内存 需要频繁在中间插入和删除如果只是在尾部插入、遍历和随机访问一般vector更合适。如果需要频繁在中间插入和删除一般list更合适。如果需要普通先进先出队列可以使用queue。如果需要两端操作就使用deque。十七、常见易错点1. 空队列不能直接访问 front 和 back错误写法dequeint dq; cout dq.front() endl;正确写法if (!dq.empty()) { cout dq.front() endl; }2. pop_front 和 pop_back 不返回元素错误理解int x dq.pop_front();这是错误的。正确写法int x dq.front(); dq.pop_front();3. 下标访问不能越界错误写法cout dq[100] endl;如果dq没有这么多元素会发生错误。4. 滑动窗口中通常存下标不是存值在滑动窗口最大值中建议存下标dequeint dq;因为下标可以判断元素是否过期。如果只存值很难判断某个值是否已经离开窗口。十八、总结deque是 C STL 中非常重要的容器它的核心特点是可以在头部和尾部高效插入、删除元素 支持随机访问 适合实现双端队列和单调队列与vector相比deque的头部操作更高效。与queue相比deque的操作更加灵活。在算法题中deque最经典的应用就是滑动窗口最大值。通过维护一个单调递减队列可以把原本 O(n * k) 的暴力算法优化为 O(n)。可以用一句话概括dequedeque 是一种既像数组、又像队列的 STL 容器它兼具随机访问能力和双端高效操作能力特别适合处理滑动窗口、单调队列等问题。
