栈在括号匹配中的应用

  1. // 数据结构
  2. #define MaxSize 10
  3. typedef struct {
  4.     char data[MaxSize];
  5.     int top;  // 栈顶指针
  6. } SqStack;
  7. // 初始化栈
  8. void InitStack(SqStack &S)
  9. // 判断栈是否为空
  10. bool StackEmpty(SqStack S) 
  11. // 入栈
  12. bool Push(SqStack &S, char x) 
  13. // 出栈
  14. bool Pop(SqStack &S, char &x)
  1. // 括号匹配
  2. bool bracketCheck(char str[], int length) {
  3.     SqStack S;
  4.     InitStack(S);
  5.     for (int i = 0; i < length; i++) {
  6.         if (str[i] == '(' || str[i] == '[' || str[i] == '{') {
  7.             Push(S, str[i]);  // 扫描左括号入栈
  8.         } else {
  9.             if (StackEmpty(S)) {  // 扫描右括号，如果栈空
  10.                 return false;     // 匹配失败
  11.             }
  12.             char topElem;
  13.             Pop(S, topElem);  // 栈顶元素出栈
  14.             if (str[i] == ')' && topElem != '(') {
  15.                 return false;
  16.             }
  17.             if (str[i] == ']' && topElem != '[') {
  18.                 return false;
  19.             }
  20.             if (str[i] == '}' && topElem != '{') {
  21.                 return false;
  22.             }
  23.         }
  24.     }
  25.     return StackEmpty(S);  // 检查完全部括号后，栈空说明匹配成功
  26. }
  27. // BracketCheck.cpp

栈在表达式求值的应用

算数表达式

算数表达式由三个部分组成：操作数、运算符、界限符（即括号，反映计算的先后顺序）

  • 中缀表达式：运算符在两个操作数的中间，如 a + b，a + b - c，a + b - c * d
  • 后缀表达式：运算符在两个操作数的后面，如 a b +，a b + c - ，a b + c d * -
  • 前缀表达式：运算符在两个操作数的前面，如 + a b，- + a b c ，- + a b * c d

    中缀转后缀

    中缀转后缀的手算方法：
  1. 确定中缀表达式中各个运算符的运算顺序
  2. 选择下一个运算符，按照「左操作数 右操作数 运算符」的方式组合成一个新的操作数
  3. 如果还有运算符没被处理，就继续步骤2

注意：保证手算和计算机算结果相同，需要遵循“左优先”原则，即只要左边的运算符能先计算就优先计算左边的。（可以保证运算顺序唯一）

