一：栈
栈是限制插入和删除只能在一个位置上进行的表，此位置就是表的末端，叫作栈顶。
栈的基本操作分为push(入栈) 和 pop(出栈),前者相当于插入元素到表的末端（栈顶），后者相当于删除栈顶的元素。
二：栈的实现
|
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
|
public class LinearStack { /** * 栈的初始默认大小为10 */ private int size = 5; /** * 指向栈顶的数组下标 */ int top = -1; /** * 定义栈stack */ private int[] stack; public LinearStack() { stack = new int[size]; } /** * 判断栈满 */ public boolean isFull() { boolean result = false; if(top == size - 1) { result = true; } return result; } /** * 入栈操作push */ public void push(int value) { /** * 如果栈满，拓展栈的容量 */ if(isFull()) stack = expansionStack(); top++; stack[top] = value; } /** * 出栈操作 */ public int pop() { if(top == -1) throw new RuntimeException("栈空！出栈失败"); int result = stack[top] ; top--; return result; } /** * 扩充容量 */ public int[] expansionStack() { size = size + 10; int[] stackTemp = new int[size]; for (int i = 0; i < stack.length; i++) { stackTemp[i] = stack[i]; } return stackTemp; } /** * 获取栈顶的元素 */ public int getTop() { return stack[top]; } /** * 显示栈中的全部元素 */ public String toString() { String str = "["; for (int i = 0; i <= top; i++) { if(i == top) str = str + stack[i] + "]"; else str = str + stack[i] + ","; } return str; }} |
三：栈的测试
|
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
|
public class LinearStackTest { public static void main(String[] args) { LinearStack linearStack = new LinearStack(); /** * 元素入栈 */ linearStack.push(1); linearStack.push(2); linearStack.push(3); linearStack.push(4); linearStack.push(5); /** * 栈满，显示栈中所有元素 */ System.out.println("0：arrayStack " + linearStack.toString()); /** * 再次入栈 */ linearStack.push(6); /** * 再次显示占中的所有元素 */ System.out.println("1：arrayStack: " + linearStack.toString()); /** * 获取栈顶元素 */ System.out.println("获取栈顶元素：stack[top] = " + linearStack.getTop()+" top = " + linearStack.top); /** * 出栈 */ System.out.println("出栈：stack[top] = " + linearStack.pop()+" top = " + linearStack.top); /** * 再次显示栈中的元素 */ System.out.println("2：arrayStack: " + linearStack.toString()); }} |
四：栈的应用（回文序列的判断）
|
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
|
public class LinearStackChar { private int size = 5; /** * 指向栈顶的数组下标 */ int top = -1; /** * 定义栈stack */ private char[] stack; public LinearStackChar() { stack = new char[size]; } /** * 判断栈满 */ public boolean isFull() { boolean result = false; if(top == size - 1) { result = true; } return result; } /** * 入栈操作push */ public void push(char value) { /** * 如果栈满，拓展栈的容量 */ if(isFull()) stack = expansionStack(); top++; stack[top] = value; } /** * 出栈操作 */ public char pop() { if(top == -1) throw new RuntimeException("栈空！出栈失败"); char result = stack[top] ; top--; return result; } /** * 扩充容量 */ public char[] expansionStack() { size = size + 10; char[] stackTemp = new char[size]; for (int i = 0; i < stack.length; i++) { stackTemp[i] = stack[i]; } return stackTemp; } /** * 获取栈顶的元素 */ public char getTop() { return stack[top]; } /** * 显示栈中的全部元素 */ public String toString() { String str = "["; for (int i = 0; i <= top; i++) { if(i == top) str = str + stack[i] + "]"; else str = str + stack[i] + ","; } return str; }} |
|
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
|
public class LinearStackCharTest { public static void main(String[] args) { /** * 判断一个字符串abcba是不是回文序列？ * 思路：将字符串切割成为单个字符，存放在字符栈中； * 然后出栈，判断出栈后字符数组组成的字符串是否和原字符串相等； * 相等--回文序列 * 不相等--不是回文序列 */ String str = "abcba"; LinearStackChar linearStackChar = new LinearStackChar(); //讲字符串切割，存放在栈中 for (int i = 0; i < str.length(); i++) { linearStackChar.push(str.charAt(i)); } //存放完成，显示栈中的元素 System.out.println("stack = " + linearStackChar.toString()); //出栈 String result = ""; int length = linearStackChar.top; System.out.println("top = " + length); for (int i = 0; i <= length; i++) { result = result + String.valueOf(linearStackChar.pop()); } //出栈组成的字符串 System.out.println("result = " + result); //判断是否相等 System.out.println("result = abcba? " + (result.equals("abcba") ? true : false)); }} |
总结
到此这篇关于Java数据结构之栈的线性结构的文章就介绍到这了,更多相关Java栈的线性结构内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！
原文链接：https://juejin.cn/post/6992200772179984415
