1. 项目概述：C++数据结构与算法实战训练
最近在整理C++算法刷题笔记时，发现栈和队列这对"数据结构双生子"在面试中出现的频率极高。特别是它们之间的相互实现问题，既能考察对基础数据结构的理解深度，又能检验编码实现能力。这次我将通过5个经典题目（用栈实现队列、用队列实现栈、有效的括号、删除字符串相邻重复项、逆波兰表达式求值），分享C++标准库容器在实际算法问题中的灵活运用技巧。
这些题目覆盖了LeetCode中栈和队列类问题的典型场景：
- 数据结构相互转化（栈↔队列）
- 符号匹配验证（括号有效性）
- 字符串处理（相邻重复项删除）
- 表达式计算（逆波兰表示法）
提示：本文所有代码示例均基于C++17标准，使用STL容器时需要包含 和 头文件
2. 核心题目解析与实现方案
2.1 用栈实现队列（LeetCode 232）
栈（LIFO）和队列（FIFO）的本质区别在于元素的出入顺序。要用栈模拟队列，我们需要两个栈来"翻转"元素顺序：
class MyQueue { private: stack<int> inStack, outStack; void transfer() { while (!inStack.empty()) { outStack.push(inStack.top()); inStack.pop(); } } public: void push(int x) { inStack.push(x); } int pop() { if (outStack.empty()) transfer(); int val = outStack.top(); outStack.pop(); return val; } int peek() { if (outStack.empty()) transfer(); return outStack.top(); } bool empty() { return inStack.empty() && outStack.empty(); } };时间复杂度分析：
- 均摊时间复杂度：O(1)（每个元素最多被push/pop两次）
- 最坏情况时间复杂度：O(n)（当outStack为空时需要转移全部元素）
注意事项：在pop()和peek()操作时，必须检查outStack是否为空，否则会导致顺序错乱
2.2 用队列实现栈（LeetCode 225）
与前一题相反，这里需要用队列的FIFO特性实现栈的LIFO行为。有两种主流实现方式：
方案一：双队列法（主队列+辅助队列）
class MyStack { private: queue<int> q1, q2; public: void push(int x) { q2.push(x); while (!q1.empty()) { q2.push(q1.front()); q1.pop(); } swap(q1, q2); } int pop() { int val = q1.front(); q1.pop(); return val; } // ...其他接口实现 };方案二：单队列循环法（更优空间复杂度）
class MyStack { private: queue<int> q; public: void push(int x) { int size = q.size(); q.push(x); for (int i = 0; i < size; ++i) { q.push(q.front()); q.pop(); } } // ...其他接口实现 };性能对比：
| 方案 | push时间复杂度 | pop时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 双队列法 | O(n) | O(1) | O(n) |
| 单队列法 | O(n) | O(1) | O(n) |
虽然两种方案时间复杂度相同，但单队列法减少了队列切换的开销，实际运行效率更高。
2.3 有效的括号（LeetCode 20）
这是栈结构的经典应用场景，通过维护一个括号栈来验证嵌套关系：
bool isValid(string s) { stack<char> st; unordered_map<char, char> pairs = { {')', '('}, {']', '['}, {'}', '{'} }; for (char c : s) { if (pairs.count(c)) { // 右括号 if (st.empty() || st.top() != pairs[c]) return false; st.pop(); } else { // 左括号 st.push(c); } } return st.empty(); }边界条件处理：
- 字符串长度为奇数时直接返回false
- 栈为空时遇到右括号立即返回false
- 遍历结束后栈不为空说明有未匹配的左括号
2.4 删除字符串中所有相邻重复项（LeetCode 1047）
这个问题可以看作是括号匹配的变种，使用栈来维护非重复字符序列：
string removeDuplicates(string s) { string stack; for (char c : s) { if (!stack.empty() && stack.back() == c) { stack.pop_back(); } else { stack.push_back(c); } } return stack; }优化技巧：
- 直接使用string作为栈容器，避免最后反转操作
- 时间复杂度O(n)，空间复杂度O(1)（如果允许修改原字符串）
2.5 逆波兰表达式求值（LeetCode 150）
逆波兰表示法（后缀表达式）的计算是栈的典型应用：
int evalRPN(vector<string>& tokens) { stack<int> st; for (const string& token : tokens) { if (token == "+" || token == "-" || token == "*" || token == "/") { int b = st.top(); st.pop(); int a = st.top(); st.pop(); if (token == "+") st.push(a + b); else if (token == "-") st.push(a - b); else if (token == "*") st.push(a * b); else st.push(a / b); } else { st.push(stoi(token)); } } return st.top(); }注意事项：
- 除法向零取整（C++默认行为）
- 操作数顺序：先弹出的是右操作数
- 使用stoi()将字符串转为整数
3. 核心技巧与常见问题
3.1 STL容器选择策略
| 场景 | 推荐容器 | 原因 |
|---|---|---|
| 需要快速访问顶部元素 | stack | 提供简洁的LIFO接口 |
| 需要遍历栈内容 | vector/deque | stack无法迭代 |
| 频繁的转移操作 | deque | 两端操作效率高 |
| 字符串构建型栈操作 | string | 直接支持字符操作和结果返回 |
3.2 调试技巧与边界条件
栈空检查：在调用top()/pop()前必须检查empty()
// 错误示范 int val = st.top(); // 可能崩溃 st.pop(); // 正确做法 if (!st.empty()) { int val = st.top(); st.pop(); }容器选择陷阱：
- stack默认基于deque实现，切换为vector可能提升局部性
stack<int, vector<int>> st; // 使用vector作为底层容器表达式计算注意事项：
- 操作数顺序（特别是减法和除法）
- 整数溢出处理（尤其乘法操作）
- 除以零检查
3.3 性能优化实践
预留空间：提前reserve()避免动态扩容
string stack; stack.reserve(s.size()); // 预分配字符串空间移动语义：对于大型对象使用emplace
stack.emplace(arg1, arg2); // 避免临时对象构造自定义哈希：当使用自定义类型作为map键时
struct PairHash { size_t operator()(const pair<int,int>& p) const { return hash<int>()(p.first) ^ hash<int>()(p.second); } }; unordered_map<pair<int,int>, char, PairHash> pairs;
4. 扩展应用与变种问题
4.1 单调栈应用场景
单调栈是栈的一种特殊用法，常用于解决"下一个更大元素"类问题：
vector<int> nextGreaterElements(vector<int>& nums) { int n = nums.size(); vector<int> res(n, -1); stack<int> st; // 存储下标 for (int i = 0; i < 2*n; ++i) { while (!st.empty() && nums[st.top()] < nums[i%n]) { res[st.top()] = nums[i%n]; st.pop(); } if (i < n) st.push(i); } return res; }4.2 队列在BFS中的应用
队列是广度优先搜索（BFS）的核心数据结构，以下为二叉树层序遍历示例：
vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> res; queue<TreeNode*> q; if (root) q.push(root); while (!q.empty()) { int size = q.size(); vector<int> level; while (size--) { TreeNode* node = q.front(); q.pop(); level.push_back(node->val); if (node->left) q.push(node->left); if (node->right) q.push(node->right); } res.push_back(level); } return res; }4.3 复合数据结构问题
当问题需要同时维护多种特性时，可以组合使用栈和队列：
实现一个支持getMin()的栈（LeetCode 155）
class MinStack { private: stack<int> dataStack; stack<int> minStack; public: void push(int x) { dataStack.push(x); if (minStack.empty() || x <= minStack.top()) { minStack.push(x); } } void pop() { if (dataStack.top() == minStack.top()) { minStack.pop(); } dataStack.pop(); } int top() { return dataStack.top(); } int getMin() { return minStack.top(); } };在实际工程中，这种数据结构组合的思想广泛应用于：
- 浏览器前进后退栈
- 撤销操作记录
- 消息队列的优先级处理
通过这组栈和队列的经典问题训练，我对C++ STL容器的选择和使用有了更深入的理解。特别是在处理数据结构相互转化问题时，关键在于抓住它们的本质特性——栈的LIFO和队列的FIFO，通过辅助容器来实现行为转换。建议在面试准备时，每个题目至少手写实现3遍，直到能够无bug一次通过所有测试用例。