当前位置：首页 > news >正文

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

news 2026/8/16 21:56:45

上篇聊了map和unordered_map，今天看两个"受限"容器——stack和queue。

说它们受限，是因为它们不支持遍历，不能随机访问，只能在特定的位置操作元素。但正是这种限制，让它们在特定场景下非常高效。

面试里考stack和queue，通常和算法题绑在一起。"用BFS求最短路径""实现一个栈的排序""用两个栈实现队列"……这些题你都得熟悉stack和queue的接口。

stack：后进先出

stack的接口非常简单：

std::stack<int> s; s.push(1); // 入栈 s.push(2); s.push(3); cout << s.top(); // 3，查看栈顶 s.pop(); // 弹出3 cout << s.top(); // 2 cout << s.size(); // 2

push和pop都在栈顶操作，后进先出（LIFO）。没有begin()、end()，不能遍历。

stack的默认底层容器是deque，但你可以指定用vector或list：

std::stack<int, std::vector<int>> s; // 用vector做底层 std::stack<int, std::list<int>> s; // 用list做底层

大部分时候用默认的deque就够了。如果你确定stack里的元素数量会很多且不需要在中间操作，用vector底层可能缓存更友好。

stack在算法面试中的应用

stack在面试算法题里出现频率极高。

最经典的：用stack实现DFS（深度优先搜索）。在机器人开发里，DFS常用于地图探索、迷宫求解。

// 网格地图的DFS探索 void dfs(vector<vector<int>>& grid, int r, int c) { int rows = grid.size(), cols = grid[0].size(); stack<pair<int,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({cr+1, cc}); s.push({cr, cc-1}); s.push({cr, cc+1}); } }

还有个经典面试题："有效的括号匹配"。用stack来做，遇到左括号入栈，遇到右括号检查栈顶是否匹配。

bool isValid(const string& s) { stack<char> 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::queue<int> 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(vector<vector<int>>& grid, pair<int,int> start, pair<int,int> end) { int rows = grid.size(), cols = grid[0].size(); queue<pair<int,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_queue<int> max_heap; max_heap.push(3); max_heap.push(1); max_heap.push(5); cout << max_heap.top(); // 5 // 小顶堆 priority_queue<int, vector<int>, greater<int>> min_heap; min_heap.push(3); min_heap.push(1); min_heap.push(5); cout << min_heap.top(); // 1

priority_queue底层是vector实现的堆结构，插入和弹出都是O(log N)。

在机器人开发里，priority_queue是A*和Dijkstra算法的核心数据结构。每次从open list里取代价最小的节点，用priority_queue天然合适。

// Dijkstra算法核心 priority_queue<pair<double, int>, vector<pair<double, int>>, greater<>> pq; pq.push({0.0, start_node}); while (!pq.empty()) { auto [cost, node] = pq.top(); pq.pop(); // 处理node... }

补充一个面试容易忽略的知识点：stack和queue在STL里其实是容器适配器，不是独立的容器。它们底层默认分别用deque实现，但你可以通过模板参数指定其他底层容器。比如stack<int, vector<int>>用vector做底层，queue<int, list<int>>用list做底层。面试时如果你能说出"stack和queue是适配器而不是容器"，面试官会觉得你对STL的架构理解得很透彻。在机器人开发里，有时候你需要一个线程安全的队列，做法就是继承std::queue然后加锁，或者用std::deque配合std::mutex封装一个生产者消费者队列，这在多传感器数据融合的场景里非常常见。