ARTICLE DETAIL

建站实战干货

来自一线的建站与推广经验沉淀，每一条都经过真实交付验证。

首页 / 资讯中心 / 正文

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

2026/8/10 16:28:24 拓冰建站 浏览量
栈与队列：5大经典算法题解析与C++实现

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 时间复杂度分析

  1. 栈实现队列：

    • push(): O(1)
    • pop()/peek(): 均摊O(1)

  2. 队列实现栈：

    • push(): O(n)
    • pop()/top(): O(1)

  3. 有效的括号：O(n)

  4. 删除相邻重复项：O(n)

  5. 逆波兰表达式：O(n)

4.2 空间复杂度分析

所有解法在最坏情况下都需要O(n)的额外空间，其中n是输入的大小。

4.3 实际应用中的优化建议

  1. 对于频繁的栈操作，考虑预分配内存以避免频繁的动态内存分配。
  2. 在逆波兰表达式求值中，可以预先检查token是否为运算符，避免多次字符串比较。
  3. 在删除相邻重复项的问题中，使用字符串模拟栈可以省去最后的反转操作。

5. 常见问题与调试技巧

5.1 栈溢出问题

递归算法容易导致栈溢出，特别是处理深度嵌套结构时。例如括号匹配问题如果用递归实现，在深度很大的情况下会栈溢出。使用显式栈可以避免这个问题。

5.2 边界条件处理

  • 空输入的情况
  • 只有一个元素的情况
  • 所有元素都相同的情况（对于删除相邻重复项）
  • 非法输入（对于逆波兰表达式）

5.3 调试技巧

  1. 打印栈/队列内容：在关键操作前后打印数据结构的状态。
  2. 使用断言检查不变量：如在pop操作前检查栈是否为空。
  3. 单元测试：为每个边界情况编写测试用例。
// 示例：打印栈内容的辅助函数 void printStack(stack<int> s) { cout << "Stack (top to bottom): "; while (!s.empty()) { cout << s.top() << " "; s.pop(); } cout << endl; }

6. 扩展应用与变种问题

6.1 栈的更多应用场景

  1. 浏览器前进后退功能
  2. 撤销(Undo)操作
  3. 迷宫求解
  4. 算术表达式求值（中缀转后缀）

6.2 队列的更多应用场景

  1. 打印机任务队列
  2. 消息队列系统
  3. 广度优先搜索(BFS)
  4. 缓存实现

6.3 相关变种题目

  1. 最小栈：设计一个能在O(1)时间内获取最小元素的栈
  2. 滑动窗口最大值：使用双端队列实现
  3. 下一个更大元素：使用单调栈解决
  4. 柱状图中最大矩形：栈的高级应用

对于想进一步挑战的读者，可以尝试这些变种问题，它们都是建立在栈和队列的基础之上，但需要更巧妙的运用。