在C编程中我们经常需要实现一些基础的数据结构。比如栈stack和队列queue明明已经有vector存数据了但它的接口根本不符合栈“后进先出”、队列“先进先出”的需求只能自己从头写push、pop、top这些接口一套下来光一个简单的栈就写了几十行代码重复造轮子的感觉太糟了。这时候会花不少时间从头开始写——定义结构、实现各种操作函数……结果一个简单的栈或队列代码就可能膨胀到几十甚至上百行。而 STL 适配器的出现正是为了把我们从这种“重复造轮子”的工作中解放出来。它就像一把精巧的转换器通过对现有容器进行封装用极少的代码就能实现特定的数据结构行为让编程变得更简洁、更高效。而STL适配器就是来解决这个问题的它就像个现成的“工具包”直接把vector、deque这些基础容器包装一下就能变成你需要的栈或队列几行代码就能搞定所有功能省下来的时间摸鱼不香吗一、什么是 STL 适配器1.1 适配器模式接口转换的核心思想其实适配器模式很好理解说白了就是个“接口转换器”。就像我们手机充电插座是220V交流电手机要的是5V直流电这时候电源适配器一插问题就解决了——既不用改插座也不用动手机。STL适配器也是一个道理。它把vector、deque这些基础容器“包起来”藏起里面复杂的实现细节只给你暴露栈、队列需要的接口。比如你想要个栈它就把deque的接口改成“后进先出”的样式你直接用push、pop、top就行根本不用管底层是怎么存数据的。1.2 三大适配器类型STL里的适配器主要分三类各自有不同的用处咱们简单过一遍容器适配器改造现有容器的接口让它变成特定数据结构。比如stack、queue、priority_queue都属于这个范畴默认都是用deque包装出来的用的时候就像用独立数据结构一样方便。迭代器适配器改变迭代器的遍历方向。比如reverse_iterator本来迭代器是从前往后走用它就能反过来遍历特别实用。函数适配器帮你调整函数的调用方式。比如std::bind能把函数和固定参数绑在一起生成新的调用对象后续用起来更灵活。今天咱们重点聊容器适配器就盯着stack和queue这两个最常用的扒一扒它们的底层逻辑看看怎么用最少的代码实现最强的功能。二、容器适配器详解2.1 栈stack后进先出的 “极简封装”2.1.1 接口与使用STL里的stack就是个容器适配器专门实现“后进先出”LIFO的逻辑。它的接口设计特别精简核心就5个记起来毫无压力push()压栈把元素放到栈顶。底层默认调用容器的push_back比如用deque当底层的话就是往deque末尾加元素相当于栈顶。pop()弹栈删掉栈顶元素。底层默认调用pop_back还是以deque为例就是删掉末尾的元素。top()取栈顶元素不会删掉它。底层对应容器的back()直接拿deque末尾的元素就行。empty()判断栈是不是空的空就返回true反之false。size()返回栈里有多少个元素一眼知道栈的大小。实际用起来特别简单给大家放个整数栈的示例代码一看就懂#include iostream #include stack int main() { std::stackint myStack; // 压栈操作 myStack.push(10); myStack.push(20); myStack.push(30); // 输出栈顶元素 std::cout 栈顶元素: myStack.top() std::endl; // 弹栈操作并输出弹出的元素 while (!myStack.empty()) { std::cout 弹出元素: myStack.top() std::endl; myStack.pop(); } return 0; }这段代码很直观先创建一个整数栈myStack用push把10、20、30依次压进去再用top取栈顶元素此时是30。最后用while循环只要栈不为空就先取栈顶元素输出再用pop弹栈直到栈空为止。2.1.2 底层实现与模拟其实STL的stack就是个模板类默认用deque当底层容器。为啥选deque因为它两端插入、删除都快时间复杂度都是O(1)刚好适配栈的操作需求。当然你也可以自己指定底层容器比如用vector或者list。但要注意选的容器必须支持stack需要的接口——比如stack要用push_back和pop_back所以vector能用但它扩容的时候会拷贝元素可能影响性能这点要留意。为了让大家更清楚底层逻辑我写了个简单的stack模拟实现大家可以看看#include iostream #include vector template typename T, typename Container std::vectorT class MyStack { private: Container c; // 底层容器 public: void push(const T x) { c.push_back(x); } void pop() { c.pop_back(); } T top() { return c.back(); } bool empty() const { return c.empty(); } size_t size() const { return c.size(); } };这个MyStack模板类默认用vector当底层容器。核心就是把vector的接口包装一下push调用push_backpop调用pop_backtop调用backempty和size直接用vector的同名接口。说白了stack就是个“包装器”核心功能还是靠底层容器。2.1.3 实战案例括号匹配检查stack的应用场景特别多括号匹配检查绝对是最经典的一个。咱们写代码的时候经常要用到()、[]、{}要是配对错了代码直接报错。利用栈的后进先出特性可以轻松解决这个问题具体实现思路如下遍历字符串遇到左括号(、{、[就压进栈里。左括号肯定要等对应的右括号先存起来准没错。遇到右括号)、}、]先看栈空不空。要是空的说明没对应的左括号直接返回不匹配要是不空就取栈顶元素对比匹配就弹栈不匹配就返回false。遍历完之后栈空了说明所有括号都配对成功反之就有没匹配的返回false。对应的代码实现如下大家可以直接抄来用#include iostream #include stack #include string bool isValidBrackets(const std::string str) { std::stackchar stk; for (char c : str) { if (c ( || c { || c [) { stk.push(c); } else { if (stk.empty()) return false; char top stk.top(); if ((c ) top ! () || (c } top ! {) || (c ] top ! [)) { return false; } stk.pop(); } } return stk.empty(); }使用这段代码我们可以快速验证一个字符串中的括号是否匹配int main() { std::string s1 {[()]}; std::string s2 ([)]; std::string s3 {}()[]; std::cout s1: (isValidBrackets(s1)? 匹配 : 不匹配) std::endl; std::cout s2: (isValidBrackets(s2)? 匹配 : 不匹配) std::endl; std::cout s3: (isValidBrackets(s3)? 匹配 : 不匹配) std::endl; return 0; }在这个例子中我们定义了三个测试字符串 s1、s2、s3分别调用 isValidBrackets 函数进行括号匹配检查并输出结果。运行结果很明显s1{[()]}匹配s2([)]不匹配s3{}()[]匹配。这种方法核心逻辑就10行左右比自己写栈再写匹配逻辑快多了效率至少翻10倍。2.2 队列queue先进先出的 “双端控制”2.2.1 接口与使用queue和stack刚好相反是“先进先出”FIFO的容器适配器。它的接口都是围绕FIFO设计的核心接口就这几个push()入队把元素加到队列末尾。默认调用底层容器的push_back比如用deque的话就是往deque末尾加元素。pop()出队删掉队列头部的元素。默认调用底层容器的pop_front用deque就是删开头的元素。front()取队头元素不删除。back()取队尾元素也不删除。empty()判断队列空不空空返回true反之false。size()返回队列里元素的个数知道队列有多大。在实际使用中队列的操作也很简单用法和stack差不多。比如我们创建一个整数队列将一些整数入队然后依次出队并输出#include iostream #include queue int main() { std::queueint myQueue; // 入队操作 myQueue.push(10); myQueue.push(20); myQueue.push(30); // 输出队头元素 std::cout 队头元素: myQueue.front() std::endl; // 出队操作并输出弹出的元素 while (!myQueue.empty()) { std::cout 出队元素: myQueue.front() std::endl; myQueue.pop(); } return 0; }逻辑很简单创建队列myQueue用push把10、20、30入队用front取队头元素此时是10。然后循环取队头元素输出再出队直到队列为空完美体现FIFO特性。2.2.2 底层实现与容器选择queue和stack最大的不同就是它需要在两端操作队尾入队队头出队。所以底层容器必须支持push_back尾插和pop_front头删不然用不了。STL里queue默认用deque当底层容器就是因为deque两端操作都快时间复杂度O(1)。list也能用它也支持两端高效操作但内存是不连续的不如deque实用。至于vector就不适合当queue的底层容器了——它没有高效的pop_front删头部元素要搬移所有元素时间复杂度O(n)数据多了会特别慢。同样给大家整个queue的模拟实现以便更好地理解其底层原理#include iostream #include deque template typename T, typename Container std::dequeT class MyQueue { private: Container c; // 底层容器 public: void push(const T x) { c.push_back(x); } void pop() { c.pop_front(); } T front() { return c.front(); } T back() { return c.back(); } bool empty() const { return c.empty(); } size_t size() const { return c.size(); } };这个MyQueue默认用deque当底层容器核心还是包装接口push调用push_backpop调用pop_frontfront和back直接用deque的同名接口。关键就是要满足queue的FIFO特性底层容器的接口必须匹配。2.2.3 实战案例广度优先搜索BFSqueue在算法里用得特别多广度优先搜索BFS绝对离不开它。BFS主要用来遍历图或者树按层次一层一层访问节点queue就是用来存待访问节点的核心工具。BFS的步骤很固定用queue实现特别简单先把起点节点入队这是搜索的开始。队列不为空就循环取队头节点处理处理完把它没访问过的邻居节点都入队。这样就能一层一层访问不会乱。直到队列为空所有能访问到的节点都处理完了搜索结束。用STL的queue写BFS根本不用操心底层存储专心想算法逻辑就行代码量至少能省一半。下面是一个简单的 BFS 示例用于遍历一个简单的图#include iostream #include deque template typename T, typename Container std::dequeT class MyQueue { private: Container c; // 底层容器 public: void push(const T x) { c.push_back(x); } void pop() { c.pop_front(); } T front() { return c.front(); } T back() { return c.back(); } bool empty() const { return c.empty(); } size_t size() const { return c.size(); } };这里用邻接表表示图bfs函数里创建了一个记录访问节点的集合和一个queue。先把起点入队并标记为已访问然后循环取队头节点访问再把没访问过的邻居入队直到队空。整个过程特别清晰重点都在算法逻辑上。三、为什么选择 deque 作为默认底层容器3.1 deque 的特性解析很多粉丝可能会好奇为啥STL偏偏选deque当stack和queue的默认底层容器其实核心就是两个字平衡——兼顾效率和适用场景。我们先聊聊deque的特性。1、双端高效操作deque全称是双端队列最大的优点就是两端插入、删除都快时间复杂度都是O(1)。对stack来说push和pop都在一端用deque刚好对queue来说队尾入队、队头出队deque两端操作都高效完美适配。要是用vector当头插得搬移所有元素慢到不行。2、分段连续内存再看内存结构deque用的是“分段连续内存”还有个中控器管理所有内存块。比如元素满了要扩容只需要新开辟一块内存在中控器里加个指针就行不用像vector那样拷贝所有元素。vector扩容的时候又费时间又占内存deque就没这问题。3、无迭代器依赖还有个关键原因stack和queue根本不用遍历deque的迭代器确实有点复杂遍历效率不高但stack只关心栈顶queue只关心队头队尾完全用不上遍历。这就避开了deque的缺点只用到了它的优点。3.2 对比其他容器咱们用表格对比下deque、vector、list在stack和queue场景下的表现一看就知道为啥deque是首选底层容器stack 场景LIFOqueue 场景FIFOdeque最优双端操作都快最优两端操作都快vector可行尾插尾删还行不可行头删太慢list可行双向操作都支持可行双向操作都支持从表格能看出来vector虽然尾插尾删快但头删不行只能当stack的底层容器还得忍受扩容拷贝的问题。queue用vector就纯属找罪受删个头都要等半天。list倒是双向操作都快理论上能用但它内存不连续访问速度慢还得额外存指针内存开销大。日常开发里除了特殊场景没人会特意选list当底层容器。所以说deque既能满足stack和queue对双端操作的效率要求又能平衡内存和扩容问题通用性最强。选它当默认底层容器绝对是STL开发者的最优解。整理了一波干货文章✨直接覆盖Linux C/C全成长赛道 主打一个帮大家避坑、少走弯路技术升级一路开挂✨ 先破局C到底值不值得冲是不是总刷到“劝退C”的帖子转头又刷到大厂核心岗疯抢别内耗别纠结速看《为什么很多人劝退学C但大厂核心岗位还是要C》帮你理清思路放心冲就完事主打一个不踩认知坑✨ 后端党集合按大厂标准打怪升级想深耕Linux C/C后端却对着一堆知识点一脸懵《【大厂标准】Linux C/C后端进阶学习路线》直接帮你捋顺学习脉络搭好能力框架进阶路上不慌不忙主打一个高效上分✨ 音视频爱好者速来入门不懵圈对音视频流媒体开发狠狠心动但一上手就卡壳《音视频流媒体高级开发 - 学习路线》把核心技术拆得明明白白帮你快速搭好知识框架轻松开启学习模式新手也能快速入门✨ Qt选手狂喜桌面/嵌入式通吃不管是想搞桌面应用还是深耕嵌入式开发《C Qt学习路线一条龙桌面开发 嵌入式开发》直接拿捏 从入门到实战一步到位轻松搞定项目落地不用自己瞎琢磨主打一个省心✨ 硬核玩家专属深挖Linux内核想钻透操作系统底层突破技术天花板《Linux内核学习指南硬核修炼手册》分享超实用的学习小技巧适合愿意沉下心深耕的宝子主打一个硬核提升✨ 面试冲刺八股文速查神器备战技术面试需要快速复盘知识点《C高频八股文面试题1000题三》直接当复习手册用帮你巩固核心考点面试时气场拉满不慌不乱主打一个稳稳上岸四、避坑指南与进阶用法4.1 空容器操作风险在使用 stack 和 queue 时空容器的操作是一个需要特别注意的点。最常见的就是空容器操作——比如栈空了还调用top()队列空了还调用front()这都会触发未定义行为程序直接崩给你看。空容器调用pop()也一样会出大问题。解决办法很简单调用top()、front()、back()之前先用empty()检查一下容器是不是空的。比如这样写std::stackint myStack; // 假设这里没有向栈中添加元素 if (!myStack.empty()) { int topElement myStack.top(); // 进行后续操作 }还有个小细节pop()不会返回被弹出的元素。所以要先用top()或front()取元素再pop()。比如队列操作要这样写不然会丢数据std::queueint myQueue; myQueue.push(10); if (!myQueue.empty()) { int frontElement myQueue.front(); myQueue.pop(); // 使用frontElement进行后续操作 }4.2 自定义底层容器虽然默认用deque但某些场景下我们也能自定义底层容器。比如想利用vector的连续内存优势提高访问速度就可以显式指定vector当stack的底层容器std::stackint, std::vectorint myStack;但一定要记住自定义容器必须支持适配器需要的接口stack要push_back和pop_backqueue要push_back和pop_front。不支持的话编译直接报错别踩这个坑。4.3 性能优化建议性能优化方面也说两句用stack的话数据量大、增长快的场景优先用默认的deque避免vector频繁扩容拷贝用queue的话如果能预估数据量提前给底层容器预留空间能减少扩容次数。比如用deque当底层的queue可以这样写std::queueint myQueue; std::dequeint underlyingDeque myQueue.get_container(); underlyingDeque.reserve(100); // 假设预估数据量为100这样提前预留100个元素的空间后续入队的时候就不用频繁扩容了效率会高很多。最后给大家留一个小思考优先级队列又是如何通过适配器实现的它的底层容器选择与栈、队列有何不同
面试必问：C++ STL 适配器
发布时间：2026/7/6 4:55:45
在C编程中我们经常需要实现一些基础的数据结构。比如栈stack和队列queue明明已经有vector存数据了但它的接口根本不符合栈“后进先出”、队列“先进先出”的需求只能自己从头写push、pop、top这些接口一套下来光一个简单的栈就写了几十行代码重复造轮子的感觉太糟了。这时候会花不少时间从头开始写——定义结构、实现各种操作函数……结果一个简单的栈或队列代码就可能膨胀到几十甚至上百行。而 STL 适配器的出现正是为了把我们从这种“重复造轮子”的工作中解放出来。它就像一把精巧的转换器通过对现有容器进行封装用极少的代码就能实现特定的数据结构行为让编程变得更简洁、更高效。而STL适配器就是来解决这个问题的它就像个现成的“工具包”直接把vector、deque这些基础容器包装一下就能变成你需要的栈或队列几行代码就能搞定所有功能省下来的时间摸鱼不香吗一、什么是 STL 适配器1.1 适配器模式接口转换的核心思想其实适配器模式很好理解说白了就是个“接口转换器”。就像我们手机充电插座是220V交流电手机要的是5V直流电这时候电源适配器一插问题就解决了——既不用改插座也不用动手机。STL适配器也是一个道理。它把vector、deque这些基础容器“包起来”藏起里面复杂的实现细节只给你暴露栈、队列需要的接口。比如你想要个栈它就把deque的接口改成“后进先出”的样式你直接用push、pop、top就行根本不用管底层是怎么存数据的。1.2 三大适配器类型STL里的适配器主要分三类各自有不同的用处咱们简单过一遍容器适配器改造现有容器的接口让它变成特定数据结构。比如stack、queue、priority_queue都属于这个范畴默认都是用deque包装出来的用的时候就像用独立数据结构一样方便。迭代器适配器改变迭代器的遍历方向。比如reverse_iterator本来迭代器是从前往后走用它就能反过来遍历特别实用。函数适配器帮你调整函数的调用方式。比如std::bind能把函数和固定参数绑在一起生成新的调用对象后续用起来更灵活。今天咱们重点聊容器适配器就盯着stack和queue这两个最常用的扒一扒它们的底层逻辑看看怎么用最少的代码实现最强的功能。二、容器适配器详解2.1 栈stack后进先出的 “极简封装”2.1.1 接口与使用STL里的stack就是个容器适配器专门实现“后进先出”LIFO的逻辑。它的接口设计特别精简核心就5个记起来毫无压力push()压栈把元素放到栈顶。底层默认调用容器的push_back比如用deque当底层的话就是往deque末尾加元素相当于栈顶。pop()弹栈删掉栈顶元素。底层默认调用pop_back还是以deque为例就是删掉末尾的元素。top()取栈顶元素不会删掉它。底层对应容器的back()直接拿deque末尾的元素就行。empty()判断栈是不是空的空就返回true反之false。size()返回栈里有多少个元素一眼知道栈的大小。实际用起来特别简单给大家放个整数栈的示例代码一看就懂#include iostream #include stack int main() { std::stackint myStack; // 压栈操作 myStack.push(10); myStack.push(20); myStack.push(30); // 输出栈顶元素 std::cout 栈顶元素: myStack.top() std::endl; // 弹栈操作并输出弹出的元素 while (!myStack.empty()) { std::cout 弹出元素: myStack.top() std::endl; myStack.pop(); } return 0; }这段代码很直观先创建一个整数栈myStack用push把10、20、30依次压进去再用top取栈顶元素此时是30。最后用while循环只要栈不为空就先取栈顶元素输出再用pop弹栈直到栈空为止。2.1.2 底层实现与模拟其实STL的stack就是个模板类默认用deque当底层容器。为啥选deque因为它两端插入、删除都快时间复杂度都是O(1)刚好适配栈的操作需求。当然你也可以自己指定底层容器比如用vector或者list。但要注意选的容器必须支持stack需要的接口——比如stack要用push_back和pop_back所以vector能用但它扩容的时候会拷贝元素可能影响性能这点要留意。为了让大家更清楚底层逻辑我写了个简单的stack模拟实现大家可以看看#include iostream #include vector template typename T, typename Container std::vectorT class MyStack { private: Container c; // 底层容器 public: void push(const T x) { c.push_back(x); } void pop() { c.pop_back(); } T top() { return c.back(); } bool empty() const { return c.empty(); } size_t size() const { return c.size(); } };这个MyStack模板类默认用vector当底层容器。核心就是把vector的接口包装一下push调用push_backpop调用pop_backtop调用backempty和size直接用vector的同名接口。说白了stack就是个“包装器”核心功能还是靠底层容器。2.1.3 实战案例括号匹配检查stack的应用场景特别多括号匹配检查绝对是最经典的一个。咱们写代码的时候经常要用到()、[]、{}要是配对错了代码直接报错。利用栈的后进先出特性可以轻松解决这个问题具体实现思路如下遍历字符串遇到左括号(、{、[就压进栈里。左括号肯定要等对应的右括号先存起来准没错。遇到右括号)、}、]先看栈空不空。要是空的说明没对应的左括号直接返回不匹配要是不空就取栈顶元素对比匹配就弹栈不匹配就返回false。遍历完之后栈空了说明所有括号都配对成功反之就有没匹配的返回false。对应的代码实现如下大家可以直接抄来用#include iostream #include stack #include string bool isValidBrackets(const std::string str) { std::stackchar stk; for (char c : str) { if (c ( || c { || c [) { stk.push(c); } else { if (stk.empty()) return false; char top stk.top(); if ((c ) top ! () || (c } top ! {) || (c ] top ! [)) { return false; } stk.pop(); } } return stk.empty(); }使用这段代码我们可以快速验证一个字符串中的括号是否匹配int main() { std::string s1 {[()]}; std::string s2 ([)]; std::string s3 {}()[]; std::cout s1: (isValidBrackets(s1)? 匹配 : 不匹配) std::endl; std::cout s2: (isValidBrackets(s2)? 匹配 : 不匹配) std::endl; std::cout s3: (isValidBrackets(s3)? 匹配 : 不匹配) std::endl; return 0; }在这个例子中我们定义了三个测试字符串 s1、s2、s3分别调用 isValidBrackets 函数进行括号匹配检查并输出结果。运行结果很明显s1{[()]}匹配s2([)]不匹配s3{}()[]匹配。这种方法核心逻辑就10行左右比自己写栈再写匹配逻辑快多了效率至少翻10倍。2.2 队列queue先进先出的 “双端控制”2.2.1 接口与使用queue和stack刚好相反是“先进先出”FIFO的容器适配器。它的接口都是围绕FIFO设计的核心接口就这几个push()入队把元素加到队列末尾。默认调用底层容器的push_back比如用deque的话就是往deque末尾加元素。pop()出队删掉队列头部的元素。默认调用底层容器的pop_front用deque就是删开头的元素。front()取队头元素不删除。back()取队尾元素也不删除。empty()判断队列空不空空返回true反之false。size()返回队列里元素的个数知道队列有多大。在实际使用中队列的操作也很简单用法和stack差不多。比如我们创建一个整数队列将一些整数入队然后依次出队并输出#include iostream #include queue int main() { std::queueint myQueue; // 入队操作 myQueue.push(10); myQueue.push(20); myQueue.push(30); // 输出队头元素 std::cout 队头元素: myQueue.front() std::endl; // 出队操作并输出弹出的元素 while (!myQueue.empty()) { std::cout 出队元素: myQueue.front() std::endl; myQueue.pop(); } return 0; }逻辑很简单创建队列myQueue用push把10、20、30入队用front取队头元素此时是10。然后循环取队头元素输出再出队直到队列为空完美体现FIFO特性。2.2.2 底层实现与容器选择queue和stack最大的不同就是它需要在两端操作队尾入队队头出队。所以底层容器必须支持push_back尾插和pop_front头删不然用不了。STL里queue默认用deque当底层容器就是因为deque两端操作都快时间复杂度O(1)。list也能用它也支持两端高效操作但内存是不连续的不如deque实用。至于vector就不适合当queue的底层容器了——它没有高效的pop_front删头部元素要搬移所有元素时间复杂度O(n)数据多了会特别慢。同样给大家整个queue的模拟实现以便更好地理解其底层原理#include iostream #include deque template typename T, typename Container std::dequeT class MyQueue { private: Container c; // 底层容器 public: void push(const T x) { c.push_back(x); } void pop() { c.pop_front(); } T front() { return c.front(); } T back() { return c.back(); } bool empty() const { return c.empty(); } size_t size() const { return c.size(); } };这个MyQueue默认用deque当底层容器核心还是包装接口push调用push_backpop调用pop_frontfront和back直接用deque的同名接口。关键就是要满足queue的FIFO特性底层容器的接口必须匹配。2.2.3 实战案例广度优先搜索BFSqueue在算法里用得特别多广度优先搜索BFS绝对离不开它。BFS主要用来遍历图或者树按层次一层一层访问节点queue就是用来存待访问节点的核心工具。BFS的步骤很固定用queue实现特别简单先把起点节点入队这是搜索的开始。队列不为空就循环取队头节点处理处理完把它没访问过的邻居节点都入队。这样就能一层一层访问不会乱。直到队列为空所有能访问到的节点都处理完了搜索结束。用STL的queue写BFS根本不用操心底层存储专心想算法逻辑就行代码量至少能省一半。下面是一个简单的 BFS 示例用于遍历一个简单的图#include iostream #include deque template typename T, typename Container std::dequeT class MyQueue { private: Container c; // 底层容器 public: void push(const T x) { c.push_back(x); } void pop() { c.pop_front(); } T front() { return c.front(); } T back() { return c.back(); } bool empty() const { return c.empty(); } size_t size() const { return c.size(); } };这里用邻接表表示图bfs函数里创建了一个记录访问节点的集合和一个queue。先把起点入队并标记为已访问然后循环取队头节点访问再把没访问过的邻居入队直到队空。整个过程特别清晰重点都在算法逻辑上。三、为什么选择 deque 作为默认底层容器3.1 deque 的特性解析很多粉丝可能会好奇为啥STL偏偏选deque当stack和queue的默认底层容器其实核心就是两个字平衡——兼顾效率和适用场景。我们先聊聊deque的特性。1、双端高效操作deque全称是双端队列最大的优点就是两端插入、删除都快时间复杂度都是O(1)。对stack来说push和pop都在一端用deque刚好对queue来说队尾入队、队头出队deque两端操作都高效完美适配。要是用vector当头插得搬移所有元素慢到不行。2、分段连续内存再看内存结构deque用的是“分段连续内存”还有个中控器管理所有内存块。比如元素满了要扩容只需要新开辟一块内存在中控器里加个指针就行不用像vector那样拷贝所有元素。vector扩容的时候又费时间又占内存deque就没这问题。3、无迭代器依赖还有个关键原因stack和queue根本不用遍历deque的迭代器确实有点复杂遍历效率不高但stack只关心栈顶queue只关心队头队尾完全用不上遍历。这就避开了deque的缺点只用到了它的优点。3.2 对比其他容器咱们用表格对比下deque、vector、list在stack和queue场景下的表现一看就知道为啥deque是首选底层容器stack 场景LIFOqueue 场景FIFOdeque最优双端操作都快最优两端操作都快vector可行尾插尾删还行不可行头删太慢list可行双向操作都支持可行双向操作都支持从表格能看出来vector虽然尾插尾删快但头删不行只能当stack的底层容器还得忍受扩容拷贝的问题。queue用vector就纯属找罪受删个头都要等半天。list倒是双向操作都快理论上能用但它内存不连续访问速度慢还得额外存指针内存开销大。日常开发里除了特殊场景没人会特意选list当底层容器。所以说deque既能满足stack和queue对双端操作的效率要求又能平衡内存和扩容问题通用性最强。选它当默认底层容器绝对是STL开发者的最优解。整理了一波干货文章✨直接覆盖Linux C/C全成长赛道 主打一个帮大家避坑、少走弯路技术升级一路开挂✨ 先破局C到底值不值得冲是不是总刷到“劝退C”的帖子转头又刷到大厂核心岗疯抢别内耗别纠结速看《为什么很多人劝退学C但大厂核心岗位还是要C》帮你理清思路放心冲就完事主打一个不踩认知坑✨ 后端党集合按大厂标准打怪升级想深耕Linux C/C后端却对着一堆知识点一脸懵《【大厂标准】Linux C/C后端进阶学习路线》直接帮你捋顺学习脉络搭好能力框架进阶路上不慌不忙主打一个高效上分✨ 音视频爱好者速来入门不懵圈对音视频流媒体开发狠狠心动但一上手就卡壳《音视频流媒体高级开发 - 学习路线》把核心技术拆得明明白白帮你快速搭好知识框架轻松开启学习模式新手也能快速入门✨ Qt选手狂喜桌面/嵌入式通吃不管是想搞桌面应用还是深耕嵌入式开发《C Qt学习路线一条龙桌面开发 嵌入式开发》直接拿捏 从入门到实战一步到位轻松搞定项目落地不用自己瞎琢磨主打一个省心✨ 硬核玩家专属深挖Linux内核想钻透操作系统底层突破技术天花板《Linux内核学习指南硬核修炼手册》分享超实用的学习小技巧适合愿意沉下心深耕的宝子主打一个硬核提升✨ 面试冲刺八股文速查神器备战技术面试需要快速复盘知识点《C高频八股文面试题1000题三》直接当复习手册用帮你巩固核心考点面试时气场拉满不慌不乱主打一个稳稳上岸四、避坑指南与进阶用法4.1 空容器操作风险在使用 stack 和 queue 时空容器的操作是一个需要特别注意的点。最常见的就是空容器操作——比如栈空了还调用top()队列空了还调用front()这都会触发未定义行为程序直接崩给你看。空容器调用pop()也一样会出大问题。解决办法很简单调用top()、front()、back()之前先用empty()检查一下容器是不是空的。比如这样写std::stackint myStack; // 假设这里没有向栈中添加元素 if (!myStack.empty()) { int topElement myStack.top(); // 进行后续操作 }还有个小细节pop()不会返回被弹出的元素。所以要先用top()或front()取元素再pop()。比如队列操作要这样写不然会丢数据std::queueint myQueue; myQueue.push(10); if (!myQueue.empty()) { int frontElement myQueue.front(); myQueue.pop(); // 使用frontElement进行后续操作 }4.2 自定义底层容器虽然默认用deque但某些场景下我们也能自定义底层容器。比如想利用vector的连续内存优势提高访问速度就可以显式指定vector当stack的底层容器std::stackint, std::vectorint myStack;但一定要记住自定义容器必须支持适配器需要的接口stack要push_back和pop_backqueue要push_back和pop_front。不支持的话编译直接报错别踩这个坑。4.3 性能优化建议性能优化方面也说两句用stack的话数据量大、增长快的场景优先用默认的deque避免vector频繁扩容拷贝用queue的话如果能预估数据量提前给底层容器预留空间能减少扩容次数。比如用deque当底层的queue可以这样写std::queueint myQueue; std::dequeint underlyingDeque myQueue.get_container(); underlyingDeque.reserve(100); // 假设预估数据量为100这样提前预留100个元素的空间后续入队的时候就不用频繁扩容了效率会高很多。最后给大家留一个小思考优先级队列又是如何通过适配器实现的它的底层容器选择与栈、队列有何不同
