《数据结构与算法分析Java语言描述》第二章3.6与3.7节节读书笔记
3.6 栈ADT
3.6.1 栈模型
栈是插入和删除只能在末端的表，该位置叫栈顶(类似一个桶)。对栈的操作只有进栈(push)与出栈(pop)。
栈是一个后进先出(LIFO)表。我们对栈能进行的操作基本只有push和pop操作。位于栈顶的元素，是唯一直接可见(可访问)的元素。
3.6.2 栈的实现
栈是一个表，任何能实现表的的方法都能实现栈，给出两种流行的实现方法：一种使用链式结构，一种使用数组，二者均简化了在ArrayList和LinkedList的实现。
栈的链表实现
使用单链表，在表的顶端插入实现push，删除表顶端的元素实现pop，top操作获取表顶端的元素并返回值，有时pop与top合二为一。
栈的数组实现
数组的实现避免了链而且可能是最流行的解决方案。push模仿ArrayList的add操作，实现简单。与栈相关的操作是theArray和topOfStack，对空栈，topOfStack为-1(初始化操作)，当由元素x入栈时，topOfStack + 1，theArray[topOfStack] = x。 同理弹栈的时候返回theArray[topOfStack] ，之后topOfStack - 1。
上述操作皆以常数时间运行，再某些机器上push与pop都可以写作一条机器指令，现代化计算机将栈操作作为指令系统的一部分。
3.6.3 应用
平衡符号
编译器检查具有成对的符号(如大括号、括号)缺失引起的编译错误。例如[()]是合法的，但是[(])是错误的。对该算法的简单叙述如下：
将所有字符读入，如果字符是是一个开放符号(成对符号左边的)，就将符号入栈(注意是只入栈符号)。如果是封闭符号，当空栈时报错，否则将栈顶的元素弹出，如果弹出的不是对应的开放符号，则报错，如果读到文件尾，栈非空，则报错。该算法时线性的，且他是联机算法。
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
|
public static boolean isBalanceChar(String str) {
if (str.length() < 2) {
return false;
}
char[] chars = str.toCharArray();
Stack<Character> stack = new Stack<>();
for (int i = 0; i < chars.length; i++) {
if (chars[i] == '(' || chars[i] == '[' || chars[i] == '{') {
stack.push(chars[i]);
} else {
if (stack.isEmpty()) {
return false;
}
char c = stack.pop();
if ((chars[i] == ')' && c != '(') || (chars[i] == ']' && c != '[') || (chars[i] == '}' && c != '{')) {
return false;
}
}
}
return stack.isEmpty();
}
|
后缀表达式
在我们使用的四则运算中，我们都知道乘除优先，需要指定优先级时，可以使用括号，但这(中序表达式)对于计算机则非常不友好，于是有了后缀表达式或称逆波兰式。操作符号放在需要参与运算的数的后面，并且与他前面的数参与运算。他的一个显著的优点是不需要知道运算的优先规则。
例如表达式 6 5 2 3 + 8 ∗ + 3 + ∗ 的含义：将6、5、2、3入栈，遇到+号，表示+号前面的3+前面的2弹栈，并将得到5入栈。再遇到8，8入栈，接着遇到*号，则*号前面的8与5的弹栈，并将8*5的结果40入栈。。。(即遇到数字就继续入栈，遇到四则符号就将前面的两个数弹栈，并将计算的结果入栈)。上式的计算结果如下。
((((3+2)∗8)+5)+3)∗6=288
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
|
public class EvalRPNTest {
public static void main(String[] args) {
String[] tokens = {"2","1","+","3","*"};
int i = evalRPN(tokens);
System.out.println(i);
}
public static int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (String token : tokens) {
switch (token) {
case "+" :
case "-" :
case "*" :
case "/" :
int num2 = stack.pop();
int num1 = stack.pop();
stack.push(calc(num1, num2, token));
break;
default:
stack.push(Integer.parseInt(token));
}
}
return stack.pop();
}
private static Integer calc(int num1, int num2, String token) {
switch (token) {
case "+":
return num1 + num2;
case "-":
return num1 - num2;
case "*":
return num1 * num2;
default:
return num1 / num2;
}
}
}
|
中缀转后缀表达式
日常使用的中缀表达式可以转为后缀表达式，之后方便计算机进行计算。
范例：a + b * c + (d * e + f) * g ====== a b c *+ d e * f + g *+
逻辑：
- 初始化一个栈，用于存放运算符；初始化一个List用于存放数字。List为最终结果
- 如果遇到数字，则直接存入List
- 如果遇到运算符，则与栈顶的运算符比较，如果优先级比栈顶的高，则入栈，否则(同优先级或者低)将栈顶的运算符弹栈再存入队列，之后再将运算符与栈顶的元素继续比较，直到入栈。(优先级 ‘*’ = ‘/’ > ‘+‘ = ‘-’)。注意运算符不与括号比较，直接入栈。
- 如果遇到左括号，则直接入栈，如果遇到右括号，则将栈顶的运算符依次弹出存入队列，直到遇到左括号(不判断栈空的情况：表达式错误)，弹出左括号。(注意括号只弹出，不输出)
- 如果传入数组遍历完毕，则依次弹出栈顶元素存入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
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
111
112
113
114
115
116
117
118
119
120
121
| public class SuffixExpression {
public static void main(String[] args) {
String expression = "1+((23+3)*4)-5";
List<String> expressionList = expressionToList(expression);
System.out.println("中缀表达式字符串转List：" + expressionList);
List<String> suffixList = parseToSuffixExpression(expressionList);
System.out.println("中缀表达式：" + suffixList);
int i = EvalRPNTest.evalRPN(suffixList.toArray(new String[suffixList.size()]));
System.out.println("后缀表达式计算结果：" + i);
}
public static List<String> parseToSuffixExpression(List<String> expressList) {
Stack<String> opStack = new Stack<>();
ArrayList<String> suffixList = new ArrayList<>();
for (String item : expressList) {
if (item.matches("\\d+")) {
suffixList.add(item);
} else if ("+".equals(item) || "-".equals(item) || "*".equals(item) || "/".equals(item)) {
if (opStack.isEmpty() || "(".equals(opStack.peek()) || MyPriority.getPriority(item) > MyPriority.getPriority(opStack.peek())) {
opStack.push(item);
} else {
while (!opStack.isEmpty() && !"(".equals(opStack.peek())) {
if (MyPriority.getPriority(item) <= MyPriority.getPriority(opStack.peek())) {
suffixList.add(opStack.pop());
}
}
opStack.push(item);
}
} else if ("(".equals(item)) {
opStack.push(item);
} else if (")".equals(item)) {
while (!"(".equals(opStack.peek())) {
suffixList.add(opStack.pop());
}
opStack.pop();
}
}
while (!opStack.isEmpty()) {
suffixList.add(opStack.pop());
}
return suffixList;
}
public static List<String> expressionToList(String expression) {
int index = 0;
List<String> list = new ArrayList<>();
do{
char ch = expression.charAt(index);
if(ch < 47 || ch > 58){
index ++ ;
list.add(ch+"");
}else if(ch >= 47 && ch <= 58){
String str = "";
while (index < expression.length() && expression.charAt(index) >=47 && expression.charAt(index) <= 58){
str += expression.charAt(index);
index ++;
}
list.add(str);
}
}while (index < expression.length());
return list;
}
private static class MyPriority {
private static final Integer ADD = 1;
private static final Integer SUB = 1;
private static final Integer MUL = 2;
private static final Integer DIV = 2;
public static Integer getPriority(String opr) {
switch (opr) {
case "+":
return ADD;
case "-":
return SUB;
case "*":
return MUL;
case "/":
return DIV;
default:
return 0;
}
}
}
}
|
3.7 队列ADT
3.7.1 队列模型
队列的入队发生在队列尾，出队出现在队首。类似排队，只能在队尾增加，队首删除。
3.7.2 队列的数组实现
队列的数组与链表都可以实现，都是O(1)的时间运行。如下是数组的实现。
顺序队列：初始时，head与tail指针同时指向0，每当新增元素，tail++，删除元素，head–。直到数组尾部。
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
|
public class SeqArrayQueue<T> {
private int capacity;
private int currentSize;
private int head;
private int tail;
private T[] arr;
public SeqArrayQueue(int cap) {
capacity = cap;
currentSize = 0;
head = 0;
tail = 0;
arr = (T[]) new Object[cap];
}
public void enqueue(T element) {
if (isFull()) {
throw new ArrayIndexOutOfBoundsException("队列越界");
} else {
arr[tail++] = element;
currentSize++;
}
}
public T dequeue() {
if (isEmpty()) {
throw new RuntimeException("队列为空，无法删除");
}
currentSize--;
return arr[head++];
}
public T getHeadElement() {
if (isEmpty()) {
return null;
} else {
return arr[head];
}
}
public T getTailElement() {
if (isEmpty()) {
return null;
} else {
return arr[tail];
}
}
public boolean isFull() {
return tail == capacity-1;
}
public boolean isEmpty() {
return head == tail;
}
}
|
循环队列：初始时，head与tail指针同时指向0，每当新增元素，tail++，删除元素，head–。如数组越界，则插入倒队首对应的位置。
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
| public class LoopArrayQueue<T> {
private int capacity;
private int currentSize;
private int head;
private int tail;
private T[] arr;
public LoopArrayQueue(int cap) {
capacity = cap;
currentSize = 0;
head = 0;
tail = 0;
arr = (T[]) new Object[cap];
}
public void enqueue(T element) {
if (isFull()) {
throw new ArrayIndexOutOfBoundsException("队列越界");
} else {
arr[tail] = element;
tail = (tail+1) % capacity;
currentSize++;
}
}
public T dequeue() {
if (isEmpty()) {
throw new RuntimeException("队列为空，无法删除");
}
currentSize--;
T deQueueElement = arr[head];
head = (head + 1) % capacity;
return deQueueElement;
}
public T getHeadElement() {
if (isEmpty()) {
return null;
} else {
return arr[head];
}
}
public T getTailElement() {
if (isEmpty()) {
return null;
} else {
return arr[tail];
}
}
public boolean isFull() {
return tail == (head + 1) % capacity;
}
public boolean isEmpty() {
return head == tail;
}
}
|