栈

[Zakariyya]

• 一个 先进后出 的有序列表
• 栈是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端， 为变化的一端，称为栈顶（Top） ， 另一端为固定的一端，称为栈底（Bottom）
• 入栈，压栈（push）、出栈（pop）

应用

1. 子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。（我们常用的 return）
2. 处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量的数据存入堆栈中
3. 表达式的转换 【中缀表达式转后缀表达式】 去求值（实际解决）
4. 二叉树的遍历
5. 图形的深度优化（depth—first）搜索法

实现思路

1. 使用数组来模拟 栈
2. 定义一个top 来表示栈顶，初始化为 -1
3. 入栈 ：当有数据加入到栈时， top++ ; stack[top] = data;
4. 出栈 ： int value = stack[top]; top--; return value;

实现表达式计算（计算器）

思路

创建两个 栈

• 数栈（numStack，存放数）
• 符号栈（operStack，存放运算符）

1. 通过一个index值（索引），遍历表达式
2. 如果是数字，直接入栈
3. 如果扫描到是一个符号，分以下情况
   • 如果发现当前的符号，直接入栈
   • 如果符号栈有操作符，就进行比较，如果 当前的操作符的优先级小于或者等于栈中的操作符，就需要从数栈中pop出两个数，再从符号栈中pop出一个符号，进行运算，将得到的结果，入数栈，然后将当前的操作符入符号栈， 如果当前的操作符的优先级大于栈中的操作符，就直接入符号栈 。
4. 当表达式扫描完毕，就顺序的从 数栈 和 符号栈 中pop出相应的数和符号，并运行
5. 最后在数栈只有一个数字，就是表达式的结果

3 + 6 * 2 - 2

index	数栈	符号栈
0	3
1		+
2	6

index = 3;

• 判断出符号栈中存在 符号（+），于是将 * 和 + 做优先级比较
• • 优先级大于 + ，存入符号栈

index	数栈	符号栈
3		*
4	2

index = 5;

• 判断出符号栈中存在 符号（），于是将 和 - 做优先级比较
• • 优先级小于 * ，于是乎……
• 从数栈中取出两个数，符号栈中取出一个符号，进行运算
• 得到运算结果后，存入数栈
• 再将 index=5 的符号存入符号栈

index	数栈	符号栈
5	12	-
6	2

表达式扫描结束

数栈	符号栈
3	+
12	-
2

1. 取出数栈顶 两数（12，2），符号栈顶 符号（-），运算得出 10，存入数栈。
2. 取出数栈顶 两数（10，3），符号栈顶 符号（+），运算得出 13，存入数栈。
3. 取出数栈数 13，则是结果，运算结束

70 + 2 * 6 - 4（进阶）多位数的运算

思路

1. 处理多位数时，不能发现一个数就立即入栈，因为可能是多位数
2. 在处理数时，需要向表达式的 index 后再看一位，如果是数就进行扫描，如果是符号才入栈
3. 因此我们需要定义一个变量 字符串，用于拼接