栈的介绍

  1. 栈的英文为(stack)
  2. 栈是一个先入后出(FILO-First In Last Out)的有序列表。
  3. 栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端,为变化的一端,称为栈顶(Top),另一端为固定的一端,称为栈底(Bottom)。
  4. 根据栈的定义可知,最先放入栈中元素在栈底,最后放入的元素在栈顶,而删除元素刚好相反,最后放入的元素最先删除,最先放入的元素最后删除。
  5. 栈的插入操作(push),称压栈、入栈。类似子弹入弹夹。
    栈的删除操作(pop),叫作出栈,也有的叫作弹栈。如同弹夹中的子弹出夹。

栈的顺序存储结构

栈的链式存储结构

栈的应用场景

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

用数组模拟栈

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
package com.nanzx.stack;

import java.util.Scanner;

public class ArrayStackDemo {

public static void main(String[] args) {
// 测试一下ArrayStack 是否正确
// 先创建一个ArrayStack对象->表示栈
ArrayStack stack = new ArrayStack(4);
String key = "";
boolean loop = true; // 控制是否退出菜单
Scanner scanner = new Scanner(System.in);

while (loop) {
System.out.println("show: 表示显示栈");
System.out.println("exit: 退出程序");
System.out.println("push: 表示添加数据到栈(入栈)");
System.out.println("pop: 表示从栈取出数据(出栈)");
System.out.println("请输入你的选择");
key = scanner.next();
switch (key) {
case "show":
stack.list();
break;
case "push":
System.out.println("请输入一个数");
int value = scanner.nextInt();
stack.push(value);
break;
case "pop":
try {
int res = stack.pop();
System.out.printf("出栈的数据是 %d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case "exit":
scanner.close();
loop = false;
break;
default:
break;
}
}

System.out.println("程序退出~~~");
}
}

//定义一个 ArrayStack 表示栈
class ArrayStack {
private int maxSize; // 栈的大小
private int[] stack; // 数组,数组模拟栈,数据就放在该数组
private int top = -1;// top表示栈顶,初始化为-1

// 构造器
public ArrayStack(int maxSize) {
this.maxSize = maxSize;
stack = new int[this.maxSize];
}

// 栈满
public boolean isFull() {
return top == maxSize - 1;
}

// 栈空
public boolean isEmpty() {
return top == -1;
}

// 入栈-push
public void push(int value) {
// 先判断栈是否满
if (isFull()) {
System.out.println("栈满");
return;
}
top++;
stack[top] = value;
}

// 出栈-pop, 将栈顶的数据返回
public int pop() {
// 先判断栈是否空
if (isEmpty()) {
// 抛出异常
throw new RuntimeException("栈空,没有数据~");
}
int value = stack[top];
top--;
return value;
}

// 显示栈的情况[遍历栈], 遍历时,需要从栈顶开始显示数据
public void list() {
if (isEmpty()) {
System.out.println("栈空,没有数据~~");
return;
}
// 需要从栈顶开始显示数据
for (int i = top; i >= 0; i--) {
System.out.printf("stack[%d]=%d\n", i, stack[i]);
}
}

}

前缀表达式(波兰式)

介绍

前缀表达式又称波兰式,前缀表达式的运算符位于操作数之前。
举例说明: (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6

前缀表达式的计算机求值

从右至左扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(栈顶元素 和 次顶元素),并将结果入栈;重复上述过程直到表达式最左端,最后运算得出的值即为表达式的结果。

例如: (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6 , 针对前缀表达式求值步骤如下:

  1. 从右至左扫描,将6、5、4、3压入堆栈
  2. 遇到+运算符,因此弹出3和4(3为栈顶元素,4为次顶元素),计算出3+4的值,得7,再将7入栈
  3. 接下来是×运算符,因此弹出7和5,计算出7×5=35,将35入栈
  4. 最后是-运算符,计算出35-6(栈顶元素 - 次顶元素)的值,即29,由此得出最终结果

中缀表达式

介绍

中缀表达式就是常见的运算表达式,如(3+4)×5-6

中缀表达式的计算机求值

使用栈完成中缀表达式的计算思路:

  1. 需要创建两个栈:数栈存放数字,符号栈存放运算符

  2. 通过一个 index 值(索引),来遍历我们的表达式

  3. 如果我们发现是一个数字, 就直接入数栈

  4. 如果发现扫描到是一个运算符, 就分如下情况:

    如果当前的符号栈为空,就直接入栈。

    如果符号栈有运算符,就进行比较:①当前运算符的优先级 <= 栈中的操作符, 就需要从数栈中pop出两个数,再从符号栈中pop出一个运算符,进行运算,将得到结果压入数栈,然后将当前运算符压入符号栈。②当前运算符的优先级 > 栈中的操作符, 就直接入符号栈。

  5. 当表达式扫描完毕,就顺序的从数栈和符号栈中pop出相应的数和符号,并运行

  6. 最后在数栈只有一个数字,就是表达式的结果

后缀表达式(逆波兰表达式)

介绍

后缀表达式又称逆波兰表达式,与前缀表达式相似,只是运算符位于操作数之后

举例说明: (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 –

后缀表达式的计算机求值

从左至右扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(次顶元素 和 栈顶元素),并将结果入栈;重复上述过程直到表达式最右端,最后运算得出的值即为表达式的结果。

例如: (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 - , 针对后缀表达式求值步骤如下:

  1. 从左至右扫描,将3和4压入堆栈;
  2. 遇到+运算符,因此弹出4和3(4为栈顶元素,3为次顶元素),计算出3+4的值,得7,再将7入栈;
  3. 将5入栈;
  4. 接下来是×运算符,因此弹出5和7,计算出7×5=35,将35入栈;
  5. 将6入栈;
  6. 最后是-运算符,计算出35-6的值(次顶元素 - 栈顶元素),即29,由此得出最终结果

逆波兰计算器的实现

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
49
50
51
52
53
54
55
package com.nanzx.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class PolandNotation {

public static void main(String[] args) {
// 后缀表达式为9 3 1 - 3 * + 10 2 / + 中缀表达式为9+(3-1)*3+10/2=20
String suffixExpression = "9 3 1 - 3 * + 10 2 / +";
List<String> list = getListString(suffixExpression);
System.out.println(calculate(list));
}

// 一个后缀表达式, 依次将数据和运算符放入到ArrayList中
public static List<String> getListString(String suffixExpression) {
String[] split = suffixExpression.split(" ");
List<String> list = new ArrayList<String>();
for (String ele : split) {
list.add(ele);
}
return list;
}

// 根据逆波兰表达式求值
public static int calculate(List<String> list) {
Stack<String> stack = new Stack<String>();
for (String item : list) {
// 正则表达式,匹配是否为数字
if (item.matches("\\d+")) {
stack.push(item);
} else {
int num1 = Integer.valueOf(stack.pop());//栈顶元素
int num2 = Integer.valueOf(stack.pop());//次顶元素
int result = 0;
if (item.equals("+")) {
result = num1 + num2;
} else if (item.equals("*")) {
result = num1 * num2;
} else if (item.equals("-")) {//注意减数和被减数
result = num2 - num1;
} else if (item.equals("/")) {//注意除数和被除数
result = num2 / num1;
} else {
System.out.println("程序有异常!!!");
}
stack.push(result + "");//将数字型转换为字符串型
}
}
return Integer.valueOf(stack.pop());//栈中最后一个元素即为结果
}
}


将中缀表达式转换为后缀表达式

中缀表达式“9+(3-1)×3+10÷2”转化为后缀表达式“9 3 1 - 3 * + 10 2 / +”。

规则:从左到右遍历中缀表达式的每个数字和符号,若是数字就输出,即成为后缀表达式的一部分;若是符号,则判断其与栈顶符号的优先级,是右括号或优先级低于栈顶符号(乘除优先加减)则栈顶元素依次出栈并输出,并将当前符号进栈,一直到最终输出后缀表达式为止。

思路:

  1. 初始化:运算符栈stack和动态数组(ArrayList) list;

  2. 从左至右扫描中缀表达式;

  3. 遇到操作数时,将其添加到list中;

  4. 遇到运算符时,比较其与stack栈顶运算符的优先级:

    • 如果stack为空,或栈顶运算符为左括号“(”,则直接将此运算符入栈;
    • 如果优先级比栈顶运算符的高,也将运算符压入stack;
    • 如果优先级比栈顶运算符的低,将stack栈中的所有运算符弹出并追加到list中。
  5. 遇到括号时:

    • 如果是左括号“(”,则直接压入stack;

    • 如果是右括号“)”,则依次弹出stack栈顶的运算符,并追加到list中,直到遇到左括号为止,此时将这一对括号丢弃。

  6. 从左至右扫描中缀表达式结束后,将stack中剩余的运算符依次追加到list中。

代码实现:

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
package com.nanzx.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class PolandNotation {

public static void main(String[] args) {
String infixExpression = "9+(3-1)*3+10/2";
List<String> ls = toInfixExpressionList(infixExpression);
List<String> list = parseSuffixExpreesionList(ls);
System.out.println(ls);
System.out.println(list);
System.out.println(calculate(list));
}

public static int priority(String s) {
if (s.equals("*") || s.equals("/")) {
return 1;
} else if (s.equals("+") || s.equals("-")) {
return 0;
} else {
return -1;
}
}
//将中缀表达式放入到ArrayList中,进行数据处理
public static List<String> toInfixExpressionList(String s) {
List<String> ls = new ArrayList<String>();
int i = 0; // 这时是一个指针,用于遍历中缀表达式字符串
String str; // 对多位数的拼接
char c; // 每遍历到一个字符,就放入到c
do {
// 如果c是一个非数字,需要加入到ls
if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
ls.add("" + c);
i++; // i需要后移
} else { // 如果是一个数,需要考虑多位数
str = ""; // 先将str 置成"" '0'[48]->'9'[57]
while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {
str += c;// 拼接
i++;
}
ls.add(str);
}
} while (i < s.length());
return ls;// 返回
}

public static List<String> parseSuffixExpreesionList(List<String> ls) {
Stack<String> stack = new Stack<String>();
List<String> list = new ArrayList<String>();
for (String ele : ls) {
if (ele.matches("\\d+")) {
list.add(ele);
} else if (ele.equals("(")) {
stack.push(ele);
} else if (ele.equals(")")) {
while (!stack.peek().equals("(")) {//peek查看并没有pop出去
list.add(stack.pop());
}
stack.pop();//把括号pop出去,并没有加入list
} else {//运算符的判断
while (stack.size() != 0 && priority(ele) <= priority(stack.peek())) {
list.add(stack.pop());
}
stack.push(ele);
}
}
while (stack.size() != 0) {
list.add(stack.pop());
}
return list;
}
}