2023考研408数据结构备考知识点：栈（下）

今天小编为大家整理了2023考研408数据结构知识点之栈的相关介绍，从栈和函数调用、栈的应用等方面为大家做详细的介绍，助力大家更好地备考，提高备考效率，顺利进入理想院校。

7：栈和函数调用

函数的调用符合先调用，后执行的特点，正好可以用栈来进行存储函数的调用过程;在用栈进行存储时，先调用的函数，先入栈，那么从栈底到栈顶依次是函数调用的顺序。

8：栈的应用

1、 符号匹配：程序中经常用到一些成对出现的符号，比如括号，对其进行是否成对检验是基本的编译问题，可利用堆栈特点是先检测算法。每扫描到一个左括号，将其入栈，扫描到右括号，将其出栈。扫描结束，若栈非空，返回0，说明左右括号个数不一致，否则返回1，说明二者个数匹配。

2、 整数进制转换(eleType为unsigned类型)：以十进制转八进制为例，其他进制类似。比如将一个十进制数字n转换为8进制数，对n除以8取余数，所有余数倒序输出即为对应的八进制数。

3.表达式求值

(1)表达式的类型。

表达式有3个组成部分.分别是操作数、运算符、界限符号(包括小括号，.中括号)。

表达式有3种类型,分别是中缀表达式.前缀表达式(波兰式)、后缀表达式(逆波兰式)。这3种表达式可以使用表达式对应的二叉树的遍历来表示。例如,给定一个表达式:b-(a+5) * 3, 按照优先级顺序,构造出与表达式相对应的二叉树,其中运算符是二叉树的根，操作数是二叉树的左、右子树。

最后在这个构造好的二叉树上进行遍历,3种遄历顺序分别如下。.

前序遍历:根-左-右。

中序遍历:左-根-右。

后序遍历:左-右-根。

在最终二叉树的基础上可以得出以下表达式。

前缀表达式:一b* +a 5 3。

中缀表达式:b-(a+5) * 3。

后綴表达式:ba5+3*一。

(2)中缀表达式转后缀表达式。

①转化前先建立两个栈，命名为s1和s2。用栈s1存储表达式中的运算数,用栈s2存储符号。

②在转化的过程中,需从左到右扫描中綴表达式的每个运算数和符号,若是运算数则压入到栈sl中。

③若扫描到的是符号,设符号是C,则可能出现以下情况。

a若s2为空,则C压入到栈s2中。

b.若C为左括号，则C压入到栈s2中。

c.若s2的栈顶符号为左括号，则C压入到栈s2中。

d.若s2的栈顶符号的优先级小于C.则C压入到栈s2中(右括号的优先级最低)。

e.否则，就要将s2的栈顶符号弹出,从sl中弹出两个(也可能是1个)运算数.进行运算,并把运算的结果压回s1。

④扫描到表达式结束,若最后栈s2中还有符号,则将其依次出栈,并从s1中弹出两个(也可能是1个)运算数,进行运算,并把运算的结果压回sl。

⑤最终完成转化过程。