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

1. 项目概述作为一名长期奋战在算法竞赛一线的C开发者我深知数据结构基础在实际编程中的重要性。今天要分享的这组题目涵盖了栈和队列这两种基础数据结构在算法题中的经典应用场景。这些题目看似简单却蕴含着数据结构设计的精髓也是大厂面试中的高频考点。这组题目包含五个经典问题用栈实现队列、用队列实现栈、有效的括号、删除字符串中所有的相邻重复项以及逆波兰表达式求值。每个题目都从不同角度考察了对栈和队列特性的理解与应用能力。在实际开发中这些基础数据结构的灵活运用往往能解决看似复杂的问题。2. 核心数据结构解析2.1 栈与队列的基本特性栈(Stack)是一种后进先出(LIFO)的数据结构只允许在栈顶进行插入(push)和删除(pop)操作。这种特性使得栈特别适合处理具有嵌套结构的问题比如函数调用、括号匹配等场景。队列(Queue)则是先进先出(FIFO)的数据结构元素从队尾入队(enqueue)从队头出队(dequeue)。队列常用于需要按顺序处理的场景如消息队列、广度优先搜索等。在C标准库中栈和队列分别由stack和queue头文件提供#include stack #include queue std::stackint s; // 声明一个整型栈 std::queueint q; // 声明一个整型队列2.2 栈与队列的相互实现2.2.1 用栈实现队列用栈实现队列的核心思路是使用两个栈一个输入栈(inStack)负责接收新元素一个输出栈(outStack)负责弹出元素。当outStack为空时将inStack的所有元素依次弹出并压入outStack这样就能实现FIFO的特性。class MyQueue { private: std::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(); } };注意peek()和pop()操作都需要检查outStack是否为空如果为空则需要先将inStack的元素转移到outStack。这个操作的时间复杂度虽然是O(n)但均摊到每个元素上仍然是O(1)。2.2.2 用队列实现栈用队列实现栈也有两种常见方法双队列法和单队列法。这里介绍更高效的单队列法核心思想是在每次push操作后将队列中除新元素外的所有元素依次出队再入队这样新元素就自然位于队首实现了LIFO特性。class MyStack { private: std::queueint q; public: void push(int x) { int n q.size(); q.push(x); for (int i 0; i n; i) { q.push(q.front()); q.pop(); } } int pop() { int x q.front(); q.pop(); return x; } int top() { return q.front(); } bool empty() { return q.empty(); } };实操心得虽然单队列法代码更简洁但在实际应用中如果栈操作非常频繁双队列法可能更高效。可以根据具体场景选择合适的实现方式。3. 栈的经典应用场景3.1 有效的括号括号匹配是栈的经典应用。基本思路是遍历字符串遇到左括号就入栈遇到右括号就检查栈顶是否匹配匹配则弹出不匹配则返回false。最后检查栈是否为空。bool isValid(string s) { std::stackchar st; for (char c : s) { if (c ( || c [ || c {) { st.push(c); } else { if (st.empty()) return false; char top st.top(); if ((c ) top ! () || (c ] top ! [) || (c } top ! {)) { return false; } st.pop(); } } return st.empty(); }常见错误只检查了括号匹配但忘记最后检查栈是否为空导致像((()这样的输入返回true。3.2 删除字符串中所有的相邻重复项这个问题要求删除字符串中所有相邻且相同的字符对并重复这个过程直到无法删除为止。使用栈可以高效解决遍历字符串如果当前字符与栈顶相同就弹出否则压入。string removeDuplicates(string s) { std::stackchar st; for (char c : s) { if (!st.empty() st.top() c) { st.pop(); } else { st.push(c); } } string result; while (!st.empty()) { result st.top(); st.pop(); } reverse(result.begin(), result.end()); return result; }优化版本可以直接用字符串模拟栈避免最后的反转操作string removeDuplicates(string s) { string result; for (char c : s) { if (!result.empty() result.back() c) { result.pop_back(); } else { result.push_back(c); } } return result; }3.3 逆波兰表达式求值逆波兰表达式后缀表达式的计算是栈的另一个经典应用。遍历表达式遇到数字就入栈遇到运算符就弹出栈顶两个元素进行计算然后将结果入栈。int evalRPN(vectorstring tokens) { std::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(); }注意事项1. 注意减法和除法的操作数顺序2. stoi()函数可以将字符串转换为整数3. 题目保证表达式有效实际应用中需要增加错误处理。4. 性能分析与优化4.1 时间复杂度分析栈实现队列push(): O(1)pop()/peek(): 均摊O(1)队列实现栈push(): O(n)pop()/top(): O(1)有效的括号O(n)删除相邻重复项O(n)逆波兰表达式O(n)4.2 空间复杂度分析所有解法在最坏情况下都需要O(n)的额外空间其中n是输入的大小。4.3 实际应用中的优化建议对于频繁的栈操作考虑预分配内存以避免频繁的动态内存分配。在逆波兰表达式求值中可以预先检查token是否为运算符避免多次字符串比较。在删除相邻重复项的问题中使用字符串模拟栈可以省去最后的反转操作。5. 常见问题与调试技巧5.1 栈溢出问题递归算法容易导致栈溢出特别是处理深度嵌套结构时。例如括号匹配问题如果用递归实现在深度很大的情况下会栈溢出。使用显式栈可以避免这个问题。5.2 边界条件处理空输入的情况只有一个元素的情况所有元素都相同的情况对于删除相邻重复项非法输入对于逆波兰表达式5.3 调试技巧打印栈/队列内容在关键操作前后打印数据结构的状态。使用断言检查不变量如在pop操作前检查栈是否为空。单元测试为每个边界情况编写测试用例。// 示例打印栈内容的辅助函数 void printStack(stackint s) { cout Stack (top to bottom): ; while (!s.empty()) { cout s.top() ; s.pop(); } cout endl; }6. 扩展应用与变种问题6.1 栈的更多应用场景浏览器前进后退功能撤销(Undo)操作迷宫求解算术表达式求值中缀转后缀6.2 队列的更多应用场景打印机任务队列消息队列系统广度优先搜索(BFS)缓存实现6.3 相关变种题目最小栈设计一个能在O(1)时间内获取最小元素的栈滑动窗口最大值使用双端队列实现下一个更大元素使用单调栈解决柱状图中最大矩形栈的高级应用对于想进一步挑战的读者可以尝试这些变种问题它们都是建立在栈和队列的基础之上但需要更巧妙的运用。