C++栈与队列实战：5大经典算法题解析

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(); } } // ...其他接口实现 };

性能对比：

虽然两种方案时间复杂度相同，但单队列法减少了队列切换的开销，实际运行效率更高。

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. 字符串长度为奇数时直接返回false
2. 栈为空时遇到右括号立即返回false
3. 遍历结束后栈不为空说明有未匹配的左括号

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(); }

注意事项：

1. 除法向零取整（C++默认行为）
2. 操作数顺序：先弹出的是右操作数
3. 使用stoi()将字符串转为整数

3. 核心技巧与常见问题

3.1 STL容器选择策略

3.2 调试技巧与边界条件

1. 栈空检查：在调用top()/pop()前必须检查empty()

   // 错误示范 int val = st.top(); // 可能崩溃 st.pop(); // 正确做法 if (!st.empty()) { int val = st.top(); st.pop(); }

2. 容器选择陷阱：

   • stack默认基于deque实现，切换为vector可能提升局部性

   stack<int, vector<int>> st; // 使用vector作为底层容器

3. 表达式计算注意事项：

   • 操作数顺序（特别是减法和除法）
   • 整数溢出处理（尤其乘法操作）
   • 除以零检查

3.3 性能优化实践

1. 预留空间：提前reserve()避免动态扩容

   string stack; stack.reserve(s.size()); // 预分配字符串空间

2. 移动语义：对于大型对象使用emplace

   stack.emplace(arg1, arg2); // 避免临时对象构造

3. 自定义哈希：当使用自定义类型作为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一次通过所有测试用例。