数据结构Java实现----栈和队列
程序员文章站
2022-05-11 15:46:34
一、线性栈 ArrayStack类 1 package stack; 2 3 // 线性栈 4 public class ArrayStack implements Stack { 5 private Object[] dataArray = null; 6 private int maxSize ......
一、线性栈
ArrayStack类
1 package stack;
2
3 // 线性栈
4 public class ArrayStack implements Stack {
5 private Object[] dataArray = null;
6 private int maxSize = 0; // 栈的最大容量
7 private int foot = -1; // 栈顶指针
8 private int elementCount = 0; // 栈中含有元素个数
9
10 // 无参构造
11 public ArrayStack() {
12
13 }
14
15 // 构造一个maxSize大小的栈
16 public ArrayStack(int maxSize) {
17 if (maxSize <= 0)
18 return;
19 this.maxSize = maxSize;
20 this.dataArray = new Object[maxSize];
21 }
22
23 // 设置栈的容量
24 public boolean setMaxSize(int maxSize) {
25 if (this.maxSize != 0)
26 return false;
27 this.maxSize = maxSize;
28 this.dataArray = new Object[this.maxSize];
29 return true;
30 }
31
32 // 得到栈的容量
33 public int getMaxSize() {
34 return this.maxSize;
35 }
36
37 // 得到栈含有元素的个数
38 public int getElementCount() {
39 return this.elementCount;
40 }
41
42 // 判空
43 @Override
44 public boolean IsEmpty() {
45 return this.elementCount == 0;
46 }
47
48 // 判满
49 @Override
50 public boolean IsFull() {
51 return this.elementCount == this.maxSize;
52 }
53
54 // 入栈
55 @Override
56 public boolean Push(Object data) {
57 if (data == null)
58 return false;
59 if (this.IsFull())
60 return false;
61
62 // 指针上移 添加元素
63 this.dataArray[++this.foot] = data;
64 this.elementCount++;
65 return true;
66 }
67
68 // 出栈
69 @Override
70 public Object Pop() {
71 if (this.IsEmpty())
72 return null;
73
74 // 取出数据
75 Object data = this.dataArray[this.foot];
76 // 移除数据 指针下移
77 this.dataArray[this.foot--] = null;
78 this.elementCount--;
79 return data;
80 }
81
82 // 查看栈顶元素
83 @Override
84 public Object GetTop() {
85 if (this.IsEmpty())
86 return null;
87 return this.dataArray[foot];
88 }
89
90 // 打印1
91 public void print() {
92 if (this.IsEmpty()) {
93 System.out.println("空栈");
94 return;
95 }
96 int index = this.foot; // 栈顶指针
97 for (; index >= 0;)
98 System.out.print(this.dataArray[index--] + " ");
99 }
100
101 // 判栈相等
102 @Override
103 public boolean equals(Object obj) {
104 if (obj == null)
105 return false;
106
107 // 是ArrayotherStack类
108 if (obj instanceof ArrayStack) {
109 // 造型下转
110 ArrayStack otherStack = (ArrayStack) obj;
111
112 // 含有元素相等
113 if (this.elementCount != otherStack.elementCount)
114 return false;
115
116 // 每个位置上的元素相等
117 int index = this.elementCount; // 比较次数
118 int thisFoot = this.foot; // 当前对象栈顶指针
119 int otherFoot = otherStack.foot; // 比较对象栈顶指针
120 for (; index > 0; --index) {
121 if (this.dataArray[thisFoot] != otherStack.dataArray[otherFoot])
122 return false;
123
124 // 指针下移
125 thisFoot--;
126 otherFoot--;
127 }
128 return true;
129 }
130 return false;
131 }
132
133 // 置空
134 public boolean delete(){
135 this.dataArray = null;
136 this.elementCount = 0;
137 this.foot = -1;
138 this.maxSize = 0;
139 return true;
140 }
141
142 }
TestArrayStack类
1 package Test;
2
3 import stack.ArrayStack;
4
5 // 线性栈测试类
6 public class TestArrayStack {
7
8 public static void main(String[] args) {
9 // 创建一个空栈
10 ArrayStack stack1 = new ArrayStack();
11 System.out.println("设置stack1的容量为5:" + stack1.setMaxSize(5));
12 System.out.println("重复设置stack1的容量:" + stack1.setMaxSize(5));
13 System.out.println("向stack1添加：5 12 10 14 16 20");
14 System.out.print(stack1.Push(5) + " " + stack1.Push(12) + " ");
15 System.out.print(stack1.Push(10) + " " + stack1.Push(14) + " ");
16 System.out.print(stack1.Push(16) + " " + stack1.Push(20) + " \n");
17 stack1.print();
18 System.out.println("\n出栈6次");
19 for (int index = 6; index > 0; --index)
20 System.out.print(stack1.Pop() + " ");
21 stack1.print();
22
23 // 比较栈是否相同
24 ArrayStack stack2 = new ArrayStack(3);
25 ArrayStack stack3 = new ArrayStack(3);
26 ArrayStack stack4 = new ArrayStack(3);
27 ArrayStack stack5 = new ArrayStack(2);
28 System.out.print("比较栈是否相同");
29 stack2.Push(2);
30 stack2.Push(3);
31 stack3.Push(3);
32 stack3.Push(2);
33 stack4.Push(2);
34 stack4.Push(3);
35 stack5.Push(2);
36 stack5.Push(3);
37 System.out.print("stack2: ");
38 stack2.print();
39 System.out.print("stack3: ");
40 stack3.print();
41 System.out.print("stack4: ");
42 stack4.print();
43 System.out.print("stack5：");
44 stack5.print();
45 System.out.println();
46 System.out.print("stack2:stack3 " + stack2.equals(stack3) + " ");
47 System.out.print("stack2:stack4 " + stack2.equals(stack4) + " ");
48 System.out.print("stack2:stack5 " + stack2.equals(stack5) + " ");
49
50 }
51 }
打印
1 设置stack1的容量为5:true 2 重复设置stack1的容量:false 3 向stack1添加：5 12 10 14 16 20 4 true true true true true false 5 16 14 10 12 5 6 出栈6次 7 16 14 10 12 5 null 空栈 8 比较栈是否相同stack2: 3 2 stack3: 2 3 stack4: 3 2 stack5：3 2 9 stack2:stack3 false stack2:stack4 true stack2:stack5 true
二、链式栈
LinkStack类
1 package stack;
2
3 // 链式栈
4 public class LinkStack implements Stack {
5 private Node root = null; // 根节点
6 private int maxSize = 0; // 容量
7 private int elementCount = 0; // 元素个数
8
9 class Node {
10 Object data = null; // 数据域
11 Node next = null; // 指针域
12
13 Node(Object data) {
14 this.data = data;
15 }
16 }
17
18 public LinkStack() {
19
20 }
21
22 public LinkStack(int maxSize) {
23 this.maxSize = maxSize;
24 }
25
26 public boolean SetMaxSize(int maxSize) {
27 if (this.maxSize != 0)
28 return false;
29 this.maxSize = maxSize;
30 return true;
31 }
32
33 @Override
34 public boolean IsEmpty() {
35 return this.elementCount == 0;
36 }
37
38 @Override
39 public boolean IsFull() {
40 return this.elementCount == this.maxSize;
41 }
42
43 @Override
44 public boolean Push(Object data) {
45 if (data == null)
46 return false;
47 if (this.IsFull())
48 return false;
49
50 // 封装结点
51 Node node = new Node(data);
52 this.elementCount++;
53 if (this.IsEmpty()) {
54 this.root = node;
55 return true;
56 }
57 node.next = this.root;
58 this.root = node;
59 return true;
60 }
61
62 @Override
63 public Object Pop() {
64 if (this.IsEmpty())
65 return null;
66
67 // 保存第二个结点信息
68 Object data = this.root.data;
69 if (this.elementCount > 1)
70 this.root = this.root.next;
71 this.elementCount--;
72 return data;
73 }
74
75 @Override
76 public Object GetTop() {
77 return this.root.data;
78 }
79
80 @Override
81 public boolean equals(Object obj) {
82 if (obj == null)
83 return false;
84
85 // 是LinkStack类
86 if (obj instanceof LinkStack) {
87 LinkStack otherStack = (LinkStack) obj;
88 if (this.elementCount != otherStack.elementCount)
89 return false;
90 if (this.elementCount == 0) // 都不含有元素则一定相等
91 return true;
92 Node thisNode = this.root;
93 Node otherNode = this.root;
94
95 while (true) {
96 if (thisNode.data.equals(otherNode.data))
97 return false;
98
99 if (thisNode.next == null)
100 break;
101 thisNode = thisNode.next;
102 otherNode = otherNode.next;
103 }
104 return true;
105 }
106 return false;
107 }
108
109 public void print() {
110 if (this.IsEmpty()) {
111 System.out.println("空栈");
112 return;
113 }
114 Node node = this.root;
115 for (int index = this.elementCount; index > 0; index--) {
116 System.out.print(node.data + " ");
117 node = node.next;
118 }
119 }
120
121 }
TestLinkStack类
1 package Test;
2
3 import stack.LinkStack;
4
5 // 链式栈测试类
6 public class TestLinkStack {
7
8 public static void main(String[] args) {
9 // 创建一个空栈
10 LinkStack stack1 = new LinkStack();
11 System.out.println("设置stack1的容量为5:" + stack1.SetMaxSize(5));
12 System.out.println("重复设置stack1的容量:" + stack1.SetMaxSize(5));
13 System.out.println("向stack1添加：5 12 10 14 16 20");
14 System.out.print(stack1.Push(5) + " " + stack1.Push(12) + " ");
15 System.out.print(stack1.Push(10) + " " + stack1.Push(14) + " ");
16 System.out.print(stack1.Push(16) + " " + stack1.Push(20) + " \n");
17 stack1.print();
18 System.out.println("\n出栈6次");
19 for (int index = 6; index > 0; --index)
20 System.out.print(stack1.Pop() + " ");
21 stack1.print();
22
23 // 比较栈是否相同
24 LinkStack stack2 = new LinkStack(3);
25 LinkStack stack3 = new LinkStack(3);
26 LinkStack stack4 = new LinkStack(3);
27 LinkStack stack5 = new LinkStack(2);
28
29 stack2.Push(2);
30 stack2.Push(3);
31 stack3.Push(3);
32 stack3.Push(2);
33 stack4.Push(2);
34 stack4.Push(3);
35 stack5.Push(2);
36 stack5.Push(3);
37 System.out.print("stack2:");
38 stack2.print();
39 System.out.print("stack3:");
40 stack3.print();
41 System.out.print("stack4:");
42 stack4.print();
43 System.out.print("stack5：");
44 stack5.print();
45 System.out.print("stack2:stack3 " + stack2.equals(stack3) + " ");
46 System.out.print("stack2:stack4 " + stack2.equals(stack4) + " ");
47 System.out.print("stack2:stack5 " + stack2.equals(stack5) + " ");
48
49 }
50
51 }
打印
1 设置stack1的容量为5:true 2 重复设置stack1的容量:false 3 向stack1添加：5 12 10 14 16 20 4 true true true true true false 5 16 14 10 12 5 6 出栈6次 7 16 14 10 12 5 null 空栈 8 stack2: 3 2 stack3: 2 3 stack4: 3 2 stack5：3 2 stack2:stack3 false stack2:stack4 false stack2:stack5 false
上一篇： 手机厂商青睐OLED产能快速释放 OLED产业风口到来
下一篇： 在等下雪呢