stack/queue中的deque-北京尧图网络

目录摘要一stack和queue叫适配器的原因二stack和queue的写法固定的原因1stack实现代码2queue实现代码3写法固定的原因三deque的优缺点1deque的优点2deque的结构3deqeu的缺点四deque和vector的排序速度五总结deque摘要本博客围绕STL库中的stack和queue进行讲解为什么二者不是容器类而是适配器为什么二者模拟实现时代码是写死的不能改变为什么二者底层默认的容器是deque可以随意切换吗deque没有缺点吗一stack和queue叫适配器的原因四段话理解为什么stack和queue叫作容器适配器①在 STL 的官方分类中string、vector、list属于容器Container而stack与queue却被归类为容器适配器Container Adapter。这并非只有命名上区别而是二者在设计上的不同②如何理解适配器不妨回想数据结构中实现顺序表或链表时我们需要独立管理内存、处理增删改查但实现栈和队列时我们往往直接复用已写好的顺序表或链表仅对其操作接口加以限制——栈只允许在一端进出队列只允许一端入另一端出。STL 的设计者采用了完全相同的思路。③正因如此STL 并没有为stack和queue重新设计一套内存管理方案而是在其内部封装了一个底层容器对象默认是deque。stack和queue自身不存储任何数据所有数据的增删改查均由底层容器的成员函数代为完成它们只做一件事将底层容器的通用接口如push_back、pop_back包装成符合栈或队列语义的专用接口。④这便是适配器——不创造新能力只转换旧接口。这种设计既避免了代码冗余又赋予了使用者灵活切换底层容器的自由(如将vector或list作为stack的底层容器)因此stack与queue不是容器而是容器的皮肤它们依赖容器而存在却定义了容器在特定场景下的使用规则。理解了stack和queue叫作容器适配器的原因则需要注意以下几个点接口封装层面模拟实现stack和queue时类的成员函数直接调用底层封装容器的对应接口如push调用push_backpop调用pop_back。这些调用的逻辑意图是固定的维护 LIFO 或 FIFO 特性但具体调用的底层函数由模板参数所指定的容器类型决定。功能裁剪层面stack和queue不提供迭代器因为迭代器会暴露底层容器的内部元素破坏 LIFO/FIFO 的访问约束。对于默认成员函数我们大部分情况下是不用自己实现的因为底层容器自带默认成员函数底层可配层面STL 中stack和queue默认封装的是deque容器。但底层容器并非固定不变stack和queue的类模板中设计了专门的类型参数通常命名为Container并赋予其缺省值dequeT使用者可根据需求自由替换为vector或list。这种设计使得适配器在不改变外部接口的前提下获得了底层存储策略的灵活可配性。二stack和queue的写法固定的原因我们在实现satck和queue的时候非常简单代码是固定的1stack实现代码namespace cl //防止命名冲突 { templateclass T, class Container std::dequeT class stack { public: //元素入栈 void push(const T x) { _con.push_back(x); } //元素出栈 void pop() { _con.pop_back(); } //获取栈顶元素 T top() { return _con.back(); } const T top() const { return _con.back(); } //获取栈中有效元素个数 size_t size() const { return _con.size(); } //判断栈是否为空 bool empty() const { return _con.empty(); } //交换两个栈中的数据 void swap(stackT, Container st) { _con.swap(st._con); } private: Container _con; }; }2queue实现代码namespace cl //防止命名冲突 { templateclass T, class Container std::dequeT class queue { public: //队尾入队列 void push(const T x) { _con.push_back(x); } //队头出队列 void pop() { _con.pop_front(); } //获取队头元素 T front() { return _con.front(); } const T front() const { return _con.front(); } //获取队尾元素 T back() { return _con.back(); } const T back() const { return _con.back(); } //获取队列中有效元素个数 size_t size() const { return _con.size(); } //判断队列是否为空 bool empty() const { return _con.empty(); } //交换两个队列中的数据 void swap(queueT, Container q) { _con.swap(q._con); } private: Container _con; }; }3写法固定的原因如上所示我们在实现stack和queue时代码非常简单且形式固定。无论谁来写成员函数的命名和函数体内的调用都是一成不变的stack的push调用push_backpop调用pop_backtop调用backqueue的push调用push_backpop调用pop_frontfront调用front不是不能变而是不变是最好的。为什么因为这种固定的写法本质上是对底层容器提出了一套接口要求。以stack为例一个容器若想作为它的底层必须支持push_back()、pop_back()、back()三个操作。这意味着该容器必须具备尾部高效操作的能力——尾插 O(1)O(1)、尾删 O(1)O(1)、尾访问 O(1)O(1)。而这恰恰就是栈所需要的全部能力。栈的核心语义是后进先出所有操作都发生在同一端栈顶对应到底层就是尾部。所以这种固定写法精准匹配了栈的操作模式。❓️为什么容器支持了push_back()、pop_back()、back()三个操作。就意味着该容器具备尾部高效操作的能力这就是STL设计容器类时的智慧了STL 中的容器类只实现自己擅长且高效的操作。比如vector它实现了push_back和pop_back因为尾部增删对它来说是 O(1)O(1) 的拿手好戏但它不会实现push_front和pop_front因为头部增删需要挪动所有元素代价是 O(n)O(n)。STL 宁愿让你用insert和erase间接实现头插头删也不愿提供一个低效的接口来误导使用者。所以一个容器能否作为stack的底层取决于它是否在尾部操作上足够优秀。vector、deque、list都满足所以都可以。❗️所以实现代码不变其实是一种筛选机制筛选出符合效率的容器类但如果我们强行破坏这种固定写法呢比如非要让vector作为queue的底层——queue需要pop_front()而vector没有。我们就尝试用erase间接实现头删的确让代码跑起来了。但代价是什么原本queue的出队应该是 O(1)O(1) 的常数操作被你硬生生变成了 O(n)O(n) 的线性操作栈和队列的效率优势瞬间荡然无存。所以代码固定的本质是强制底层容器必须提供高效匹配的接口。这种约束保证了适配器始终运行在最优效率下也防止了使用者误用低效容器导致性能崩盘。这也正是 STL 将stack和queue设计为容器适配器而非独立容器的深层考量——复用容器的存储能力同时用固定的接口约束来保证语义和效率的双重正确性。适配的容器类stack 底层类可以是deque默认、vector、listqueue 底层类可以是deque默认、list标准库只推荐用 deque 和 list不推荐自定义容器——除非你自己保证复杂度❓️我理解了在写法固定情况下若一个容器类能适配stack或queue就能保证stack/queue的效率但是容器都有优缺点难道stack和queue就能避开底层适配的容器类的缺点了吗是的避开了stack只使用底层容器的尾部操作(push_back/pop_back)queue只使用头尾两端操作(push_back/pop_front)这意味着vector头插慢的缺点stack永远用不到所以这个缺点对stack而言不存在。list不支持随机访问的缺点stack和queue也永远用不到因为它们根本不支持下标访问。一句话总结适配器通过限制操作接口让使用者只能走“高效通道”从而天然避开了底层容器在其他方向上的性能短板。三deque的优缺点1deque的优点vector优点下标随机访问缺点中间,头部的插入删除效率低扩容有消耗异地需挪动空间有浪费list优点任意位置插入删除效率高扩容无消耗按需申请释放缺点不支持下标随机访问而dequedouble-ended queue双端队列就是综合了二者的优点的数据结构其是C STL 中的一个序列容器允许在两端头部和尾部以及随机访问的快速的插入和删除操作并且缓存命中率高于list这也是为什么stack和queue都默认使用它的原因2deque的结构那deqeu真的这么牛吗真的这么牛的话为什么数据结构不学呢直接淘汰vector和list只学deque不就好了当然不是世界上没有完美的东西所以deque的缺点也是极其严重的下面我们探究deque的底层结构deque 并不是真正连续的空间而是由一段段连续的小空间拼接而成的实际的 deque 类似于一个动态的二维数组其底层结构如下所示解释①双端队列底层是一个假想的连续空间实际是分段连续的所以缓存命中率虽然高于list但仍然低于vector②map是一个指针数组其每个元素指向一个数组当map满了也需要扩容为了维护其整体连续、以及随机访问的假象其重任落在了 deque 的迭代器身上。因此 deque 的迭代器设计就尤为复杂如下图所示解释①deque的迭代器类中有四个指针极其复杂②cur指向当前遍历到的元素first指向当前buffer的起始地址last指向当前buffer的末尾元素地址而node指向map的一个元素③而map的元素是指针类型所以node就是一个二级指针类型源码中可见迭代器类的四个指针变量如下可见node就是一个二级指针类型所以deque的底层结构总的如下解释❓️如何随机访问[ ]呢每个buffer都是定长的所以根据索引的下标进行取余取模运算就知道是第几个buffer的第几个元素但是这里的除法/取模运算会带来一定开销所以仍然不及vector的效率❓️如何插入删除呢头插则新开辟一个buffer尾插有空间直接放没空间也要扩容开辟新的buffer最难崩的就是中间插入这意味着我们要挪动多个buffer内的数据且涉及多个 buffer 的跨块移动消耗巨大而删除中间数据也要挪动数据消耗同样巨大❓️插入删除不能原地进行吗也就是原地扩容缩容不用移动其他buffer的数据了进行原地扩容缩容这就意味着每个buffer的大小不一致的那取模取余实现随机访问不存在了随机访问的公式立刻失效退化为链表式的低效率顺序遍历。❓️头插是要开辟新的buffer的那现在假设第一个buffer只有头插的那一个数据那现在怎么进行随机访问[ ]呢所以deque不是直接用下标对buffer_size取模而是先减去第一个 buffer 的起始偏移再做除法。3deqeu的缺点所以缺点如下① 中间插入/删除极慢在deque中间插入或删除元素需要挪动插入点之后或之前的大量数据且这些数据可能横跨多个非连续的 buffer涉及跨块复制效率远低于vector的整块内存移动复杂度为 O(n)O(n) 且常数因子较大。② 随机访问的常数因子较大相比vector的“基址偏移”一次寻址deque的随机访问需要先除法取模定位 buffer再通过中控数组二次寻址。除法指令本身较慢频繁随机访问时性能不如vector。③ 内存不连续遍历时缓存不友好虽然各 buffer 内部是连续的但 buffer 之间在物理地址上并不相邻。遍历deque时跨越 buffer 边界会导致 CPU 缓存失效cache miss迭代速度慢于连续内存的vector。④ 额外的空间开销中控数组本身需要额外存储指针。当存储的元素较小时如int中控数组的开销占比会变得显著不如vector紧凑。需要明白的是deque 是一个专为头尾操作优化的选手在需要双端高频增删且偶尔随机访问的场景下表现优异但其中间插入删除的低效和遍历时的缓存不友好决定了它不适合频繁中间插入或大量遍历的场合。理解这些取舍才能在不同场景下做出正确的容器选择。而我们的stack和list不就只是单纯的需要头尾的插入删除吗这也是为什么选择deqeu的原因依旧是恰好避开了deque的缺点四deque和vector的排序速度两个代码体现deque的效率低下test_op1()直接对比vector和deque的排序效率在完全相同的随机数据集上分别对vector和deque进行排序对比二者的耗时差异。test_op2()验证拷贝后排序策略是否有效既然deque排序慢那先把deque的数据拷贝到vector排完序再拷回来总耗时会不会比直接在deque上排序更快#include iostream #include vector #include deque #include algorithm #include ctime #include cstdlib #include cstdio using namespace std; void test_op1() { srand((unsigned int)time(nullptr)); const int N 1000000; dequeint dq; vectorint v; // 预留空间避免 vector 频繁扩容影响测试结果 v.reserve(N); for (int i 0; i N; i) { auto e rand() i; v.push_back(e); dq.push_back(e); } int begin1 clock(); sort(v.begin(), v.end()); int end1 clock(); int begin2 clock(); sort(dq.begin(), dq.end()); int end2 clock(); printf(vector sort time: %d ms\n, end1 - begin1); printf(deque sort time: %d ms\n, end2 - begin2); printf(性能差距: %.2f 倍\n, (double)(end2 - begin2) / (end1 - begin1)); } void test_op2() { srand((unsigned int)time(nullptr)); const int N 1000000; dequeint dq1; dequeint dq2; for (int i 0; i N; i) { auto e rand() i; dq1.push_back(e); dq2.push_back(e); } int begin1 clock(); sort(dq1.begin(), dq1.end()); int end1 clock(); int begin2 clock(); // 拷贝到 vector 排序再拷回 deque vectorint v(dq2.begin(), dq2.end()); sort(v.begin(), v.end()); dq2.assign(v.begin(), v.end()); int end2 clock(); printf(直接在 deque 上排序: %d ms\n, end1 - begin1); printf(拷贝到 vector 排序后拷回: %d ms\n, end2 - begin2); printf(性能差距: %.2f 倍\n, (double)(end1 - begin1) / (end2 - begin2)); } int main() { printf( test_op1: vector vs deque 排序 \n); test_op1(); printf(\n test_op2: deque 直接排序 vs 拷贝后排序 \n); test_op2(); return 0; }导致排序慢的原因就是deque的缺点所致五总结deque维度具体表现底层原因对标容器头尾插入/删除✅ 效率极高均为 O(1)O(1)中控数组定长 buffer头尾操作无需移动任何元素优于vector头插慢与list持平随机访问✅ 支持 O(1)O(1) 下标访问通过除法/取模定位 buffer 中控数组二次寻址弱于vector一次寻址强于list不支持扩容代价✅ 低近似 O(1)O(1)仅需在中控数组中新增指针已有元素不动优于vector需拷贝/移动所有元素内存利用率✅ 按需分配空间浪费少按需开辟 buffer无需预留大量闲置空间优于vector可能预分配过多缓存命中率⚠️ 中等buffer 内部连续但跨 buffer 跳跃导致 cache miss优于list完全离散弱于vector完全连续中间插入/删除❌ 极慢O(n)O(n) 且常数因子大需跨多个 buffer 挪动数据涉及跨块复制弱于listO(1)O(1)弱于vector单块内存移动遍历效率⚠️ 一般buffer 边界处缓存失效弱于vector强于list空间开销⚠️ 额外开销中控数组存储指针小元素时占比显著弱于vector更紧凑优于list每个节点两个指针deque是一个专为头尾操作优化的全能型选手它综合了vector的随机访问能力和list的头尾高效增删能力但在中间操作和纯遍历场景下均不如vector。正因stack和queue只涉及头尾操作完美避开deque的短板所以deque成为它们的默认底层容器。 [ 作者 ] shylyly [ 首次发布 ] 2026.9.2❌ [ 最新修改 ] 2026.10.3 [ 声明 ] 由于笔者水平有限文中难免有疏漏或不妥之处还望读者不吝赐教

stack/queue中的deque

相关推荐

Trae安装后连不上模型？把Base URL改到TaoToken的排查清单

Python环境变量配置全攻略：从PATH原理到虚拟环境实战

C语言：系统开发的基石与现代编程的起点

更多资讯

Go GC 三色标记详解：从 Pacing 算法到 GOGC 调优

哈工大版《理论力学》课后习题答案使用指南：七章考点、避坑与自测

Sheets公式完全指南：SUM/AVG/MIN/MAX五件套与循环引用检测原理

插件系统原理与加载失败排查：从IAR、MusicFree到web boot实战

Windows 上 ESP32-C3 开发环境搭建与 LED 点灯实战

网页视频怎么下载：猫抓资源嗅探新手实用指南

今日更新

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？