在系统编程和算法设计的广阔领域中，线性数据结构构成了我们逻辑大厦的基石。而在这些结构中，栈和队列无疑是最具辨识度且应用最广泛的两种。你是否想过，为什么你的浏览器点击“后退”能回到上一页？或者为什么操作系统的任务调度能井井有条？这背后往往都有着栈或队列的身影。
栈遵循 LIFO（Last In First Out，后进先出）的原则，这就好比我们在洗碗时，最后洗干净的盘子通常会被放在最上面，而我们也是最先拿走最上面的盘子。相比之下，队列遵循 FIFO（First In First Out，先进先出）的原则，这更像是我们在排队买票，先来的人先买，后来的人排在队尾。
在这篇文章中，我们将不仅仅是停留在定义的表面。我们将深入研究一系列核心的 C/C++ 练习题，通过实际编写代码和剖析逻辑，来彻底掌握这两种数据结构。 无论你是准备技术面试，还是希望优化自己的代码架构，这些实战经验都将为你提供坚实的基础。
为什么选择 C/C++？
在探讨具体问题之前，值得强调的是，C 和 C++ 为我们提供了对内存管理的极致控制。我们可以手动分配和释放内存，也可以通过标准模板库（STL）利用高度优化的容器。在下面的示例中，我不仅会展示如何使用 STL 的 INLINECODEe154b10a 和 INLINECODE439d999c（因为在实际开发中这更高效、更安全），也会在必要时展示底层实现，帮助你理解“魔法”背后的原理。
前置知识要求：你需要对指针、数组和基本的 C++ 类模板有一定的了解。
一、 核心实战：栈的应用
栈的特点是“在一端进行插入和删除”，这使得它非常适合处理具有“回溯”性质或“匹配”性质的问题。让我们通过几个具体的例子来看看。
#### 1. 简单但经典：检查括号是否平衡
这是几乎每场编程面试的必考题。给定一个包含 INLINECODE9da25f21, INLINECODE075a5230, INLINECODE9e46b964 的字符串，我们需要判断它是否是“合法”的。例如，INLINECODE76894933 是合法的，而 {[(])} 则不是。
解题思路：
我们可以利用栈的 LIFO 特性。当我们遇到一个左括号（如 {）时，我们把它压入栈中，期待着后面能有一个匹配的右括号。当我们遇到一个右括号时，它必须与栈顶的左括号类型一致。如果匹配，我们就将栈顶弹出；如果不匹配或栈为空，说明字符串非法。最后，如果栈是空的，说明所有括号都完美匹配。
代码实现：
#include
#include
#include
using namespace std;
// 判断字符是否匹配的辅助函数
bool isMatching(char open, char close) {
if (open == ‘(‘ && close == ‘)‘) return true;
if (open == ‘{‘ && close == ‘}‘) return true;
if (open == ‘[‘ && close == ‘]‘) return true;
return false;
}
bool isBalanced(string expr) {
stack s;
for (char c : expr) {
// 如果是左括号，压入栈
if (c == ‘(‘ || c == ‘{‘ || c == ‘[‘) {
s.push(c);
}
// 如果是右括号，进行检查
else if (c == ‘)‘ || c == ‘}‘ || c == ‘]‘) {
// 如果栈为空（没有对应的左括号），或者栈顶不匹配，返回false
if (s.empty() || !isMatching(s.top(), c)) {
return false;
}
// 匹配成功，弹出栈顶
s.pop();
}
}
// 遍历结束后，栈如果为空则说明完全匹配
return s.empty();
}
int main() {
string expr = "{[()]}";
if (isBalanced(expr))
cout << "表达式平衡" << endl;
else
cout << "表达式不平衡" << endl;
return 0;
}
关键点： 注意 INLINECODE311beb9f 的检查。如果我们漏掉这个检查，当字符串以 INLINECODEf7733ed4 开头时，直接调用 s.top() 会导致程序崩溃。这是处理栈问题时常犯的错误。
#### 2. 进阶挑战：使用栈反转字符串
虽然我们可以用简单的双指针法来反转字符串，但使用栈来反转是理解其工作原理的绝佳方式。
思路： 将字符串中的每个字符依次压入栈中。由于栈是后进先出的，当我们依次弹出字符时，得到的顺序就是原字符串的逆序。
#include
#include
#include
using namespace std;
void reverseString(string &str) {
stack s;
// 1. 将所有字符压入栈
for (char c : str) {
s.push(c);
}
// 2. 修改字符串内容，通过弹出栈中元素
for (int i = 0; i < str.length(); i++) {
str[i] = s.top();
s.pop();
}
}
int main() {
string str = "HelloWorld";
reverseString(str);
cout << "反转后的字符串: " << str << endl; // 输出: dlroWolleH
return 0;
}
#### 3. 中等难度：中缀表达式转后缀表达式
在计算机科学中，计算 INLINECODEe3c4e27c 比较麻烦，因为要考虑运算符优先级。但如果将其转换为后缀表达式（逆波兰表示法），如 INLINECODE3e18a1c6，计算就变得非常简单：遇到数字就入栈，遇到运算符就弹出栈顶两个元素计算。
如何将中缀转后缀？我们需要两个栈：一个存放输出结果（可以用字符串模拟），一个存放运算符（Ops栈）。
算法规则：
- 遍历中缀表达式。
- 遇到操作数，直接加入输出。
- 遇到左括号
(，压入 Ops 栈。 - 遇到右括号
)，将 Ops 栈顶元素弹出并加入输出，直到遇到左括号为止。 - 遇到运算符（如 INLINECODE5d186378, INLINECODE3a7070d1）：如果 Ops 栈为空，压入；否则，比较优先级。如果栈顶元素优先级 >= 当前元素，则弹出栈顶（因为栈顶要先算），直到栈顶优先级 < 当前元素或栈为空。最后将当前运算符压入。
- 遍历结束后，将 Ops 栈中剩余元素全部弹出加入输出。
代码片段：
// 这是一个简化的逻辑演示，实际实现需要注意空格处理和多位数字
int precedence(char op) {
if (op == ‘+‘ || op == ‘-‘) return 1;
if (op == ‘*‘ || op == ‘/‘) return 2;
return 0;
}
// 假设输入已经是空格分隔的 token 或者逻辑处理过
// 核心逻辑展示：
// if (isOperand(token)) output += token;
// else if (token == ‘(‘) ops.push(token);
// else if (token == ‘)‘) { while(ops.top() != ‘(‘) { output += ops.top(); ops.pop(); } ops.pop(); }
// else { while(!ops.empty() && precedence(ops.top()) >= precedence(token)) { output += ops.top(); ops.pop(); } ops.push(token); }
二、 探索队列：从FIFO到复杂流控
队列在处理异步任务、广度优先搜索（BFS）以及缓冲区设计中至关重要。除了标准的 FIFO 队列，我们还会接触一些变种。
#### 1. 栈排序：只用一个额外的栈
这是一个非常有趣的面试题：给定一个栈，如何将其中的元素按从大到小的顺序排序，且只允许使用一个额外的栈？
策略：
我们可以想象这两个栈为 INLINECODEaeb96b77 和 INLINECODE4b03f02a。
- 我们要把 INLINECODE1d09c3aa 里的数移动到 INLINECODEe14d575a 中，但要保持
tmp是有序的（假设栈底最大，栈顶最小）。 - 从 INLINECODEed0d941e 弹出一个元素 INLINECODEd70e37a9。
- 比较 INLINECODE23496dc6 与 INLINECODEc42097df 栈顶的元素。
- 如果 INLINECODE88260516 为空或 INLINECODEa00edcc0 栈顶 <= INLINECODE21ea6c42，直接压入 INLINECODE8c089aae。
- 如果 INLINECODE1c56ef66 栈顶 > INLINECODE82220618，说明 INLINECODE92400125 应该在更下面。我们需要不断把 INLINECODE829eafd2 的栈顶弹回 INLINECODE94228dd0，直到找到合适的位置，然后把 INLINECODE3927f85a 压入 INLINECODEdadf4065，最后再把刚才弹回 INLINECODE515f7390 的元素重新压回
tmp。
这个算法的时间复杂度是 O(N^2)，但在空间限制严格的情况下非常有效。
#### 2. 股票跨度问题
这是典型的单调栈应用场景。给定一个每日股票价格的数组，我们需要计算每一天的价格跨度（即价格连续小于或等于今天价格的天数，包括今天）。
直观想法： 对每一天，向前遍历比较。时间复杂度 O(N^2)。
优化思路（单调栈）： 维护一个栈，栈中存放的不仅仅是价格，而是包含价格和跨度信息的结构体。或者更简单地，我们在栈中存放索引。
- 遍历价格数组。
- 当栈不为空，且当前价格 >= 栈顶索引对应的价格时，说明栈顶这一天被当前天“压制”了，我们可以弹出栈顶，因为对于后面的天数来说，当前天比栈顶那天更近且价格更高（或相等），更具参考价值。
- 如果栈空了，说明当前价格是最高的，跨度是
i + 1。 - 如果栈不为空，跨度是
i - stack.top()。
这个问题展示了栈在处理“下一个更大元素”这类问题时的威力。
三、 综合难度与最佳实践
在掌握了基础之后，我们会遇到一些极具挑战性的题目，例如 “直方图中的最大矩形面积”。这道题目要求我们在给定的一系列柱状图中，找出能构成的最大矩形面积。
核心技巧： 这里的难点在于，对于每一根柱子，我们要找到它左边第一根比它矮的和右边第一根比它矮的柱子。这实际上是两次“下一个更小元素”的查找。通过维护一个单调递增栈，我们可以在 O(N) 的时间内解决这个问题。
#### C++ 代码实现中的注意事项
作为一名开发者，在使用这些数据结构时，有几点经验我想分享给你：
- 内存管理：如果你使用的是 C 语言的数组模拟栈，请务必小心 INLINECODEd6016491（栈溢出）。总是要在 INLINECODE149a8e8e 操作前检查 INLINECODE92a37930 指针是否越界。而在 C++ 中，INLINECODE9dd941cc 和 INLINECODEe89233b1 会自动处理内存，但在极端性能敏感的场景下，预先 INLINECODE28f67759 容器的空间可以减少动态分配的开销。
- STL 的选择：
– INLINECODEa4d48f8b 和 INLINECODE0ae03dc1 是容器适配器。它们默认使用 INLINECODEe9255558 作为底层容器。INLINECODEe07e960f 在随机访问和两端增删上都表现不错。
– 如果你的数据结构只需要在两端操作，且不需要随机访问，std::list 也是一个选择。
– 避免使用 INLINECODEb904ae5c 作为 INLINECODEbec3ac56 的底层容器，因为 vector 的头部删除操作效率极低。
- 调试技巧：调试栈和队列最容易的问题是“状态丢失”。在打印调试信息时，尽量打印整个快照，而不仅仅是栈顶元素，这能帮你发现逻辑错误。
总结与后续步骤
在这篇文章中，我们一起探讨了 C/C++ 中栈和队列的多种实现与应用，从最简单的括号匹配到复杂的直方图计算。我们看到，栈不仅仅是“后进先出”的简单容器，它是处理递归、回溯和单调性问题的利器；而队列则是我们构建并发系统和层级遍历（BFS）的基础。
你现在可以尝试以下步骤来巩固你的知识：
- 实践：不要只看代码。自己手写实现一个“两个栈模拟队列”的类，深入理解 INLINECODEaf7bd8dd 和 INLINECODEfa1aed0c 的均摊复杂度。
- 探索：尝试解决我们列表中的“困难”级问题，比如“接雨水”问题，它结合了双指针和栈的思维，是提升算法感觉的绝佳题目。
代码的世界里，数据结构是骨架，算法是灵魂。掌握了栈与队列，你就已经拥有了构建复杂系统的关键工具。让我们继续保持对技术的好奇心，去探索更深层的设计模式吧！