1. 项目概述力扣算法题实战笔记CPP实现最近在系统刷力扣(LeetCode)的栈、队列和字符串相关题目整理了232、225、20、1047这四道经典题目的C解法笔记。这些题目看似基础但涉及到的数据结构应用和边界条件处理非常考验编程基本功。作为从ACM竞赛转工业界的老码农分享一下如何用C标准库高效解决这类问题。2. 题目解析与核心思路2.1 232. 用栈实现队列这道题要求使用栈的FILO特性模拟队列的FIFO特性。核心在于维护两个栈输入栈(inStack)直接push元素输出栈(outStack)当需要pop/peek时如果outStack为空则将inStack元素全部倒入outStackclass MyQueue { private: stackint inStack, outStack; void in2out() { while (!inStack.empty()) { outStack.push(inStack.top()); inStack.pop(); } } public: void push(int x) { inStack.push(x); } int pop() { if (outStack.empty()) in2out(); int x outStack.top(); outStack.pop(); return x; } int peek() { if (outStack.empty()) in2out(); return outStack.top(); } bool empty() { return inStack.empty() outStack.empty(); } };关键点每个元素最多经历两次入栈和出栈操作因此均摊时间复杂度为O(1)2.2 225. 用队列实现栈与232题相反这里需要用队列的FIFO特性模拟栈的FILO特性。有两种主流解法解法1双队列法主队列存储元素辅助队列用于反转操作push时先将新元素入辅助队列再将主队列元素依次移入辅助队列最后交换两个队列的角色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 x q1.front(); q1.pop(); return x; } int top() { return q1.front(); } bool empty() { return q1.empty(); } };解法2单队列法每次push后立即将队列中已有元素重新入队这样新元素会自动移动到队首void push(int x) { int n q.size(); q.push(x); for (int i 0; i n; i) { q.push(q.front()); q.pop(); } }2.3 20. 有效的括号经典的栈应用场景需要注意三种括号类型的匹配bool isValid(string s) { stackchar stk; unordered_mapchar, char pairs { {), (}, {], [}, {}, {} }; for (char c : s) { if (pairs.count(c)) { if (stk.empty() || stk.top() ! pairs[c]) return false; stk.pop(); } else { stk.push(c); } } return stk.empty(); }易错点最后需要检查栈是否为空避免只有左括号的情况2.4 1047. 删除字符串中的所有相邻重复项这道题可以用栈来高效处理相邻重复项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; }优化技巧直接使用字符串作为栈容器避免额外的栈到字符串的转换操作3. C实现中的工程细节3.1 标准库选择考量stack/queue选择力扣环境支持STL优先使用标准容器字符串处理C17后string提供更丰富的API如back()、pop_back()哈希表优化括号匹配使用unordered_map实现O(1)查找3.2 内存与性能优化reserve预分配处理字符串时可预先reserve避免多次扩容res.reserve(s.size()); // 1047题优化移动语义返回大对象时编译器会自动优化(NRVO)return res; // 不会发生拷贝引用传参对于只读的大字符串参数使用const引用bool isValid(const string s) // 避免拷贝4. 常见问题与调试技巧4.1 栈溢出问题当递归实现时可能出现栈溢出如// 错误示例递归解法可能导致栈溢出 void handleChar(int index) { if (index s.size()) return; // ...处理逻辑 handleChar(index 1); // 递归调用 }解决方案改用显式栈结构的迭代实现4.2 边界条件处理常见边界case需要特别注意空输入如空字符串单元素情况全匹配/全不匹配情况嵌套层级极深的情况4.3 调试打印技巧在力扣调试时可以使用标准输出cout Current stack size: stk.size() endl;或者定义调试宏#define DEBUG 1 #if DEBUG #define debug(x) cout #x x endl #else #define debug(x) #endif5. 扩展练习建议掌握这四题后可以尝试以下进阶题目最小栈设计支持O(1)获取最小值的栈字符串解码带嵌套的字符串处理每日温度单调栈应用去除重复字母栈与贪心结合对于想深入理解STL实现的同学建议阅读libstdc的stack和queue源码了解其底层默认使用deque作为容器适配器的实现细节。 
长河君 · 2026/9/7 22:28:08 · 阅读 1.2k 力扣栈与队列算法题C++实战解析
1. 项目概述力扣算法题实战笔记CPP实现最近在系统刷力扣(LeetCode)的栈、队列和字符串相关题目整理了232、225、20、1047这四道经典题目的C解法笔记。这些题目看似基础但涉及到的数据结构应用和边界条件处理非常考验编程基本功。作为从ACM竞赛转工业界的老码农分享一下如何用C标准库高效解决这类问题。2. 题目解析与核心思路2.1 232. 用栈实现队列这道题要求使用栈的FILO特性模拟队列的FIFO特性。核心在于维护两个栈输入栈(inStack)直接push元素输出栈(outStack)当需要pop/peek时如果outStack为空则将inStack元素全部倒入outStackclass MyQueue { private: stackint inStack, outStack; void in2out() { while (!inStack.empty()) { outStack.push(inStack.top()); inStack.pop(); } } public: void push(int x) { inStack.push(x); } int pop() { if (outStack.empty()) in2out(); int x outStack.top(); outStack.pop(); return x; } int peek() { if (outStack.empty()) in2out(); return outStack.top(); } bool empty() { return inStack.empty() outStack.empty(); } };关键点每个元素最多经历两次入栈和出栈操作因此均摊时间复杂度为O(1)2.2 225. 用队列实现栈与232题相反这里需要用队列的FIFO特性模拟栈的FILO特性。有两种主流解法解法1双队列法主队列存储元素辅助队列用于反转操作push时先将新元素入辅助队列再将主队列元素依次移入辅助队列最后交换两个队列的角色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 x q1.front(); q1.pop(); return x; } int top() { return q1.front(); } bool empty() { return q1.empty(); } };解法2单队列法每次push后立即将队列中已有元素重新入队这样新元素会自动移动到队首void push(int x) { int n q.size(); q.push(x); for (int i 0; i n; i) { q.push(q.front()); q.pop(); } }2.3 20. 有效的括号经典的栈应用场景需要注意三种括号类型的匹配bool isValid(string s) { stackchar stk; unordered_mapchar, char pairs { {), (}, {], [}, {}, {} }; for (char c : s) { if (pairs.count(c)) { if (stk.empty() || stk.top() ! pairs[c]) return false; stk.pop(); } else { stk.push(c); } } return stk.empty(); }易错点最后需要检查栈是否为空避免只有左括号的情况2.4 1047. 删除字符串中的所有相邻重复项这道题可以用栈来高效处理相邻重复项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; }优化技巧直接使用字符串作为栈容器避免额外的栈到字符串的转换操作3. C实现中的工程细节3.1 标准库选择考量stack/queue选择力扣环境支持STL优先使用标准容器字符串处理C17后string提供更丰富的API如back()、pop_back()哈希表优化括号匹配使用unordered_map实现O(1)查找3.2 内存与性能优化reserve预分配处理字符串时可预先reserve避免多次扩容res.reserve(s.size()); // 1047题优化移动语义返回大对象时编译器会自动优化(NRVO)return res; // 不会发生拷贝引用传参对于只读的大字符串参数使用const引用bool isValid(const string s) // 避免拷贝4. 常见问题与调试技巧4.1 栈溢出问题当递归实现时可能出现栈溢出如// 错误示例递归解法可能导致栈溢出 void handleChar(int index) { if (index s.size()) return; // ...处理逻辑 handleChar(index 1); // 递归调用 }解决方案改用显式栈结构的迭代实现4.2 边界条件处理常见边界case需要特别注意空输入如空字符串单元素情况全匹配/全不匹配情况嵌套层级极深的情况4.3 调试打印技巧在力扣调试时可以使用标准输出cout Current stack size: stk.size() endl;或者定义调试宏#define DEBUG 1 #if DEBUG #define debug(x) cout #x x endl #else #define debug(x) #endif5. 扩展练习建议掌握这四题后可以尝试以下进阶题目最小栈设计支持O(1)获取最小值的栈字符串解码带嵌套的字符串处理每日温度单调栈应用去除重复字母栈与贪心结合对于想深入理解STL实现的同学建议阅读libstdc的stack和queue源码了解其底层默认使用deque作为容器适配器的实现细节。