当前位置：首页 > news >正文

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

news 2026/8/10 16:28:24

1. 项目概述

作为一名长期奋战在算法竞赛一线的C++开发者，我深知数据结构基础在实际编程中的重要性。今天要分享的这组题目，涵盖了栈和队列这两种基础数据结构在算法题中的经典应用场景。这些题目看似简单，却蕴含着数据结构设计的精髓，也是大厂面试中的高频考点。

这组题目包含五个经典问题：用栈实现队列、用队列实现栈、有效的括号、删除字符串中所有的相邻重复项，以及逆波兰表达式求值。每个题目都从不同角度考察了对栈和队列特性的理解与应用能力。在实际开发中，这些基础数据结构的灵活运用往往能解决看似复杂的问题。

2. 核心数据结构解析

2.1 栈与队列的基本特性

栈(Stack)是一种后进先出(LIFO)的数据结构，只允许在栈顶进行插入(push)和删除(pop)操作。这种特性使得栈特别适合处理具有嵌套结构的问题，比如函数调用、括号匹配等场景。

队列(Queue)则是先进先出(FIFO)的数据结构，元素从队尾入队(enqueue)，从队头出队(dequeue)。队列常用于需要按顺序处理的场景，如消息队列、广度优先搜索等。

在C++标准库中，栈和队列分别由<stack>和<queue>头文件提供：

#include <stack> #include <queue> std::stack<int> s; // 声明一个整型栈 std::queue<int> q; // 声明一个整型队列

2.2 栈与队列的相互实现

2.2.1 用栈实现队列

用栈实现队列的核心思路是使用两个栈：一个输入栈(inStack)负责接收新元素，一个输出栈(outStack)负责弹出元素。当outStack为空时，将inStack的所有元素依次弹出并压入outStack，这样就能实现FIFO的特性。

class MyQueue { private: std::stack<int> 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::queue<int> 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::stack<char> 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::stack<char> 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(vector<string>& tokens) { std::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. 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(stack<int> s) { cout << "Stack (top to bottom): "; while (!s.empty()) { cout << s.top() << " "; s.pop(); } cout << endl; }