【408考研】数据结构 —— 栈和队列的应用

栈和队列的应用

栈的应用

括号匹配

• 使用到的数据结构是栈

• 关于表达式中的括号匹配问题：有左括号和右括号之分，左右括号组成一对括号，即左括号要匹配右括号。

• 

  • 即出现一个右括号就要消耗一个左括号

  • 

  • 依次扫描所有字符，遇到左括号就入栈，遇到右括号就出栈。

• 匹配失败的情况

  • 左括号不成对匹配
  • 右括号不成对匹配
  • 左右括号不成对匹配

• 代码实现

  • bool brackerCheck(char str[], int length){
        SqStack S;    //声明一个栈, 本质是指向一个结构体的指针
        InitStack(S);  //初始化栈
        for(int i=0;i<length;i++){
            if(str[i]=='('||str[i]=='['||str[i]=='{'){  //判断左括号
                Push(S,str[i]);  //是左括号进栈
            }else{   //否则是右括号
                if(StackEmpty(S)){  //判断栈是否为空
                    return false;   //若为空则匹配失败
                }
            	char topElem;
                Pop(S,topElem); // 将栈顶元素出栈
                if(str[i]==')' && topElem!='('){
                    return false; //匹配失败
                }else if(str[i]==']'&&topElem!='['){
                    return false; //匹配失败
                }else if(str[i]=='}'&&topElem[i]!='{'){
                    return false;  //匹配失败
                }
            }
        }
        return StackEmpty(S);  //检索完后栈为空, 则匹配完成
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23

表达式求值

表达式求值是程序设计语言编译中的一个最基本问题

三种算术表达式

算术表达式由三个部分组成： 操作数、运算符、界限符

• 操作数：进行运算的数字，运算符作用于的实体
• 运算符：进行运算的符号，用于执行程序代码运算，会针对一个或者两个以上操作数项目来进行运算
• 界限符：反映计算的先后顺序(比如括号里面的先计算)

• 中缀表达式 ：运算符在两个操作数中间。 比如：a+b、a×b+c、a+b-c÷d。正常的书写格式((大白话就是正常人能看懂的表达式))。
• 后缀表达式 ：也叫逆波兰表达式（Reverse Polish notation），运算符在两个操作数后面。 比如：ab+、ab×c+、ab+cd÷-
• 前缀表达式 ：也叫波兰式表达式（Polish notation），运算符在两个操作数前面。比如：+ab、×ab+c、-+ab÷cd

后缀表达式的计算

后缀表达式计算用计算机计算的原理：

使用栈来实现计算

1. 从左往右扫描后缀表达式中的元素，直到所有的元素被处理完
2. 若扫描到的元素是操作数，则将其入栈，返回第1步，否则执行第3步
3. 若扫描到的元素是运算符，则将依次弹出两个栈顶元素，并与运算符进行运算，在将计算结果压入栈顶，再回到第1步

注: 只有操作数才进栈, 运算符不进栈

举个栗子：

后缀表达式为 AB+CD*E/-F+

转为中缀表达式(大白话就是人能看懂的表达式)为(A+B)-((C*D)/E)+F

注意 : 中序遍历的结果并不是中缀表达式, 因为中缀表达式中可能有界限符，可能需要添加括号来改变运算顺序。比如该例子的中序遍历为 A+B-C*D/E+F, 转为中缀表达式要加括号（界限符）来区分运算的先后顺序 $\to$ (A+B)-((c*D)/E)+F

人工手算后缀表达式的结果:

两种方法：

第一种：先转换为中缀表达式再用中缀表达式计算出结果

第二种：直接计算，从左到右扫描后缀表达式，每遇到一个运算符则弹出两个栈顶元素运算后再入栈。（注：先弹出栈的元素是右操作数，虽然加法和乘法不影响最后的结果，但是减法和除法的右操作数和左操作数不同会影响最终的计算结果）

举个栗子 ：

• 计算机使用栈来实现后缀表达式的计算

  

• 注意出栈的左右操作数的位置

中缀表达式与后缀表达式互转

“左优先”原则：只要左边的运算符能先计算就先计算，即先按运算顺序优先，若运算的顺序不要求的话，则按从左到右进行计算。 （这样能保证手算和机器算的顺序一致）

举个栗子：比如 a+b*c-d, 先按照运算的优先顺序，先计算乘法再计算加法后减法。注意：虽然先算减法再算加法的结果不会有错， 但是后缀表达式的顺序会发生改变。

• 中缀表达式 $\Rightarrow$ 后缀表达式
  • 按照“左优先”原则确定运算符的运算次序
  • 根据确定的次序，依次将各个运算符和与之相邻的两个操作数，按《左操作数 右操作数 运算符》的规则排序。
• 后缀表达式 $\Rightarrow$ 中缀表达式
  • 从左到右扫描后缀表达式，每遇到一个运算符就将《左操作数 右操作数 运算符》变为《左操作数 运算符 右操作数》的规则。

画出对应的二元树， 通过后序遍历即可转成后缀表达式；通过眼瞅即可写出对应的中缀表达式， 从叶子结点开始到根结点。

---

剑指 Offer II 036. 后缀表达式

根据 逆波兰表示法，求该后缀表达式的计算结果。

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

• 整数除法只保留整数部分。
• 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1：

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
1
2
3
4
5

示例 2：

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
1
2
3
4
5

示例 3：

输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：
该算式转化为常见的中缀算术表达式为：
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
1
2
3
4
5
6
7
8
9
10
11
12
13

提示：

1 <= tokens.length <= 104
tokens[i] 要么是一个算符（“+”、“-”、“*” 或 “/”），要么是一个在范围 [-200, 200] 内的整数

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/8Zf90G

LeetCode官方题解：（C语言版）

bool isNumber(char* token) {
    return strlen(token) > 1 || ('0' <= token[0] && token[0] <= '9');
}

int evalRPN(char** tokens, int tokensSize) {
    int n = tokensSize;
    int stk[n], top = 0;
    for (int i = 0; i < n; i++) {
        char* token = tokens[i];
        if (isNumber(token)) {
            stk[top++] = atoi(token);
        } else {
            int num2 = stk[--top];
            int num1 = stk[--top];
            switch (token[0]) {
                case '+':
                    stk[top++] = num1 + num2;
                    break;
                case '-':
                    stk[top++] = num1 - num2;
                    break;
                case '*':
                    stk[top++] = num1 * num2;
                    break;
                case '/':
                    stk[top++] = num1 / num2;
                    break;
            }
        }
    }
    return stk[top - 1];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

---

中缀表达式与前缀表达式互转

• 中缀表达式 $\Rightarrow$ 前缀表达式
  1. 按“右优先”原则确定运算符的运算次序
  2. 上面确定的次序，依次将各个运算符和与之相邻的两个操作数按 《运算符 左操作数 右操作数》 的规则排序
• 举个栗子 ：
  • 中缀表达式: A+B*(C-D)-E/F
  • 转成前缀表达式 : -+A*B-CD/EF
  • 

前缀表达式的计算

前缀表达式计算用计算机计算的原理：

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

1. 从右往左扫描前缀表达式中的元素， 直到处理完所有元素
2. 若扫描到操作数则压入栈，并回到步骤1；否则执行步骤3
3. 若扫描到运算符，则弹出两个栈顶元素，执行相应运算，结果压回栈顶，回到步骤1。注意 : 先弹出的元素是"左操作数"，与后缀表达式相反， 后缀表达式的计算是先从栈内弹出的元素是“右操作数”。

前缀表达式和后缀表达式的计算相似，都是用栈来进行计算，并且都是操作数先进栈，遇到运算符出栈。不同之处是前缀表达式最先出栈的是左操作数和后缀表达式最先出栈的是右操作数。

中缀表达式转前缀表达式和中缀表达式的不同是：

• 中缀转后缀是从左往右扫描中缀表达式
• 中缀转前缀是从右往左扫描中缀表达式

中缀表达式的计算（用栈实现）

• 需要用到两个栈，一个叫操作数栈：存放操作数的，另一个叫运算符栈：存放运算符的。
• 从左到右扫描中缀表达式，若
• 初始化两个栈，操作数栈和运算符栈
• 若扫描到操作数，将其压入操作数栈
• 若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈（即按后缀表达式的顺序将运算符压入栈内）

过程相对繁琐，这里就不展开叙述了， 不在408考察范围内， 关键点在于后缀表达式。

注意 : 前缀和后缀表达式中是没有界限符的，是因为他们的表达式已经按计算的先后顺序排好了；而中缀表达式不一样， 是可以有界限符的，用来区分计算的先后顺序，比如先算括号内的，再按乘除加减的先后顺序进行计算！

递归

• 若一个函数、过程或者数据结构的定义中由调用了自身，则这个函数、过程或者数据结构称为递归定义，也简称递归。

• 它通常把一个大型的复杂问题层层转化为一个与原问题相似的规模较小的问题来求解。

• 在递归调用过程中，系统自动开辟了递归调用栈来进行数据存储。若将递归算法转为非递归算法就需要我们自己使用栈来实现转换。

• 仅少量代码就可以进行多次重复计算，大大减少了程序的代码量

• 但是效率并不是很高！原因是递归调用过程包含了很多重复的计算

典型的例子 ： 斐波那契数列

F i b ( n − 1 ) = { F i b ( n − 1 ) + F i b ( n − 2 ) , n > 1 1 , n = 1 0 , n = 0 Fib(n-1)=

Fib(n−1)=⎩ ⎨ ⎧​Fib(n−1)+Fib(n−2),n>11,n=10,n=0​

C语言程序实现:

int Fib(int n){
    if(n==0){  //边界条件
        return 0;
    }else if(n==1){ //边界条件
        return 1;      
    }else{
        return Fib(n-1)+Fib(n-2);  //递归表达式, 自身调用自身
    }
}
1
2
3
4
5
6
7
8
9

注意 :

• 递归表达式 (递归题)

• 边界条件 (递归出口)

递归的精髓在于能否将原始问题转换为属性相同但规模较小的问题。

队列的应用

层次遍历

• 二叉树的层次遍历使用队列进行遍历
• 使用队列是为了保存下一步的处理顺序
• 用队列遍历的过程
  1. 根结点入队。
  2. 若队空(所有结点都已经处理完毕)，则结束遍历；否则重复第3步。
  3. 队列中第一个结点入队，并访问之。若其有左孩子，则将左孩子入队；若有右孩子则将右孩子入队，返回第2步。

举个栗子 ：

1. 

2. 

3. 

4. 

5. 

6. 

7. 

8. 

9. 

在计算机系统中的应用

• 解决主机与外部设备之间的速度不匹配问题

  • 因为主机的运行速度极快，外部设备的运行速度很慢， 当主机传输大量数据时外部设备来不及接收，因此需要一个缓冲区来存放这些没来得及接收的数据， 而且这些数据也是按先进先出的规则来接收和传送到外部设备，这样保证数据不会乱序。

• 解决多用户引起的资源竞争问题

  • CPU的资源竞争就是很经典的例子：因为一个CPU只能服务一个用户，当多个用户进行请求CPU服务时，就需要进行排队等待，由操作系统将他们按照请求的先后顺序排成队列，来等待CPU的服务。

---

---

未完待续….

参考资料 ：

1. 23版王道408数据结构单科书
2. 王道考点精讲视频课件