上篇聊了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的灵魂设计思想有任何问题欢迎评论区留言我会尽量回复。