1. 项目概述：C++刷题实战专题

最近在整理C++数据结构相关的经典题目，发现栈和队列的相互实现、括号匹配、字符串处理以及逆波兰表达式这几类问题在面试和竞赛中出现频率极高。这些题目看似基础，但实际编码时容易在边界条件和效率优化上翻车。今天我就用5道典型题目，带大家系统掌握这些核心考点。

2. 核心题目解析与实现

2.1 用栈实现队列（LeetCode 232）

需求分析：要求用两个栈模拟先进先出的队列操作，需要实现push、pop、peek和empty四个基本方法。关键在于如何通过栈的LIFO特性实现FIFO效果。

双栈解法：

class MyQueue { private: stack<int> inStack; stack<int> 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(); } };

时间复杂度分析：

• push操作：O(1)
• pop/peek操作：均摊O(1)（虽然transfer是O(n)，但每个元素最多被转移一次）

关键技巧：只有当outStack为空时才进行栈间转移，避免不必要的操作

2.2 用队列实现栈（LeetCode 225）

实现方案对比：

1. 双队列法（主队列+辅助队列）
2. 单队列旋转法（更优解）

单队列实现：

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(); } } int pop() { int val = q.front(); q.pop(); return val; } int top() { return q.front(); } bool empty() { return q.empty(); } };

性能特点：

• push操作：O(n)
• pop/top操作：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(); }

边界情况处理：

1. 空字符串返回true
2. 奇数长度直接返回false
3. 栈提前为空说明右括号多余
4. 遍历结束栈非空说明左括号多余

2.4 删除字符串中所有相邻重复项（LeetCode 1047）

解法对比：

• 暴力法：O(n²)时间复杂度
• 栈解法：O(n)时间复杂度

栈实现优化：

string removeDuplicates(string s) { string res; // 用字符串模拟栈 for (char c : s) { if (!res.empty() && res.back() == c) { res.pop_back(); } else { res.push_back(c); } } return res; }

性能优化点：

1. 直接用字符串作为栈容器，避免最后反转操作
2. 比较时检查栈非空防止越界
3. 时间复杂度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(); }

易错点：

1. 字符串转整数的异常处理（题目保证输入合法可省略）
2. 除法向零取整（C++默认行为）
3. 减法和除法的操作数顺序（先弹出的是右操作数）

3. 通用解题技巧总结

3.1 栈的典型应用场景

1. 对称性匹配：括号匹配、HTML标签校验
2. 递归转迭代：二叉树遍历、DFS算法
3. 单调栈：下一个更大元素、柱状图最大矩形
4. 表达式求值：中缀转后缀、逆波兰表达式

3.2 队列的常见用法

1. BFS算法：层序遍历、最短路径
2. 滑动窗口：最大值、固定长度子数组
3. 任务调度：CPU任务队列、消息队列

3.3 字符串处理优化

1. 原地修改：双指针法降低空间复杂度
2. 栈模拟：适用于相邻元素处理
3. 正则表达式：复杂模式匹配场景

4. 常见问题与调试技巧

4.1 栈溢出预防

1. 递归转迭代时显式控制栈深度
2. 输入规模预估（特别是竞赛场景）
3. 尾递归优化（C++编译器支持有限）

4.2 容器选择策略

4.3 边界条件检查清单

1. 容器为空时的top/pop操作
2. 整数运算溢出（特别是逆波兰表达式）
3. 字符串空字符处理
4. 输入全为左括号或右括号的情况

5. 性能优化实战

5.1 内存分配优化

// 预分配足够容量 stack<int> st; st.reserve(10000); // 根据问题规模调整 // 使用原生数组实现栈（竞赛常用） int st[10000]; int top = -1;

5.2 运算加速技巧

1. 用位运算代替乘除法（仅限于2的幂次）
2. 查表法预处理常见运算结果
3. 使用快速IO方法（竞赛场景）

// 快速输入输出示例（适用于大量数据） ios::sync_with_stdio(false); cin.tie(nullptr);

6. 扩展思考

6.1 工程实践中的应用

1. 浏览器前进后退栈实现
2. 函数调用栈帧管理
3. 撤销操作(Undo)的栈式存储
4. 消息队列的优先级实现

6.2 进阶题目推荐

1. 最小栈（LeetCode 155）
2. 滑动窗口最大值（LeetCode 239）
3. 基本计算器系列（LeetCode 224/227/772）
4. 下一个更大元素系列（LeetCode 496/503）

在实际刷题过程中，建议先理解这些基础问题的解法，再逐步过渡到更复杂的变种题目。对于栈和队列这类基础数据结构，最重要的是掌握它们的核心特性和适用场景，而不是死记硬背特定题目的解法。