中缀转后缀的机算方法：

  • 初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。
  • 从左到右处理各个元素，直到末尾。可能遇到三种情况：
    • 遇到操作数。直接加入后缀表达式
    • 遇到界限符。遇到 ( 直接入栈；遇到 ) 则依次弹出栈内运算符并加入后缀表达式，直到弹出 ( 为止。注意：) 不加入后缀表达式。
    • 遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到 ( 或栈空则停止。之后再把当前运算符入栈。
  • 按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。

后缀表达式结果的手算方法：从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应运算，合体为一个操作数。

用栈实现后缀表达式的计算：

  1. 从左往右扫描下一个元素，直到处理完所有元素
  2. 若扫描到操作数则压入栈，并回到步骤1；否则执行步骤3

  3. 若扫描到运算符，则弹出两个栈顶元素（先出栈的是“右操作数”），执行相应运算，运算结果压回栈顶，回到步骤1

    中缀转前缀

    前缀表达式较后缀表达式用的较少
    中缀转前缀的手算方法：

  4. 确定中缀表达式中各个运算符的运算顺序

  5. 选择下一个运算符，按照「运算符 左操作数 右操作数」的方式组合成一个新的操作数
  6. 如果还有运算符没被处理，就继续步骤2

注意：同样为保证手算和计算机算结果相同，需要遵循“右优先”原则，即只要右边的运算符能先计算，就优先算右边的。

用栈实现前缀表达式的计算：

  1. 从右往左扫描下一个元素，直到处理完所有元素
  2. 若扫描到操作数则压入栈，并回到步骤 1；否则执行步骤 3

  3. 若扫描到运算符，则弹出两个栈顶元素（先出栈的是“左操作数”），执行相应运算，运算结果压回栈顶，回到步骤 1

    中缀表达式的计算

    用栈实现中缀表达式的计算（中缀转后缀+后缀表达式求值）：

  4. 初始化两个栈，操作数栈和运算符栈

  5. 若扫描到操作数，压入操作数栈
  6. 若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈（期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再压回操作数栈）

TODO 中缀表达式的计算的代码实现

栈在递归的应用

函数调用的特点：最后被调用的函数最先执行结束（LIFO）

函数调用时，需要用一个栈存储：调用返回地址；实参；局部变量

适合用“递归”算法解决：可以把原始问题转换为属性相同，但规模较小的问题。必须注意递归模型不能是循环定义的，其必须满足下面的两个条件，即递归表达式（递归体）和边界条件（递归出口）。

缺点：太多层递归可能会导致栈溢出

例如，计算正整数的阶乘 栈和队列的应用 - 图1 ：

栈和队列的应用 - 图2%3D%5Cbegin%7Bcases%7D%0A%20%20n*%5Cmathrm%7Bfactorial%7D(n-1)%2C%20%26%20n%3E1%20%5C%5C%5C%5C%20%20%0A%20%201%2C%20%26%20n%3D1%20%5C%5C%5C%5C%0A%20%201%2C%20%26%20n%3D0%0A%5Cend%7Bcases%7D#card=math&code=%5Cmathrm%7Bfactorial%7D%28n%29%3D%5Cbegin%7Bcases%7D%0A%20%20n%2A%5Cmathrm%7Bfactorial%7D%28n-1%29%2C%20%26%20n%3E1%20%5C%5C%5C%5C%20%20%0A%20%201%2C%20%26%20n%3D1%20%5C%5C%5C%5C%0A%20%201%2C%20%26%20n%3D0%0A%5Cend%7Bcases%7D&id=xvEGD)

// 计算正整数 n!
#include <iostream>
using namespace std;

int factorial(int n) {
    if (n == 0 || n == 1) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

int main() {
    int x = factorial(3);
    printf("%d", x);
}

求斐波那契数列：

栈和队列的应用 - 图3%3D%5Cbegin%7Bcases%7D%0A%20%20%5Cmathrm%7BFib%7D(n-1)%2B%5Cmathrm%7BFib%7D(n-2)%2C%20%26%20n%3E1%20%5C%5C%5C%5C%20%20%0A%20%201%2C%20%26%20n%3D1%20%5C%5C%5C%5C%0A%20%200%2C%20%26%20n%3D0%0A%5Cend%7Bcases%7D#card=math&code=%5Cmathrm%7BFib%7D%28n%29%3D%5Cbegin%7Bcases%7D%0A%20%20%5Cmathrm%7BFib%7D%28n-1%29%2B%5Cmathrm%7BFib%7D%28n-2%29%2C%20%26%20n%3E1%20%5C%5C%5C%5C%20%20%0A%20%201%2C%20%26%20n%3D1%20%5C%5C%5C%5C%0A%20%200%2C%20%26%20n%3D0%0A%5Cend%7Bcases%7D&id=eXls7)

// 计算斐波那契数列
#include <iostream>
using namespace std;

int Fib(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        return Fib(n - 1) + Fib(n - 2);
    }
}

int main() {
    for (int i = 0; i <= 10; i++) {
        printf("%d,", Fib(i));
    }
}

栈和队列的应用 - 图4

显然，在递归调用的过程中，Fib(3) 被计算了2次，Fib(2) 被计算了3次。Fib(1) 被调用了5次，Fib(0)被调用了3次。所以，递归的效率低下，但优点是代码简单，容易理解。

可以将递归算法转换为非递归算法，通常需要借助找来实现这种转换。

队列在层次遍历中的应用

层次遍历二叉树的过程：

  1. 根节点入队
  2. 若队空（所有结点都已处理完毕），则结束遍历；否则重复步骤3操作。
  3. 队列中第一个结点出队，并访问之。若其有左孩子，则将左孩子入队；若其有右孩子，则将右孩子入队，返回步骤2。

栈和队列的应用 - 图5

队列在图的广度优先遍历的应用

详见“图”章节，思想类似于树的层次遍历

队列在计算机系统中的应用

多个进程争抢着使用有限的系统资源时，FCFS ( First Come First Service）先来先服务是一种常用策略。