本章学习栈
栈
一、栈（stack）的基本概念
1、栈是一个先入后出（FILO - First In Last Out）的有序列表；
2、栈（stack）是限制线性表中元素的插入和删除只能在线性表的一端进行的一种特殊的线性表。允许插入和删除的一端为变化的一端，称为栈顶（Top），另一端为固定的一端，称为栈底；
3、根据栈的定义可知，最先放入的元素在栈底，最后放入的元素在栈顶。而删除刚好相反，先放入的元素后删除，后放入的元素先删除。
入栈的逻辑图
出栈的逻辑图
二、栈的代码实现
1、数组模拟栈的思路分析
（1）使用数组来模拟栈；
（2）定义一个top来表示栈顶，初始化为-1；
（3）入栈的操作，当有数据加入到栈时，先判断栈是否已满，若不满则top++；stack[top] = number；
（4）出栈的操作，当有数据要出栈时，先判断栈是否为空，若不为空则int value = stack[top]；top–；return value；
2、栈类的私有属性与构造方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public class ArrayStack {
private int maxSize;
private int[] stack;
private int top;
public ArrayStack(int maxSize) {
this.maxSize = maxSize;
stack = new int[maxSize];
this.top = -1;
}
}
|
3、栈类的非空与已满
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
public boolean isFull(){
return top == maxSize - 1;
}
public boolean isEmpty(){
return top == -1;
}
|
4、栈的出栈、入栈、获取栈顶内容与遍历
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
public void push(int number){
if (isFull()) {
throw new RuntimeException("栈已满！");
}
top++;
stack[top] = number;
}
public int pop(){
if (isEmpty()){
throw new RuntimeException("栈为空！");
}
int value = stack[top];
top--;
return value;
}
public int getTop(){
if (isEmpty()){
throw new RuntimeException("栈为空！");
}
return stack[top];
}
public void list(){
if (isEmpty()) {
throw new RuntimeException("栈为空！");
}
for (int i = top; i >= 0; i--) {
System.out.println(stack[i]);
}
}
|
5、栈的检测
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| public class ArrayStackDemo {
public static void main(String[] args) {
ArrayStack stack = new ArrayStack(10);
stack.push(15);
stack.push(25);
stack.push(35);
stack.push(45);
stack.push(55);
stack.push(65);
stack.push(75);
System.out.println("插入元素之后");
stack.list();
System.out.println("-----------------------");
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println("-----------------------");
System.out.println("出栈之后");
stack.list();
}
}
|
三、使用栈对一个表达式进行运算
1、使用栈完成表达式的计算思路
（1）通过一个index值（索引），来遍历我们的表达式；
（2）如果我们发现是一个数字就直接入数栈；
（3）如果发现扫描到的是一个符号，就分情况进行处理：
- 如果当前的符号栈为空就直接入栈。
- 如果当前的符号栈有操作符，就进行比较。如果当前的操作符优先级小于或等于栈中的操作符，就从数栈中pop出两个数，再从符号栈中pop出一个符号进行运算。将得到的结果再存入数栈，再将当前的符号入栈。如果当前的操作符优先级大于栈中的操作符就将当前的操作符直接入栈。
（4）当扫描完表达式后就顺序的从数栈和符号栈中pop出相应的数个符号并运行。
（5）最后在数栈只有一个数字，就是表达式的结果。
2、编写计算类——Calculator
1
2
3
4
5
6
7
8
9
10
11
12
| public class Calculator {
private String str;
private ArrayStack numberStack;
private ArrayStack symbolStack;
public Calculator(String str) {
this.str = str;
numberStack = new ArrayStack(str.length());
symbolStack = new ArrayStack(str.length());
}
}
|
3、运算符之间的优先级判断方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
public int priority(int oper){
if (oper == '(' || oper == ')'){
return 2;
}else if (oper == '*' || oper == '/'){
return 1;
}else if (oper == '+' || oper == '-'){
return 0;
}else return -1;
}
|
4、字符判断与运算方法
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
public boolean isOper(char ch){
return ch == '*' || ch == '/' || ch == '+' || ch == '-' || ch == '(' || ch == ')';
}
public Integer operation(int num1,int num2,char ch){
Integer sum = null;
switch (ch){
case '+':
sum = num1 + num2;
break;
case '-':
sum = num1 - num2;
break;
case '*':
sum = num1 * num2;
break;
case '/':
sum = num1 / num2;
break;
case '(':
numberStack.push(num1);
symbolStack.push(ch);
sum = num2;
break;
case ')':
while (true){
char pop = (char) symbolStack.pop();
if (pop == '(') {
break;
}
sum = operation(num1,num2,pop);
}
}
return sum;
}
|
5、运算方法
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| public int sunber(){
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (isOper(c)) {
if (symbolStack.isEmpty()){
symbolStack.push(c);
}else {
if (priority(symbolStack.getTop()) >= priority(c)) {
char pop = (char) symbolStack.pop();
int num2 = numberStack.pop();
int num1 = numberStack.pop();
Integer sum = operation(num1, num2, pop);
if (sum == null){
System.out.println("结果计算有误！");
return 0;
}
symbolStack.push(c);
numberStack.push(sum);
}else {
symbolStack.push(c);
}
}
}else {
numberStack.push(c - 48);
}
}
while (true){
if (symbolStack.isEmpty()) {
return numberStack.pop();
}
char pop = (char) symbolStack.pop();
int num2 = numberStack.pop();
int num1 = numberStack.pop();
numberStack.push(operation(num1, num2, pop));
}
}
|
6、测试方法
1
2
3
4
5
6
7
8
9
10
11
12
| public class CalculatorDemo {
public static void main(String[] args) {
String str5 = "3*5+(1+2)*2+2";
Calculator calculator = new Calculator(str5);
int sunber = calculator.sunber();
System.out.println(sunber);
}
}
|
参考资料： 尚硅谷Java数据结构与java算法（Java数据结构与算法）
