一 定义
- 栈的英文为(
stack) - 栈是一个
先入后出(FILO-First In Last Out)的有序列表。 - 栈(stack)是限制线性表中元素的插入和删除只能在线性表的
同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。 - 根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除
出栈(pop)和入栈(push)的概念
image.png
image.png
应用场景
-
子程序的调用(方法栈)：在跳往子程序前，会先将下个指令的地址存到堆栈(个人理解:每次遇到新指令，放到栈顶。执行完新指令后，继续执行之前的指令)中，直到子程序执行完后再将地址取出，以回到原来的程序中。 -
处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中(jvm对一些尾递归会做优化，不用栈)。 - 表达式的转换[
中缀表达式转后缀表达式]与求值(实际解决)。 -
二叉树的遍历。 -
图形的深度优先(depth一first)搜索法。
二 数组实现
实现方式有数组和链表两种，和前面的队列基本大同小异。这里只展示了数组的实现方式
思路分析
- 和队列象比，栈式
先进后出.因此不用像队列那样特殊处理（下标取模）来实现空间的复用 - 增加一个
扩容特性 - 栈顶指针top，
下一个下标入栈,当前下标出栈((数量=top+1);默认-1
代码实现
对于栈来说，只需要一个指针（指针的定义都是由编写者自己定义）
package com.zyc.stack;
/**
* @author zhuyc
* @create 2019-07-14 7:21
*/
public class MyStack {
private Object[] array;
private int top = -1;//栈顶指针，下一个下标入栈,当前下标出栈((数量=top+1)
private int size;
public MyStack(int size){
array = new Object[size];
this.size = size;
}
public void push(Object element){
if(top == size-1){
//需要扩容
resize(size*2);
}
array[++top] = element;
}
public Object pop(){
if(top == -1){
throw new RuntimeException("已到栈底");
}
return array[top--];
}
public void resize(int resize){
Object[] data = new Object[resize];
System.arraycopy(array,0,data,0,size);
array = data;
size = resize;
}
public void show(){
int i = 0;
System.out.println("----show start-------");
while(i<=top){
System.out.print(array[i]+"\t");
i++;
}
System.out.println();
System.out.println("----show end-------");
}
}
测试代码
@Test
public void test1(){
MyStack stack = new MyStack(4);
stack.push("1");
stack.push("2");
stack.push("3");
stack.push("4");
stack.push("5");
stack.push("6");
stack.push("7");
stack.push("8");
stack.push("4");
stack.push("9");
stack.show();
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
stack.push("10");
stack.push("11");
stack.push("12");
stack.push("13");
stack.show();
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
stack.show();
}
三 计算器
不考虑括号的情况下：
image.png
总结
- 空就直接入
- 不空先判断
操作符优先级,大于直接入；小于等于，数栈出两个，符号栈出一个。计算完的值放入数栈。然后继续依次判断1，2 - 表达式结束，则依次出栈（数栈2个，符号一个）
代码实现
package com.zyc.stack;
import java.util.HashMap;
import java.util.Map;
/**
* @author zhuyc
* @create 2019-07-14 8:04
*/
public class SimpleCalculator {
private MyStack numStack = new MyStack(10);
private MyStack opeStack = new MyStack(10);
public int calculate(String expression){
//TODO: 校验省略
int pre = 0;//本次次开始的截取位置
int last = 0;
char ele;
while(last<expression.length()){
ele = expression.charAt(last);
if(ele == '+' || ele == '-' || ele == '*' || ele == '/'){
//先截取前面的数字
String num = expression.substring(pre,last);
numStack.push(Integer.valueOf(num));
//再截取操作符
String ope = expression.substring(last,last+1);
dealOpe(ope);
pre = last+1;
last++;
}else{
last++;
}
}
//遍历结束
String num = expression.substring(pre);
numStack.push(Integer.valueOf(num));
//将符号全部取出来，运算完
while(true){
try {
String ope = (String) opeStack.pop();
int num1 = (int) numStack.pop();
int num2 = (int) numStack.pop();//前一个数字
cal(num2,num1,ope);
}catch (Exception e){
//结束了
break;
}
}
return (int) numStack.pop();
}
public void dealOpe(String ope){
String preOpe = null;
try {
preOpe = (String) opeStack.pop();
}catch (Exception e){
//符号栈为空
opeStack.push(ope);
return;
}
//比较优先级
int preRank = opeRank.get(preOpe);
int rank = opeRank.get(ope);
if(rank <= preRank){
int num1 = (int) numStack.pop();
int num2 = (int) numStack.pop();//前一个数字
cal(num2,num1,preOpe);
//继续放
dealOpe(ope);
}else{
opeStack.push(preOpe);//放回去
opeStack.push(ope);
}
}
public void cal(int preNum,int num,String ope){
int value = -1;
switch (ope){
case "+": value = preNum+num;break;
case "-": value = preNum-num;break;
case "*": value = preNum*num;break;
case "/": value = preNum/num;break;
}
numStack.push(value);
}
private Map<String,Integer> opeRank = new HashMap<String,Integer>(){
{
this.put("+",1);
this.put("-",1);
this.put("*",2);
this.put("/",2);
}
};
}
测试代码
@Test
public void testSimpleCalculator(){
SimpleCalculator sc = new SimpleCalculator();
System.out.println(sc.calculate("36/12*3+12-9+15/5*2*2/4+23"));//38
}
四 前缀表达式
前缀表达式(波兰表达式)
- 前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前
- 举例说明： (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6
前缀表达式的计算机求值
从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 和 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果
例如: (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6 , 针对前缀表达式求值步骤如下:
- 从右至左扫描，将6、5、4、3压入堆栈
2 .遇到+运算符，因此弹出3和4（3为栈顶元素，4为次顶元素），计算出3+4的值，得7，再将7入栈 - 接下来是×运算符，因此弹出7和5，计算出7×5=35，将35入栈
- 最后是-运算符，计算出35-6的值，即29，由此得出最终结果
五 中缀表达式
- 中缀表达式就是常见的运算表达式，如(3+4)×5-6
- 中缀表达式的求值是我们人最熟悉的，但是对计算机来说
却不好操作(前面我们讲的案例就能看的这个问题)，因此，在计算结果时，往往会将中缀表达式转成其它表达式来操作(一般转成后缀表达式.)
六 后缀表达式
后缀表达式又称逆波兰表达式,与前缀表达式相似，只是运算符位于操作数之后
举例说明： (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 –
再比如:
image.png
后缀表达式的计算机求值
从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 和 栈顶元素），并将结果入栈； 重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果
例如: (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 - , 针对后缀表达式求值步骤如下:
- 从左至右扫描，将3和4压入堆栈；
- 遇到+运算符，因此弹出4和3（
4为栈顶元素，3为次顶元素），计算出3+4(注意顺序)的值，得7，再将7入栈； - 将5入栈；
- 接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；
- 将6入栈；
- 最后是-运算符，计算出35-6的值，即29，由此得出最终结果
七 中缀表达式转换为后缀表达式
大家看到，后缀表达式适合计算式进行运算，但是人却不太容易写出来，尤其是表达式很长的情况下，因此在开发中，我们需要将 中缀表达式转成后缀表达式。
具体步骤如下:
- 初始化两个栈：
运算符栈s1和储存中间结果的栈s2； -
从左至右扫描中缀表达式； - 遇到操作数时，将其压s2；
- 遇到运算符时，
比较其与s1栈顶运算符的优先级：- 如果s1为
空，或栈顶运算符为左括号“(”，则直接将此运算符入栈s1； - 若优先级比栈顶运算符的
高，也将运算符压入s1； - 否则，将s1栈顶的运算符弹出并压入到
s2中，再次转到(步骤4)与s1中新的栈顶运算符相比较；
- 如果s1为
- 遇到括号时：
- 如果是·左括号“(”·，则直接压入s1
- 如果是·右括号“)”·，则·依次弹出·s1栈顶的运算符，并压入s2，
直到遇到左括号为止，此时将这一对括号丢弃
-
重复步骤2至5，直到表达式的最右边 - 将s1中
剩余的运算符依次弹出并压入s2
8, 依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式(从下往上读)
总结
上面这个有点烦。
转换过程需要用到栈，具体过程如下：
1）如果遇到操作数，我们就直接将其输出。
2）如果遇到操作符，则我们将其放入到栈中，遇到左括号时我们也将其放入栈中。
3）如果遇到一个右括号，则将栈元素弹出，将弹出的操作符输出直到遇到左括号为止。注意，左括号只弹出并不输出。
4）如果遇到任何其他的操作符，如（“+”， “*”，“（”）等，从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)(优先级高的先出栈)为止。弹出完这些元素后，才将遇到的操作符压入到栈中。有一点需要注意，只有在遇到" ) "的情况下我们才弹出" ( "，其他情况我们都不会弹出" ( "。
5）如果我们读到了输入的末尾，则将栈中所有元素依次弹出。
代码实现
public static void translate(String MidStr) {
String express = "";
String sign = "";
Stack<String> stack = new Stack<>();
String[] strs = MidStr.split(" ");
for(String str:strs) {
if("(".equals(str)) {//这个直接放
stack.push(str);
}else if(")".equals(str)) {
do {
sign = stack.pop();
if(!"(".equals(sign)) {
express+=" "+sign;
}else {//直到'('为止，并且不输出
break;
}
}while(!stack.empty());
}else if("+".equals(str)||"-".equals(str)) {
while(!stack.empty()) {//非空就出栈
sign = stack.pop();//出栈
// System.out.println(":"+sign);
if("(".equals(sign)) {//+或-只有碰到(才会停止，其他优先度都不比它们低，`(`不会入栈的
stack.push("(");//放回去
break;
}
express+=" "+sign;//
}
stack.push(str);
}else if("*".equals(str) || "/".equals(str)) {
while(!stack.empty()) {
sign = stack.pop();//出栈看看是什么
if("*".equals(sign) || "/".equals(sign)) {//只有这两个才是一样的
express+=" "+sign;
}else {
stack.push(sign);//放回去
break;
}
}
stack.push(str);
}else {
express += " "+str;
}
}
int size = stack.size();
//pop的size是变化的，先取好
for(int i =0;i<size;i++) {
System.out.println("chu");
express += " "+stack.pop();
}
System.out.println(express);
}
