基本介绍:
栈:栈是限定仅在表尾进行插入和删除操作的线性表,后进先出
允许插入的一段叫做栈顶,另一端就成为栈底,如图所示:
栈.png
队列:队列是只允许在一端进行插入操作、而在另一端进行删除操作的线性表
插入的一端称为队尾，删除的一端称为队头,如图所示:
队列.png
栈和队列都只是一种特殊的加入特定算法的线性表,我们在工作中应该灵活的运用它们,而不是死抠概念.比如队列在Android中比较经典的应用:MessageQueue.熟悉Android的朋友应该不会陌生,MessageQueue是Handler机制中非常重要的一部分.后面我们再分析一下它.
下面我们分别来分析一下栈和队列的常用场景:
栈的常用场景:
- Android分层显示:在Android屏幕上,不止有X和Y轴,还有Z轴.我们说的Activity的四种启动模式就运用到了栈.我们新打开一个页面就把这个页面入栈,当我们按返回键的时候,位于栈顶的页面就出栈.
- 日常生活中穿衣服脱衣服其实也是一个入栈出栈的过程
- 逆波兰表达式实现计算器
大家对逆波兰表达式可能会比较陌生,简单介绍一下:
逆波兰表达式，它的语法规定，表达式必须以逆波兰表达式的方式给出。逆波兰表达式又叫做后缀表达式。
这个知识点在数据结构和编译原理这两门课程中都有介绍，下面是一些例子：
正常的表达式 逆波兰表达式
a+b ---> a,b,+
a+(b-c) ---> a,b,c,-,+
a+(b-c)*d ---> a,b,c,-,d,*,+
a+d*(b-c)--->a,d,b,c,-,*,+
a=1+3 ---> a,1,3,+,=
http=(smtp+http+telnet)/1024 写成什么呢？
http,smtp,http,+,telnet,+,1024,/,=
当把普通的中缀表达式转变成逆波兰表达式时,后续的计算就变成了一个入栈出栈的过程
逆波兰表达式的实现算法
1.中缀表达式转为后缀表达式
2.设置一个堆栈，初始时将堆栈顶设置为#
3.顺序读入中缀表达式，到读到的单词为数字时将其输出，接着读下一个单词；
4.令x1 为栈顶运算符变量，x2 为扫描到的运算符变量，当顺序从表达试中读到的运算符时赋值给x2，然后比较x1 和 x2 的优先级，
若x1 的优先级高于x2的优先级，将x1退栈并输出，接着比较新的栈顶运算符x1，x2的优先级；
若 x1的优先级低于x2的优先级，将x2 入栈;如果x1 = “（”且 x2 = “）”，将x1 退栈；若x1的优先级等于x2的优先级且x1 = “#”而x2=“#”时，算法结束
下面我们就用栈来实现一下逆波兰表达式计算
首先分析一下Stack源码:
1.首先Stack继承自Vector
2.Stack的主要方法:
1.push方法:向栈顶添加一个元素
2.pop方法:移除栈顶元素,并重新指定栈顶
3.peek方法:获取栈顶元素,但不移除
4.search方法:返回第一个符合该条件的元素距离栈顶的距离
5.empty方法:判断当前栈是否为空栈
3.结合Vecotr代码分析Stack的主要方法及数据结构:
Vector的是一个顺序结构的线性表,数据用一个数据存储,Vector的主要组成部分如下:
1.成员变量:
elementCount:用于存储线性表中存储元素的个数
elementData:是一个对象数组,用于存储实际数据
capacityIncrement:数组每一次扩容的数量
2.主要方法:
add:add方法有两个重载,这里我们主要分析栈常用的push方法所用到的add(E)方法,
即向Vector尾部添加一个元素,在栈中就是栈顶添加元素,也就是将元素添加到数组的末尾,如果数组的长度不够就自动扩容.
自动扩容的算法咱们在这就不详细介绍了
vector还有很多重要方法,但都与我们前面分析的Stack的几个重要方法没什么关系,这里我们就不再介绍了,有兴趣的可以自己去翻看源码
在正式开始撸码之前，我们再来理一下将中缀表达式转换成后缀表达式算法以及逆波兰表达式求值算法：
一、 将中缀表达式转换成后缀表达式算法：
1、从左至右扫描一中缀表达式。
2、若读取的是操作数，则判断该操作数的类型，并将该操作数存入操作数堆栈
3、若读取的是运算符
(1) 该运算符为左括号"("，则直接存入运算符堆栈。
(2) 该运算符为右括号")"，则输出运算符堆栈中的运算符到操作数堆栈，直到遇到左括号为止。
(3) 该运算符为非括号运算符：
(a) 若运算符堆栈栈顶的运算符为括号，则直接存入运算符堆栈。
(b) 若比运算符堆栈栈顶的运算符优先级高，则直接存入运算符堆栈。
(c) 若比运算符堆栈栈顶的运算符优先级低或相等，则输出栈顶运算符到操作数堆栈，并将当前运算符压入运算符堆栈
4、当表达式读取完成后运算符堆栈中尚有运算符时，则依序取出运算符到操作数堆栈，直到运算符堆栈为空。
二、逆波兰表达式求值算法：
1、从左到右依次扫描语法单元的项目。
2、如果扫描的项目是操作数，则将其压入操作数堆栈，并扫描下一个项目。
3、如果扫描的项目是一个二元运算符，则对栈的顶上两个操作数执行该运算。
4、如果扫描的项目是一个一元运算符，则对栈的最顶上操作数执行该运算。
5、将运算结果重新压入堆栈。
6、重复步骤2-5，堆栈中即为结果值。
好了，介绍完具体的算法咱们就开始敲代码了:
1.定义一个中缀表达式格式的字符串，
String s="9+(5-2)*4+10/2";
2.将中缀表达式对应的字符串先转化成一个char类型的数组
3.定义两个栈numStack以及opeStack，分别用于存储数字和字符。
4.结合前面分析的算法，两个算法结合执行，这样最后的栈中就剩下我们最后要得到的结果了
具体代码如下：
public Stack resetString(char[] charArray) {
numStack=new Stack();
opeStack=new Stack();
//定义一个StringBuffer用来拼接连续的数字作为一个字符串，
//如10在被转化为charArray的时候被分割成了1和0 现在需要把他们拼接起来
StringBuffer numS=new StringBuffer();
for (int i = 0; i < charArray.length; i++) {
String s=String.valueOf(charArray[i]);
if(isOperator(s)) {
//找到符号则把之前拼接的字符串入数字栈
if(!numS.toString().equals("")) {
numStack.push(numS.toString());
numS=new StringBuffer();
}
if(opeStack.isEmpty()) {
opeStack.push(s);
}else {
if(s.equals("(")) {//该运算符为左括号"("，则直接存入运算符堆栈
opeStack.push(s);
}else if(s.equals(")")) {
// 该运算符为右括号")"，则输出运算符堆栈中的运算符到操作数堆栈，直到遇到左括号为止
String op=(String) opeStack.pop();
while(!op.equals("(")) {
calculate(op);
op=(String) opeStack.pop();
}
}else {
String op=(String) opeStack.peek();
if(op.equals("(")) {
opeStack.push(s);//若运算符堆栈栈顶的运算符为括号，则直接存入运算符堆栈
}else {
int result=compare(s,op);
if(result>0) {//若比运算符堆栈栈顶的运算符优先级高，则直接存入运算符堆栈
opeStack.push(s);
}else {
/*
若比运算符堆栈栈顶的运算符优先级低或相等，则输出栈顶运算符到操作数堆栈，
并将当前运算符压入运算符堆栈
* */
calculate(op);
opeStack.pop();
calculate(s);
}
}
}
}
}else {
numS.append(s);
}
//不要忘了最后一个
if(i==charArray.length-1&&!"".equals(numS.toString())) {
numStack.push(numS.toString());
}
}
//当表达式读取完成后运算符堆栈中尚有运算符时，则依序取出运算符到操作数堆栈，直到运算符堆栈为空
while(!opeStack.isEmpty()) {
String string=(String) opeStack.pop();
calculate(string);
}
return numStack;
}
//判断是不是符号
private boolean isOperator(String s) {
return s.equals(ps)||s.equals(ms)||s.equals(mp)||s.equals(dd)||s.equals("(")||s.equals(")");
}
//比较符号的优先级
private int compare(String s1,String s2) {
if(s1.equals(ps)||s1.equals(ms)) {
return -1;
}else{
if(s2.equals(ps)||s2.equals(ms)) {
return 1;
}else {
return 0;
}
}
}
//符号栈出栈，并将数字栈栈顶两个数字出栈进行计算，将结果入栈
private void calculate(String flag) {
int result=0;
int b=Integer.parseInt((String) numStack.pop());
int a=Integer.parseInt((String) numStack.pop());
switch(flag) {
case "+":
result= a+b;
break;
case "-":
result= a-b;
break;
case "*":
result= a*b;
break;
case "/":
result= a/b;
break;
}
numStack.push(String.valueOf(result));
}
