1. 项目概述C数据结构与算法实战训练最近在整理C算法刷题笔记时发现栈和队列这对数据结构双生子在面试中出现的频率极高。特别是它们之间的相互实现问题既能考察对基础数据结构的理解深度又能检验编码实现能力。这次我将通过5个经典题目用栈实现队列、用队列实现栈、有效的括号、删除字符串相邻重复项、逆波兰表达式求值分享C标准库容器在实际算法问题中的灵活运用技巧。这些题目覆盖了LeetCode中栈和队列类问题的典型场景数据结构相互转化栈↔队列符号匹配验证括号有效性字符串处理相邻重复项删除表达式计算逆波兰表示法提示本文所有代码示例均基于C17标准使用STL容器时需要包含 和 头文件2. 核心题目解析与实现方案2.1 用栈实现队列LeetCode 232栈LIFO和队列FIFO的本质区别在于元素的出入顺序。要用栈模拟队列我们需要两个栈来翻转元素顺序class MyQueue { private: stackint 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: queueint 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: queueint 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) { stackchar st; unordered_mapchar, 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(vectorstring tokens) { stackint 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/dequestack无法迭代频繁的转移操作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可能提升局部性stackint, vectorint st; // 使用vector作为底层容器表达式计算注意事项操作数顺序特别是减法和除法整数溢出处理尤其乘法操作除以零检查3.3 性能优化实践预留空间提前reserve()避免动态扩容string stack; stack.reserve(s.size()); // 预分配字符串空间移动语义对于大型对象使用emplacestack.emplace(arg1, arg2); // 避免临时对象构造自定义哈希当使用自定义类型作为map键时struct PairHash { size_t operator()(const pairint,int p) const { return hashint()(p.first) ^ hashint()(p.second); } }; unordered_mappairint,int, char, PairHash pairs;4. 扩展应用与变种问题4.1 单调栈应用场景单调栈是栈的一种特殊用法常用于解决下一个更大元素类问题vectorint nextGreaterElements(vectorint nums) { int n nums.size(); vectorint res(n, -1); stackint 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的核心数据结构以下为二叉树层序遍历示例vectorvectorint levelOrder(TreeNode* root) { vectorvectorint res; queueTreeNode* q; if (root) q.push(root); while (!q.empty()) { int size q.size(); vectorint 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 155class MinStack { private: stackint dataStack; stackint 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一次通过所有测试用例。