第33篇 STL之stack与queue：BFS/DFS的标配数据结构，面试手写不过分吧-北京尧图网络

上篇聊了map和unordered_map今天看两个受限容器——stack和queue。说它们受限是因为它们不支持遍历不能随机访问只能在特定的位置操作元素。但正是这种限制让它们在特定场景下非常高效。面试里考stack和queue通常和算法题绑在一起。用BFS求最短路径实现一个栈的排序用两个栈实现队列……这些题你都得熟悉stack和queue的接口。stack后进先出stack的接口非常简单std::stackint s; s.push(1); // 入栈 s.push(2); s.push(3); cout s.top(); // 3查看栈顶 s.pop(); // 弹出3 cout s.top(); // 2 cout s.size(); // 2push和pop都在栈顶操作后进先出LIFO。没有begin()、end()不能遍历。stack的默认底层容器是deque但你可以指定用vector或liststd::stackint, std::vectorint s; // 用vector做底层 std::stackint, std::listint s; // 用list做底层大部分时候用默认的deque就够了。如果你确定stack里的元素数量会很多且不需要在中间操作用vector底层可能缓存更友好。stack在算法面试中的应用stack在面试算法题里出现频率极高。最经典的用stack实现DFS深度优先搜索。在机器人开发里DFS常用于地图探索、迷宫求解。// 网格地图的DFS探索 void dfs(vectorvectorint grid, int r, int c) { int rows grid.size(), cols grid[0].size(); stackpairint,int s; s.push({r, c}); while (!s.empty()) { auto [cr, cc] s.top(); s.pop(); if (cr 0 || cr rows || cc 0 || cc cols) continue; if (grid[cr][cc] 1) continue; // 已访问或障碍物 grid[cr][cc] 1; // 标记已访问 // 四个方向入栈 s.push({cr-1, cc}); s.push({cr1, cc}); s.push({cr, cc-1}); s.push({cr, cc1}); } }还有个经典面试题有效的括号匹配。用stack来做遇到左括号入栈遇到右括号检查栈顶是否匹配。bool isValid(const string s) { stackchar st; for (char c : s) { if (c ( || c [ || c {) { st.push(c); } else { if (st.empty()) return false; if (c ) st.top() ! () return false; if (c ] st.top() ! [) return false; if (c } st.top() ! {) return false; st.pop(); } } return st.empty(); }queue先进先出queue的接口也很简单std::queueint q; q.push(1); // 入队尾部 q.push(2); q.push(3); cout q.front(); // 1查看队首 cout q.back(); // 3查看队尾 q.pop(); // 弹出1队首push在队尾pop在队首先进先出FIFO。同样不能遍历。queue的默认底层容器也是deque。queue在算法面试中的应用queue最经典的用途就是BFS广度优先搜索。在机器人开发里BFS用于求最短路径、 flood fill、层级遍历。// 网格地图的BFS求最短路径 int shortestPath(vectorvectorint grid, pairint,int start, pairint,int end) { int rows grid.size(), cols grid[0].size(); queuepairint,int q; q.push(start); grid[start.first][start.second] 1; // 标记已访问 int steps 0; while (!q.empty()) { int size q.size(); for (int i 0; i size; i) { auto [r, c] q.front(); q.pop(); if (r end.first c end.second) return steps; int dr[] {-1, 1, 0, 0}; int dc[] {0, 0, -1, 1}; for (int d 0; d 4; d) { int nr r dr[d], nc c dc[d]; if (nr 0 nr rows nc 0 nc cols grid[nr][nc] 0) { grid[nr][nc] 1; q.push({nr, nc}); } } } steps; } return -1; // 不可达 }BFS保证找到的是最短路径在无权图中因为它是按层级扩展的。DFS不保证最短但内存占用通常更小。priority_queue带优先级的队列面试里还有个常客priority_queue优先队列。它不是FIFO而是每次弹出的都是当前最大或最小的元素。// 默认大顶堆 priority_queueint max_heap; max_heap.push(3); max_heap.push(1); max_heap.push(5); cout max_heap.top(); // 5 // 小顶堆 priority_queueint, vectorint, greaterint min_heap; min_heap.push(3); min_heap.push(1); min_heap.push(5); cout min_heap.top(); // 1priority_queue底层是vector实现的堆结构插入和弹出都是O(log N)。在机器人开发里priority_queue是A*和Dijkstra算法的核心数据结构。每次从open list里取代价最小的节点用priority_queue天然合适。// Dijkstra算法核心 priority_queuepairdouble, int, vectorpairdouble, int, greater pq; pq.push({0.0, start_node}); while (!pq.empty()) { auto [cost, node] pq.top(); pq.pop(); // 处理node... }补充一个面试容易忽略的知识点stack和queue在STL里其实是容器适配器不是独立的容器。它们底层默认分别用deque实现但你可以通过模板参数指定其他底层容器。比如stackint, vectorint用vector做底层queueint, listint用list做底层。面试时如果你能说出stack和queue是适配器而不是容器面试官会觉得你对STL的架构理解得很透彻。在机器人开发里有时候你需要一个线程安全的队列做法就是继承std::queue然后加锁或者用std::deque配合std::mutex封装一个生产者消费者队列这在多传感器数据融合的场景里非常常见。给正在准备面试的你一点建议stack和queue本身接口简单面试主要考你怎么用它们解决问题。必须掌握的stack的LIFO特性用于DFS和括号匹配queue的FIFO特性用于BFSpriority_queue用于Dijkstra和A*。面试手写代码的时候BFS和DFS是必须闭着眼写出来的。特别是BFS的层级遍历模板每次处理一层的所有节点很多候选人写着写着就乱了。下篇讲迭代器模式——STL的灵魂设计思想。如果这篇文章对你有帮助欢迎点赞、在看、转发三连。你的支持是我持续更新的最大动力。「机器人软件开发面试·从入门到精通」连载系列上一篇第32篇 STL之map与unordered_map——底层红黑树vs哈希表下一篇预告第34篇迭代器模式——STL的灵魂设计思想有任何问题欢迎评论区留言我会尽量回复。

第33篇 STL之stack与queue：BFS/DFS的标配数据结构，面试手写不过分吧

相关推荐

云服务器安全加固：从SSH端口更换到OpenClaw部署的完整指南

OpenSSH 7.4到8.9p1安全升级：编译安装与生产环境平滑迁移指南

DrawingBench: Evaluating Spatial Reasoning and UI Interaction Capabilities of Large Language Mode...

更多资讯

烽火交换机带外登录、VLAN/PVID与IPTV组播配置实战

用Python+SQLite搭建路由器默认密码查询库与调试流程

旅游区景点管理系统课设：数据结构选型与最短路径算法实战

IIS 部署 .NET WebApi 全流程：从角色安装到端口放行

操作系统期末高分攻略：进程、调度、内存与文件系统核心考点精讲

Nemea 高速网络流量分析：从抓包瓶颈到流式异常检测架构

今日更新

MATLAB缩进快捷键与批量格式化实战指南

用Poco实现Qt风格信号与槽的跨平台C++方案

ESXi裸机虚拟化安装指南：从硬件兼容到虚拟机部署

本周精选

金融AI落地指南：从调研报告到技术选型与工程实践

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

基于GMM的语音识别系统原理与MATLAB实现详解

本月热门

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

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

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

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