Java集合-数据结构
2020-12-13 02:57
标签：源码 数值 one 引用 就是 blank data 最大 删除节点 数据结构部分，复习栈，队列，数组，链表和红黑树，参考博客和资料学习后记录到这里方便以后查看，感谢被引用的博主。 栈(stack)又称为堆栈，是线性表，它只能从栈顶进入和取出元素，有先进后出，后进先出(LIFO, last in first out)的原则，并且不允许在除了栈顶以外任何位置进行添加、查找和删除等操作。栈就相当如手枪的弹夹，先进入栈的数据被压入栈底(bottom)，而后入栈的数据存放在栈顶(top)。当需要出栈时，是先让栈顶的数据出去后，下面的数据才能出去，这就是先进后出的特点。插入数据一般称为进栈或压栈(push)，删除数据则称为出栈或弹栈(pop)。 下面参考博文，地址：https://www.cnblogs.com/ysocean/p/7911910.html，底层使用数组来模拟一个栈的功能，具有push，pop，peek等常用方法，原生的stack是继承自vector类的子类，其具备父类的所有方法，这里模拟除了前面三种方法外，还写了判断自定义栈是否为空，以判断自定义栈是否满等方法。 测试代码，验证自定义栈中的方法。 控制台输出情况。 在上面例子的基础上，依然参考上述博文，自定义一个栈并能实现栈容量自动扩容，以及栈中可以存储不同的数据类型。 测试代码，验证自动扩容，空闲位置是什么。 控制台输出情况。 在参考博文中，栈除了以上用途外，还可以巧妙用在将字符串反转，还有验证分隔符是否匹配，以后如果有需要可以参考引用的博文。 队列(queue)，跟堆栈类似，也是线性表，它是仅允许在尾部(tail)进行插入，在头部(head)进行删除，满足先进先出(FIFO)的原则，类似火车头进入山洞，先进入山洞的车厢就先出来山洞，后进入山洞的火车头后出来山洞。查看队列源码，可以看到接口有如下方法。 简单的整理一下如下。 （1）插入元素到tail尾部：add(e)，offer(e)，前者为执行失败时抛出异常，后者不会抛出但返回特殊值(null或false)。 （2）移除head头部元素：remove()，poll()，前者为执行失败时抛出异常，后者不会抛出但返回特殊值(null或false)。 （3）查看列头head元素：element()，peek()，前者为执行失败时抛出异常，后者不会抛出但返回特殊值(null或false)。 下面分别使用两种类型的方法进行queue操作。 控制台输出结果，可以看出如果实现类为LinkedList时可以插入null，并且看出先加入的Messi，如果执行remove方法后也是先移除，执行element方法也是先查询得到头部元素，因此遵循先进先出原则。 如果不往集合中add元素，直接执行remove方法会发生如下报错，提示没有元素异常，并发现执行remove方法，会执行LinkedList底层的removeFirst方法，说明其移除的就是第一个元素。 同样如果不往集合中添加元素，直接执行element方法会报如下错，也提示没有元素异常，并发现执行element方法时会调用底层的getFirst方法，说明它取得是第一个元素。 可以看出当队列的实现类为LinkedList时，是可以插入null的，如果把实现类更换为PriorityQueue，会发生什么呢？发现会报空指针异常，原因是优先队列不允许插入null。 以上是使用queue的add，remove和element方法，上述同样的情况下，如果更换成offer，poll和peek方法后会是什么情况，看如下代码测试。 以上代码正常情况下执行跟第一种情况一模一样的结果，如果集合为空，直接调用poll方法和peek方法，查看执行结果如下，发现输出均为null，说明在集合为空的情况下这两种方法不会抛出异常。 同样如果将实现类更换为PriorityQueue，往里面添加null，会是什么结果呢？发现依然抛出异常，主要原因查看offer源码发现，如果实现类不支持null就会抛出异常。 另外还有一个deque，是queue的子接口，为双向队列，可以有效的在头部和尾部同时添加或删除元素，其实现类为ArrayDeque和LinkedList类，如果需要一个循环数组队列，选择ArrayDeque，如果需要一个链表队列，使用实现了Queue接口的LinkedList类。 由于Deque实现了Queue接口，因此其可以表现为完全的Queue特征，同时也可以当做栈来使用，具体是Queue还是栈，根据执行的方法来选择，一般来说如果添加元素和删除元素都是在同一端执行(方法后面都为First)，就表现为栈的特性，否则就是Queue的特性，以下是Deque接口的方法。 从以上的方法列表中，大概可以总结出以下几个特点： （1）凡是以add，remove和get开头的方法，都可能在执行的过程中抛出异常，而以offer，poll和peek的方法往往返回null或者其他。 （2）凡是方法后面有Queue接口标志的方法，说明其是继承自接口Queue的方法，有Collection标志的说明是继承自Collection接口的通用方法。 Deque方法参考博文，分类总结如下： 下面简单的用deque的方法来实现集合操作，从队列两端添加，删除和查看元素，和栈以及queue的相关方法不在这里测试了，未来工作中继续感受。 控制台输出结果，可以看出deque可以在head和tail两端进行插入、删除和查看操作。 数组(Array)，是一种有序的元素序列，数组在内存中开辟一段连续的空间，并在连续的空间存放数据，查找数组可以通过数组索引来查找，因此查找速度快，但是增删元素慢。数组创建以后在程序运行期间长度是不变的，如果要增加一个元素，会创建一个新的数组，将新元素存储到索引位置，并将原数组根据索引一一复制到新数组，原来的数组被gc回收，新数组的内存地址赋值给数组变量。 关于数组部分，直接可以从自己写的博客查看具体内容，博客地址：https://www.cnblogs.com/youngchaolin/p/10987960.html，另外参考了大牛博客，进行一些知识面的扩展。 底层利用数组，也可以实现数据结构的基本功能，简单概括一下，就是需要具备增删改查循环遍历的功能，这样才能算实现基本的数据结构，下面参考博客，进行这些功能的封装，实现一个基于数组的简单数据结构。 测试类来测试上面写的数据结构。 控制台输出情况，发现可以正常的实现增删改查和循环遍历的功能。 链表(linked list),是由一系列结点node组成，结点包含两个部分，一个是存储数据的数据域，一个是存储下一个节点地址以及自己地址的地址域，即链表是双向链接的(double linked)，多个节点通过地址进行连接，组成了链表，其特点是增删元素快，只要创建或删除一个新的节点，内存地址重新指向规划就行，但是查询元素慢，需要通过连接的节点从头开始依次向后查找。 依然参考博主系列文章的链表，自己实现一个自定义的链表，并具有增加头部元素、删除指定元素、修改指定元素、查找元素以及展示链表内容等功能。栈
自定义栈，底层采用数组模拟
1 package dataStructure;
2 /**
3 * 自定义栈，使用数组来实现
4 */
5 public class MyStack {
6
7 private int size;//数组大小
8 private String[] arr;//数组
9 private int top=-1;//默认栈顶位置
10
11 //构造方法
12 public MyStack(int size) {
13 this.size = size;
14 arr=new String[size];
15 }
16
17 //压栈
18 public void push(String value){
19 //top范围0到size-1
20 if(top){
21 arr[++top]=value;
22 }
23 }
24
25 //出栈
26 public String pop(){
27 //原栈顶元素设置为null，等待gc自动回收
28 return arr[top--];
29 }
30
31 //查看栈顶
32 public String peek(){
33 if(top>-1){
34 return arr[top];
35 }else{
36 return null;
37 }
38 }
39
40 //检查栈是否为空
41 public boolean Empty(){
42 return top;
43 }
44
45 //检查栈是否满
46 public boolean Full(){
47 return top==size-1;
48 }
49
50 //检查栈中元素数量
51 public String size(){
52 int count=top+1;
53 return "栈中元素:"+count+" | 栈容量"+size;
54 }
55
56 }
1 package dataStructure;
2
3 public class TestMyStack {
4
5 public static void main(String[] args) {
6 //测试自定义Stack
7 MyStack stack=new MyStack(3);
8 //压入栈顶
9 stack.push("Messi");
10 stack.push("Ronald");
11 stack.push("Herry");
12
13 //查看栈中元素数量
14 System.out.println(stack.size());
15
16 //查看栈顶元素
17 System.out.println(stack.peek());
18
19 //循环遍历栈中元素
20 while(!stack.Empty()){
21 System.out.println(stack.pop());
22 }
23
24 //判断栈是否为空
25 System.out.println(stack.Empty()); //true
26 System.out.println(stack.size());
27
28 }
29
30 }
自定义一个栈，实现数组自动扩容并能储存不同的数据类型
1 package dataStructure;
2
3 import java.util.Arrays;
4 import java.util.EmptyStackException;
5
6 /**
7 * 自定义栈，使用数组来实现，可以实现数组自动扩容，以及存储不同的数据类型
8 */
9 public class MyArrayStack {
10 //定义属性
11 private int size;//容量
12 private Object[] arr;//对象数组
13 private int top;//栈顶位置
14
15 //默认构造方法
16 public MyArrayStack() {
17 this.size=10;
18 this.arr=new Object[10];
19 this.top=-1;
20 }
21
22 //自定义数组容量的构造方法
23 public MyArrayStack(int size) {
24 if(size){
25 throw new IllegalArgumentException("栈容量不能小于0"+size);
26 }
27 this.size = size;
28 this.arr=new Object[size];
29 this.top=-1;
30 }
31
32 //压栈
33 public Object push(Object value){
34 //压栈之前欠判断数组容量是否足够，不够就扩容
35 getNewCapacity(top+1);
36 arr[++top]=value;
37 return value;
38 }
39
40 //出栈
41 public Object pop(){
42 if(top==-1){
43 throw new EmptyStackException();
44 }
45 Object obj=arr[top];
46 //删除原来栈顶的位置，默认设置为null，等待gc自动回收
47 arr[top--]=null;
48 return obj;
49 }
50
51 //查找栈顶的元素
52 public Object peek(){
53 return arr[top];
54 }
55
56 //判断栈是否为空
57 public boolean Empty(){
58 return top==-1;
59 }
60
61 //检查栈中元素
62 public String size(){
63 int count=top+1;
64 return "栈中元素:"+count+" | 栈容量"+size;
65 }
66
67 //返回栈顶到数组末端内容
68 public void printWaitPosition(){
69 if(top
1 package dataStructure;
2
3 public class TestMyArrayStack {
4
5 public static void main(String[] args) {
6 // 测试自定义MyArrayStack
7 MyArrayStack stack=new MyArrayStack(2);
8 stack.push("Messi");
9 stack.push("Ronald");
10 System.out.println(stack.size());
11 System.out.println(stack.peek());
12 //超出容量后继续压栈
13 stack.push("boy you will have a good future");
14 System.out.println(stack.size());
15 System.out.println(stack.peek());
16 //打印stack中空闲位置内容
17 stack.printWaitPosition();
18 //压入数字
19 stack.push(8848);
20 System.out.println(stack.size());
21 System.out.println(stack.peek());
22 stack.printWaitPosition();
23 //压入布尔类型
24 stack.push(true);
25 System.out.println(stack.size());
26 System.out.println(stack.peek());
27 stack.printWaitPosition();
28 }
29 }
队列
使用会抛出异常的方法
1 package DataCompose;
2
3 import java.util.LinkedList;
4 import java.util.PriorityQueue;
5 import java.util.Queue;
6
7 /**
8 * 测试队列，队列Queue具有先进先出的特点
9 */
10 public class QueueTest {
11
12 public static void main(String[] args) {
13 //创建一个队列，使用LinkedList来创建对象，并被接口指向
14 Queue
1 package DataCompose;
2
3 import java.util.LinkedList;
4 import java.util.PriorityQueue;
5 import java.util.Queue;
6
7 /**
8 * 测试队列，队列Queue具有先进先出的特点
9 */
10 public class QueueTest1 {
11
12 public static void main(String[] args) {
13 //创建一个队列，使用LinkedList来创建对象，并被接口指向
14 Queue
deque和栈的方法对照表
deque和queue的方法对照表
deque中抛出异常和返回其他值的方法
1 package DataCompose;
2
3 import java.util.Deque;
4 import java.util.LinkedList;
5
6 /**
7 * 测试双向队列，其可以表现为Queue，也可以表现为Stack，这里测试双向列队
8 */
9 public class DequeTest {
10
11 public static void main(String[] args) {
12 //使用链表实现
13 Deque
数组
1 package DataCompose;
2
3 /**
4 * 数组测试，理解最基本数据结构，利用数组封装一个简单的数据结构，实现增删改查和循环遍历
5 */
6 public class ArrayTest {
7 //底层数组，使用Object类型
8 private Object[] arr;
9 //数组占用长度
10 private int length;
11 //数组容量
12 private int maxSize;
13
14 //默认构造方法，仿造ArrayList，默认长度为10
15 public ArrayTest() {
16 this.length=0;
17 this.maxSize=10;
18 arr=new Object[maxSize];
19 }
20
21 //自定义数组长度
22 public ArrayTest(int maxSize) {
23 this.maxSize = maxSize;
24 this.length=0;
25 arr=new Object[maxSize];
26 }
27 //增加元素
28 public boolean add(Object obj){
29 //增加元素暂时不使用底层再创建一个新的数组，进行数组内容复制，参考博客直接添加
30 if(length==maxSize){
31 System.out.println("数组容量达到极限，无法自动扩容");
32 return false;
33 }
34 //原数组后面再添加一个元素，否则就是初始值null
35 arr[length++]=obj;
36 return true;
37 }
38 //查找元素，本来先要写删，但是删元素之前需要先查是否存在，因此先写查询方法
39 public int find(Object obj){
40 int n=-1;
41 for (int i= 0; i) {
42 if(obj.equals(arr[i])){
43 n=i;
44 break;
45 }
46 }
47 return n;
48 }
49 //删除元素
50 public boolean remove(Object obj){
51
52 if(obj==null){
53 System.out.println("不能删除null，请输入正常内容");
54 return false;
55 }
56 int index=find(obj);
57 if(index==-1){
58 System.out.println("不存在的元素:"+obj);
59 return false;
60 }
61 //数组元素覆盖操作
62 if(index==length-1){
63 length--;
64 }else{
65 for(int i=index;i
1 package DataCompose;
2
3 /**
4 * 测试自己底层用数组写的数据结构
5 */
6 public class TestArrayTest {
7
8 public static void main(String[] args) {
9 ArrayTest arr=new ArrayTest(5);
10 //添加元素
11 arr.add("boy you will have girl");
12 arr.add(true);
13 arr.add("how many would you like");
14 arr.add(1);
15
16 //打印数组
17 arr.toArrayString();
18
19 //查询为1的元素
20 System.out.println(arr.find(1));
21
22 //查询‘你好‘
23 System.out.println(arr.find("你好"));
24
25 //修改下标为3的数组为100
26 arr.modify(3,100);
27 arr.toArrayString();
28
29 //再添加一个元素
30 arr.add("哈哈哈");
31 arr.toArrayString();
32
33 //继续添加
34 arr.add("ok?");
35
36 //删除最后的元素
37 boolean result=arr.remove("哈哈哈");
38 System.out.println(result);
39 arr.toArrayString();
40
41 }
42 }
链表
链表有单向链表和双向链表之分。
单向链表：链表中只有一条‘链子‘，元素存储和取出的顺序可能不一样，不能保证元素的顺序。
双向链表：链表中除了有单向链表一条链子外，还有一条链子用于记录元素的顺序，因此它可以保证元素的顺序。单向链表的实现
1 package DataCompose;
2
3 /**
4 * 单向列表测试，
5 */
6 public class SingleLinkTest {
7 //定义链表大小
8 private int size;
9 //定义头节点，只需要定义一个头，其他元素都可以通过这个节点头来找到
10 private Node head;
11
12 public SingleLinkTest() {
13 this.size = 0;
14 this.head = null;
15 }
16
17 //在链表头部增加元素
18 public Object addHead(Object obj) {
19 //得到一个新的节点
20 Node newNode = new Node(obj);
21 //链表为空，将头元素数据设置为obj
22 if (size == 0) {
23 head = newNode;
24 } else {
25 newNode.next = head;
26 head = newNode;
27 }
28 this.size++;
29 return obj;
30 }
31
32 //在链表中删除元素
33 public boolean delete(Object obj) {
34 //要删除一个元素，需要首先找到这个元素，将这个元素前一个元素next属性指向这个元素的下一个元素
35 if (size == 0) {
36 System.out.println("链表为空，无法删除！");
37 return false;
38 }
39 //都是从头部开始查询，有找到需要删除的节点就删除，删除后将这个节点前一个节点next属性指向删除节点的下一个节点
40 //需要重新指向的话，需要删除节点数据，也需要删除节点前一个节点的数据，刚开始都使用头部节点数据
41 Node previousNode = head;
42 Node currentNode = head;
43 //什么时候找到这个元素什么时候停止
44 while (!currentNode.data.equals(obj)) {
45 //节点往后遍历，寻找下一个节点数据
46 if (currentNode.next == null) {
47 System.out.println("已到链表末尾，无需要删除的元素");
48 return false;
49 } else {
50 //重置当前结点和当前结点前一个结点
51 previousNode = currentNode;
52 currentNode = currentNode.next;
53 }
54 }
55
56 //能执行到这里说明有需要删除的元素
57 size--;
58 if (currentNode == head) {
59 head = currentNode.next;
60 } else {
61 previousNode.next = currentNode.next;
62 }
63 return true;
64 }
65
66 //修改元素
67 public boolean modify(Object old, Object newObj) {
68 if (size == 0) {
69 System.out.println("链表为空，无法修改元素");
70 return false;
71 }
72 Node currentNode = head;
73 while (!currentNode.data.equals(old)) {
74 if (currentNode.next == null) {
75 System.out.println("已到链表末尾，无需要删除的元素");
76 return false;
77 } else {
78 currentNode = currentNode.next;
79 }
80 }
81
82 //能执行到这里说明有相同的元素
83 currentNode.data = newObj;
84 return true;
85
86 }
87
88 //查找元素
89 public boolean find(Object obj) {
90 if (size == 0) {
91 System.out.println("链表为空");
92 }
93 Node currentNode = head;
94 while (!currentNode.data.equals(obj)) {
95 if (currentNode.next == null) {
96 System.out.println("已到链表末尾，无查找的元素");
97 return false;
98 } else {
99 currentNode = currentNode.next;
100 }
101 }
102
103 //能执行到这里说明查找到了元素
104 System.out.println("查找元素存在链表中");
105 return true;
106 }
107
108 //遍历输出元素<
上一篇：不用windows不会死
下一篇：Map 有2个数组，第一个数组内容为：[河南省,浙江省,江西省,广东省,福建省]， 第二个数组为：[郑州,杭州,南昌,广州,福州]， 将第一个数组元素作为key，第二个数组元素作为value存储到