栈经典应用场景——数据结构系列教程(c++版)
梦想不会自己发光，真正闪耀的是那个为梦狂奔的你。献给知行的孩子们！（Eric.He著）
栈是「后进先出 (Last In First Out, LIFO)」的线性数据结构，核心特点：只能从栈顶插入元素（入栈 push）、只能从栈顶删除元素（出栈 pop）、只能查看栈顶元素。本文将详细讲解栈在括号匹配、进制转换、逆序处理、表达式求值、函数调用、迷宫求解中的应用，内容由浅入深，所有代码可直接编译运行。
栈的两种实现方式：
学习经典应用场景前，请根据上面的教程封装好自定义栈，所有场景实例直接复用
一、括号匹配校验
判断一个字符串中的括号是否合法匹配，是栈的标志性应用，也是大厂笔试高频题。
问题描述：
- 匹配规则：()、[]、{} 三种括号可以嵌套，但必须成对出现、正确闭合
- 合法示例：(1+2)*[3-{4/2}]、()、[]{}()
- 非法示例：(]、((()))]、{[)]、(
算法解析：
栈处理括号匹配的逻辑，完美贴合人的思维习惯，记住这个思路，所有括号题都能解：
- 遍历字符串中的每一个字符；
- 如果遇到 左括号(、[、{，直接入栈；
-
如果遇到 右括号)、]、}：
- 若此时栈为空 → 无左括号匹配，直接判定为【不合法】；
- 若栈不为空，出栈栈顶的左括号，判断是否和当前右括号「成对」；
- 若不成对 → 判定为【不合法】；
- 遍历结束后：只有栈为空，才算完全匹配合法（栈不为空说明有未闭合的左括号）。
#include <iostream>
#include"ArrayStack.h"
using namespace std;
// 括号匹配：核心函数，str为待校验字符串，合法返回1，非法返回0
int bracketMatch(char *str)
{
int len = strlen(str);
ArrayStack<char> stacks;
for (int i = 0; i < len; i++) {
char ch = str[i];
// 左括号：直接入栈
if (ch == '(' || ch == '[' || ch == '{') {
stacks.push(ch);
}
// 右括号：判断匹配
else if (ch == ')' || ch == ']' || ch == '}') {
char topCh;
if (stacks.isEmpty()) return 0; // 栈空，无左括号匹配
topCh = stacks.pop(); // 出栈栈顶的左括号
// 判断是否成对匹配
if ((ch == ')' && topCh != '(') ||
(ch == ']' && topCh != '[') ||
(ch == '}' && topCh != '{')) {
return 0;
}
}
// 其他字符（数字、字母、运算符）：直接跳过，不处理
}
return stacks.isEmpty();//栈空则完全匹配
}
// 测试案例
int main() {
char str1[] = "(1+2)*[3-{4/2}]"; // 合法
char str2[] = "{[)]"; // 非法
char str3[] = "((()))"; // 合法
char str4[] = "(()"; // 非法
printf("字符串 %s 的括号匹配结果：%s\n", str1, bracketMatch(str1)?"合法":"非法");
printf("字符串 %s 的括号匹配结果：%s\n", str2, bracketMatch(str2)?"合法":"非法");
printf("字符串 %s 的括号匹配结果：%s\n", str3, bracketMatch(str3)?"合法":"非法");
printf("字符串 %s 的括号匹配结果：%s\n", str4, bracketMatch(str4)?"合法":"非法");
return 0;
}
输出结果
字符串 (1+2)*[3-{4/2}] 的括号匹配结果：合法
字符串 {[)] 的括号匹配结果：非法
字符串 ((())) 的括号匹配结果：合法
字符串 (() 的括号匹配结果：非法
二、进制转换（十进制转任意进制，2/8/16 进制最常用）
进制转换是栈的经典应用，十进制整数 → 二进制 / 八进制 / 十六进制 是算法入门必练题。
问题描述：
- 十进制 10 → 二进制 1010
- 十进制 15 → 八进制 17
- 十进制 26 → 十六进制 1A
算法解析：
十进制转 N 进制的通用规则：除 N 取余，逆序输出余数
- 计算方式：用十进制数反复除以 N，记录每一次的余数，直到商为 0；
- 关键特点：最先得到的余数是目标进制的最低位，最后得到的余数是最高位 → 正好符合栈的「后进先出」！
- 栈的作用：把每次的余数入栈，最后依次出栈，就得到了「正序」的进制结果。
#include <iostream>
using namespace std;
// 进制转换：十进制num 转 base进制，base范围[2,16]
void decimalToAny(int num, int base) {
int sNumm = num;
if (base < 2 || base > 16) {
printf("进制数必须在2~16之间！\n");
return;
}
if (num == 0) { // 特殊值：0的任意进制都是0
printf("十进制0 转 %d进制 = 0\n", base);
return;
}
ArrayStack<int> stacks;
char hex[] = "0123456789ABCDEF"; // 十六进制的字符映射
int remainder; // 余数
// 核心：除base取余，余数入栈
while (num > 0) {
remainder = num % base;
stacks.push(remainder);
num = num / base;
}
// 余数出栈，逆序输出就是结果
printf("十进制%d 转 %d进制 = ", sNumm, base);
while (!stacks.isEmpty()) {
remainder = stacks.pop();
printf("%c", hex[remainder]);
}
printf("\n");
}
// 测试案例
int main() {
decimalToAny(10, 2); // 10 → 1010
decimalToAny(15, 8); // 15 → 17
decimalToAny(26, 16); // 26 → 1A
decimalToAny(0, 2); // 0 → 0
return 0;
}
输出结果
十进制10 转 2进制 = 1010
十进制15 转 8进制 = 17
十进制26 转 16进制 = 1A
十进制0 转 2进制 = 0
三、逆序处理
栈的「后进先出」特性，天生就是为逆序操作设计的，是实现逆序最简单的方式，无任何算法复杂度
问题描述：
- 字符串逆序："hello" → "olleh"
- 数组逆序：[1,2,3,4] → [4,3,2,1]
- 输入内容逆序输出：输入一串数字，倒序打印
算法解析：
三步走，无脑套用：
- 遍历需要逆序的内容（字符串 / 数组），把每个元素依次入栈；
- 依次出栈栈中的所有元素，按出栈顺序拼接 / 存储；
- 出栈的结果就是原内容的逆序。
#include <iostream>
using namespace std;
// 字符串逆序：利用栈实现
void reverseString(char *str) {
ArrayStack<char> stacks;
int len = strlen(str);
// 1. 所有字符入栈
for (int i = 0; i < len; i++) {
stacks.push(str[i]);
}
// 2. 出栈，覆盖原字符串，实现逆序
for (int i = 0; i < len; i++) {
str[i] = stacks.pop();
}
}
// 测试案例
int main() {
char str[] = "hello world";
printf("原字符串：%s\n", str);
reverseString(str);
printf("逆序后：%s\n", str); // olleh dlrow
return 0;
}
输出结果
原字符串：hello world
逆序后：dlrow olleh
四、表达式求值
如何让计算机正确计算数学表达式的值，需通过中缀表达式 转 后缀表达式 (逆波兰式) + 后缀求值的方式来实现。
问题描述：
- 计算 3+4*2-5、(1+2)*(3-4/2) 的值。
- 我们人类能看懂的表达式：a+b*c → 叫 中缀表达式（运算符在两个操作数中间）
- 计算机能直接计算的表达式：3 4 2 * + 5 - → 叫 后缀表达式 (逆波兰式)（运算符在两个操作数后面）
算法解析：
计算机无法直接处理中缀表达式的「运算符优先级」和「括号」，必须通过栈完成转换和计算，核心分两步，两步都依赖栈：
- 步骤 1：中缀表达式 转 后缀表达式（核心用栈存「运算符」）
- 遍历中缀表达式的每个字符；
- 遇到操作数：直接输出到后缀表达式；
- 遇到左括号：入栈；
- 遇到右括号：栈顶运算符依次出栈，直到遇到左括号，左括号出栈不输出；
- 遇到运算符 (+、-、*、/)：栈顶运算符优先级 ≥ 当前运算符 → 出栈输出，直到栈空 / 左括号，再将当前运算符入栈；
- 遍历结束，栈中剩余运算符全部出栈输出。
- 步骤 2：后缀表达式求值（核心用栈存「操作数」）
- 遍历后缀表达式的每个字符；
- 遇到操作数：直接入栈；
- 遇到运算符：出栈栈顶两个操作数，用运算符计算，计算结果重新入栈；
注意：先出栈的是右操作数，后出栈的是左操作数（比如 3 4 * → 计算 34 而不是 43）
- 遍历结束，栈中仅剩一个元素，就是表达式的最终结果。
总结：中缀转后缀 → 栈存【运算符】；后缀求值 → 栈存【操作数】
#include <iostream>
using namespace std;
// 判断是否为运算符
int ExpressionEvaluation::isOperator(char ch) {
return ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(' || ch == ')';
}
// 获取运算符优先级（优先级：() < +- < */）
int ExpressionEvaluation::getPriority(char op) {
switch (op) {
case '(': return 0;
case '+':
case '-': return 1;
case '*':
case '/': return 2;
default: return -1;
}
}
// 中缀表达式转后缀表达式
// 输入：中缀表达式字符串（如"3+4*2/(1-5)"）
// 输出：后缀表达式字符串（存储在postfix中）
void ExpressionEvaluation::infixToPostfix(char *infix, char *postfix) {
ArrayStack<char> opStack; // 运算符栈
int i = 0, j = 0; // i遍历中缀，j构建后缀
while (infix[i] != '\0') {
// 情况1：遇到数字（支持多位数）
if (isdigit(infix[i])) {
while (isdigit(infix[i])) {
postfix[j++] = infix[i++];
}
postfix[j++] = ' '; // 用空格分隔数字，方便后续计算
}
// 情况2：遇到左括号，直接入栈
else if (infix[i] == '(') {
opStack.push(infix[i]);
i++;
}
// 情况3：遇到右括号，弹出运算符直到左括号
else if (infix[i] == ')') {
while (opStack.getTop() != '(') {
postfix[j++] = opStack.pop();
postfix[j++] = ' ';
}
opStack.pop(); // 弹出左括号（不加入后缀）
i++;
}
// 情况4：遇到运算符
else if (isOperator(infix[i])) {
// 栈顶运算符优先级 >= 当前运算符，弹出栈顶到后缀
while (!opStack.isEmpty() && getPriority(opStack.getTop()) >= getPriority(infix[i])) {
postfix[j++] = opStack.pop();
postfix[j++] = ' ';
}
opStack.push(infix[i]); // 当前运算符入栈
i++;
}
// 跳过空格等无效字符
else {
i++;
}
}
// 弹出栈中剩余的运算符
while (!opStack.isEmpty()) {
postfix[j++] = opStack.pop();
postfix[j++] = ' ';
}
postfix[j-1] = '\0'; // 去掉最后一个空格，结束字符串
}
// 计算后缀表达式
//从左至右扫描表达式，如果当前字符为数字，则压栈，如果是运算符，则将栈顶两个元素弹出作相应运算，结果再入栈，最后当表达式扫描完后，栈里的就是结果。
// 输入：后缀表达式字符串（如"3 4 2 * 1 5 - / +"）
// 返回：计算结果（出错返回-99999）
int ExpressionEvaluation::calculatePostfix(char *postfix) {
ArrayStack<char> numStack; // 数字栈
int i = 0, num, a, b, res;
while (postfix[i] != '\0') {
// 情况1：遇到数字（解析多位数）
if (isdigit(postfix[i])) {
num = 0;
while (isdigit(postfix[i])) {
num = num * 10 + (postfix[i] - '0');
i++;
}
numStack.push(num);
}
// 情况2：遇到运算符（跳过空格后处理）
else if (isOperator(postfix[i])) {
// 弹出两个操作数（注意顺序：后弹出的是左操作数）
b = numStack.pop();
a = numStack.pop();
if (a == -1 || b == -1) { // 操作数不足
printf("表达式错误：操作数不足！\n");
return -99999;
}
// 计算
switch (postfix[i]) {
case '+': res = a + b; break;
case '-': res = a - b; break;
case '*': res = a * b; break;
case '/':
if (b == 0) { // 除数为0
printf("表达式错误：除数不能为0！\n");
return -99999;
}
res = a / b;
break;
default:
printf("表达式错误：未知运算符！\n");
return -99999;
}
numStack.push(res); // 结果入栈
i++;
}
// 跳过空格
else {
i++;
}
}
// 最终栈顶应为唯一结果
res = numStack.pop();
if (!numStack.isEmpty()) { // 操作数多余
printf("表达式错误：操作数多余！\n");
return -99999;
}
return res;
}
// 测试案例
int main() {
char infix1[] = "3+4*2-5"; // 中缀表达式1
char infix2[] = "(1+2)*(3-4/2) "; // 中缀表达式2
char postfix1[size(infix1)*2]; // 后缀表达式1
char postfix2[size(infix2)*2]; // 后缀表达式2
int postResult; //计算结果
infixToPostfix(infix1, postfix1);
printf("转换后的后缀表达式：%s\n", postfix1);
postResult = calculatePostfix(postfix1);
if (postResult != -99999) {
printf("后缀表达式计算结果：%d\n", postResult);
}
infixToPostfix(infix2, postfix2);
printf("转换后的后缀表达式：%s\n", postfix2);
postResult = calculatePostfix(postfix2);
if (postResult != -99999) {
printf("后缀表达式计算结果：%d\n", postResult);
}
return 0;
}
输出结果
中缀表达式：3+4*2-5
转换后的后缀表达式：3 4 2 * + 5 -
后缀表达式计算结果：6
中缀表达式：(1+2)*(3-4/2)
转换后的后缀表达式：1 2 + 3 4 2 / - *
后缀表达式计算结果：3
五、函数调用
栈是计算机底层的核心应用，也是最容易被忽略的重要场景：所有编程语言（C/C++/Java/Python）在程序运行时的函数调用，底层都是用栈实现的。
问题描述：
- 在 C 语言中函数调用顺序为 A() → B() → C()，函数的执行顺序是 C () 执行完 → B () 执行完 → A () 执行完。
算法解析：
程序运行时，系统会为其分配一块内存，这块内被分区为：全局/静态区、常量区、栈区、堆区
- 全局/静态区：用于存放全局变量、静态变量以及未初始化的全局变量（BSS段），这些数据在程序启动时分配，生命周期贯穿整个程序运行期间。
- 常量区：专门存储字符串常量、字面量等不可修改的数据，其内容在程序运行期间保持不变。
- 栈区：由系统自动管理，用于存储函数调用时的局部变量、参数、返回地址等信息，内存分配和释放遵循后进先出（LIFO）原则，随着函数调用的嵌套而动态增长或收缩。
- 堆区：是动态内存分配区域，程序员通过malloc、free（C语言）或new、delete（C++）等操作手动管理内存，适用于运行时才能确定大小的数据结构（如链表、树节点）。
函数执行时的逻辑：
- 调用函数时 → 函数的栈帧入栈，栈顶永远是「正在执行的函数」；
- 函数执行完毕 → 该函数的栈帧出栈，释放内存；
- 递归调用的本质：就是函数不断入栈，直到触发递归终止条件，再依次出栈。
当递归调用的层数过多时，栈帧会不断入栈，超出栈的内存容量，就会触发栈溢出 (Stack Overflow)
这也是为什么递归解法有时需要改成非递归（迭代），本质是手动控制栈的大小，避免系统栈溢出。
#include <iostream>
using namespace std;
// 无限递归，会触发栈溢出
void recursion() {
recursion();
}
// 测试案例
int main() {
recursion();
return 0;
}
输出结果
Process returned -1073741571 (0xC00000FD) execution time : 1.380 s
六、迷宫求解
栈是深度优先搜索 (DFS) 的底层实现，DFS 是解决「迷宫寻路、排列组合、子集问题」的核心算法
问题描述：
- 迷宫中从起点到终点的路径查找；
算法解析：
深度优先搜索的特点：一条路走到黑，走不通就回头，这个「回头」的操作，就是栈的「出栈」，完美贴合栈的特性；
- 从起点出发，把当前位置入栈，标记为已访问；
- 向四周探索可走的方向，找到未访问的位置 → 入栈，继续探索；
- 走到死胡同（无任何可走方向）→ 当前位置出栈，回到上一个位置，继续探索其他方向；
- 直到找到终点，或栈空（无路径）。
#include <iostream>
#include"ArrayQueue.h"
using namespace std;
// 迷宫坐标结构体（存储x,y坐标+步数）
struct Pos{
int x;
int y;
int step;
};
// ===================== 2. DFS+栈 实现迷宫最短路径 =====================
// maze：迷宫数组，rows/cols：迷宫行列数，sx/sy：起点，ex/ey：终点
int mazeShortestPathDfs(int maze[][5], int rows, int cols, int sx, int sy, int ex, int ey) {
// 边界校验
if (sx < 0 || sx >= rows || sy < 0 || sy >= cols ||
ex < 0 || ex >= rows || ey < 0 || ey >= cols ||
maze[sx][sy] == 1 || maze[ex][ey] == 1) {
return -1; // 起点/终点非法
}
if (sx == ex && sy == ey) {
return 0; // 起点即终点
}
ArrayStack<Pos> stack;
int visited[500][500] = {{0}}; // 标记是否访问过
int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; // 上下左右
vector<int> allSteps; // 存储所有有效路径的步数
// 起点入队
stack.push({sx, sy, 0});
visited[sx][sy] = 1;
while (!stack.isEmpty()) {
Pos cur = stack.pop();
// 遍历四个方向
for (int i = 0; i < 4; i++) {
int nx = cur.x + dirs[i][0];
int ny = cur.y + dirs[i][1];
// 到达终点，记录当前路径步数+1
if (nx == ex && ny == ey) {
allSteps.push_back(cur.step + 1);
continue; // 找到一条路径，继续找其他路径
}
// 新坐标合法且可走、未访问
if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && maze[nx][ny] == 0 && !visited[nx][ny]) {
visited[nx][ny] = 1;
stack.push({nx, ny, cur.step + 1});
}
}
}
// 筛选最短步数
if (!allSteps.empty()) {
int minStep = INT_MAX;
for (int step : allSteps) {
if (step < minStep) {
minStep = step;
}
}
return minStep;
} else {
return -1; // 无有效路径
}
}
// 测试案例
int main() {
// 迷宫示例：5行5列，0可走，1墙
int maze[5][5] = {
{0, 1, 0, 0, 0},
{0, 1, 0, 1, 0},
{0, 0, 0, 1, 0},
{1, 1, 0, 1, 0},
{0, 0, 0, 0, 0}
};
int sx = 0, sy = 0; // 起点(0,0)
int ex = 4, ey = 4; // 终点(4,4)
int minStep = mazeShortestPath(maze, 5, 5, sx, sy, ex, ey);
if (minStep == -1) {
printf("迷宫无有效路径！\n");
} else {
printf("迷宫从(%d,%d)到(%d,%d)的最短步数：%d\n", sx, sy, ex, ey, minStep); // 预期：8
}
return 0;
}
输出结果
迷宫从(0,0)到(4,4)的最短步数：8
七、总结
- 栈是算法的基石，没有栈，就没有表达式求值、没有 DFS、没有函数调用，本文的 6 个场景是栈的核心高频应用，优先级排序：
- 括号匹配 > 进制转换 > 逆序处理 > 表达式求值 > 函数调用栈 > 迷宫 DFS
- 所有场景的代码都基于同一个栈的封装，学会栈的基础操作后，所有应用场景都是「换汤不换药」，掌握规律后，栈的所有题目都能轻松解决！
返回顶部