Java进阶篇--数据结构

目录

一.数组(Array):

1.1  特点:

1.2  基本操作:

1.3  使用数组的好处包括:

1.4  数组也有一些限制:

二.集合框架(Collections Framework):

2.1  列表(List):

2.1.1  数组列表(ArrayList):

扩展知识:

方法:

ArrayList的遍历方式

ArrayList使用泛型

Arrays工具类

2.1.2  链表(LinkedList):

常用方法:

2.1.3  使用选择:

2.1.4  示例代码:

2.2  集(Set):

2.2.1  哈希集(HashSet):

基本类型对应的包装类表如下:

HashSet的常用方法包括:

2.2.2  树集(TreeSet):

TreeSet的常用方法包括:

2.2.3  使用选择:

2.2.4  示例代码:

2.3  映射(Map):

2.3.1  哈希映射(HashMap):

2.3.2  树映射(TreeMap):

2.3.3  使用选择

2.3.4  示例代码

三.栈(Stack)和队列(Queue):

3.1方法

3.2示例代码

四.树(Tree):

4.1  二叉树(Binary Tree):

4.2二叉搜索树(Binary Search Tree):

4.3  操作方法

4.4  树的遍历

4.4.1树的遍历包括两种主要方式:

4.4.2  树的两种基本遍历方式:

4.5  示例代码

五.图(Graph):

六.堆(Heap):

七.链表(LinkedList):

八.MAP:


Java 提供了多种数据结构来有效地组织和处理数据。以下是一些常见的 Java 数据结构:

一.数组(Array):

数组(Array)是一种线性数据结构,用于存储固定大小的相同类型元素的连续序列,可以通过索引快速访问和修改元素。。在 Java 中,数组可以包含基本类型(如 int、double、char 等)或引用类型(如对象、字符串等)的元素。

1.1  特点:

  1. 元素类型必须相同,即数组是同一类型的项的集合。
  2. 长度固定,在创建数组时需要指定大小,后续无法改变。
  3. 内存中分配连续的空间,元素之间存储紧密,通过索引快速访问和修改元素。

1.2  基本操作:

  • 初始化:创建一个数组,并为其赋初值。

  • 遍历:使用循环遍历数组中的每个元素。

  • 打印:将数组中的元素依次输出。

  • 最大值:遍历数组,通过比较找到数组中的最大值。

  • 最大值下标:遍历数组,记录当前最大值的下标。

  • 使用增强for循环(foreach):对于数组中的每个元素,可以使用增强for循环进行遍历并执行相应的操作。
  • 复制数组有三种方法:
  1. 遍历原数组,逐个复制到新数组。
  2. 使用System.arraycopy()方法进行数组复制。
  3. 使用数组的clone()方法复制数组。
  • 线性查找::从数组的第一个元素开始逐个比较,直到找到目标元素或遍历完整个数组。时间复杂度为O(n),其中n为数组长度。
  • 二分查找:要求在已排序的数组中进行查找。首先确定数组的中间元素,将目标值与中间元素进行比较,若相等则返回该位置,若小于中间元素,则在左半部分继续查找,若大于中间元素,则在右半部分继续查找。重复以上步骤,直到找到目标值或查找范围为空。时间复杂度为O(logn),其中n为数组长度。
  • 选择排序:每次遍历找到当前范围内的最小(或最大)元素,并将其放置在已排序的部分的末尾。通过不断选择最小(或最大)的元素,逐步完成整个数组的排序。注意,选择排序的时间复杂度为O(n^2),其中n为数组的长度。虽然简单易实现,但对于较大规模的数据可能效率较低。

以下的Java代码示例,包含数组的初始化、遍历、打印、最大值、最大值下标、使用增强for循环遍历、复制数组以及线性查找、二分查找和选择排序算法的实现。

import java.util.Arrays;

public class myClass {
    public static void main(String[] args) {
        // 初始化数组
        int[] arr = {5, 3, 9, 1, 7};

        // 遍历数组
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();

        // 打印数组
        System.out.println(Arrays.toString(arr));

        // 最大值
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        System.out.println("最大值:" + max);

        // 最大值下标
        int maxIndex = 0;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > arr[maxIndex]) {
                maxIndex = i;
            }
        }
        System.out.println("最大值下标:" + maxIndex);

        // 使用增强for循环遍历
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();

        // 复制数组方法一(遍历原数组,逐个复制到新数组)
        int[] copyArr1 = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            copyArr1[i] = arr[i];
        }

        // 复制数组方法二(使用System.arraycopy()方法)
        int[] copyArr2 = new int[arr.length];
        System.arraycopy(arr, 0, copyArr2, 0, arr.length);

        // 复制数组方法三(使用数组的clone()方法)
        int[] copyArr3 = arr.clone();

        System.out.println("复制后的数组:" + Arrays.toString(copyArr3));

        // 线性查找
        int target = 9;
        int linearSearchIndex = -1;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                linearSearchIndex = i;
                break;
            }
        }
        System.out.println("线性查找:" + (linearSearchIndex != -1 ? linearSearchIndex : "未找到"));

        // 二分查找(前提是数组必须有序)
        Arrays.sort(arr); // 先排序
        int binarySearchIndex = Arrays.binarySearch(arr, target);
        System.out.println("二分查找:" + (binarySearchIndex >= 0 ? binarySearchIndex : "未找到"));

        // 选择排序
        selectionSort(arr);
        System.out.println("选择排序后的数组:" + Arrays.toString(arr));
    }

    // 选择排序算法实现
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }
}

运行结果:

5 3 9 1 7 
[5, 3, 9, 1, 7]
最大值:9
最大值下标:2
5 3 9 1 7 
复制后的数组:[5, 3, 9, 1, 7]
线性查找:2
二分查找:4
选择排序后的数组:[1, 3, 5, 7, 9]

1.3  使用数组的好处包括:

  1. 快速随机访问:由于元素在内存中连续存储,所以可以通过索引快速定位和访问元素。
  2. 内存效率:数组在创建时需要指定长度,适用于已知固定数量的元素存储场景,不需要额外的指针或链接信息。
  3. 数组操作简单:Java 提供了一些便利的方法和属性,使得数组的操作更加简单和高效。

1.4  数组也有一些限制:

  • 长度固定:一旦创建,长度无法改变,需要事先确定好所需的元素个数。
  • 内存浪费:如果数组长度过大或未充分利用,会造成内存浪费。
  • 数据类型:数组只能存储一种类型的数据;
  • 插入和删除困难:在数组中插入或删除元素可能需要移动其他元素,开销较大。

二.集合框架(Collections Framework):

提供了一系列接口和类,用于存储和操作对象的集合。常用的集合类包括:

2.1  列表(List):

有序、可重复的集合,例如 ArrayList、LinkedList。

2.1.1  数组列表(ArrayList):

  1. ArrayList是基于数组实现的动态数组,内部通过数组来存储元素。
  2. 它可以自动扩容以适应元素的增加
  3. 它支持随机访问元素,即可以通过索引快速访问指定位置的元素。
  4. 数组列表适用于频繁读取和随机访问元素的场景,因为它内部使用数组存储,可以根据索引直接计算出元素的内存地址。
  5. ArrayList实现了List接口,继承了AbstractList类,并且还实现了RandomAccess(随机访问)、Cloneable(克隆)和Serializable(可序列化)这些接口。
  6. 与Vector不同,ArrayList不是线程安全的。因此,在单线程环境下建议使用ArrayList,在多线程环境下可以选择Vector或CopyOnWriteArrayList。

扩展知识:

Vector是Java中的一个旧的类,它与ArrayList具有相似的用法,但在性能和使用上存在一些差异。虽然Vector是线程安全的,但在大多数情况下,推荐使用更现代的替代方案。

一个常见的替代方案是使用Collections工具类提供的synchronizedList方法,该方法可以将ArrayList转换为线程安全的List。以下是示例代码:

List<String> lst = new ArrayList<>();
// 往lst中添加元素

List<String> synList = Collections.synchronizedList(lst);

通过将原始的ArrayList通过synchronizedList方法包装,我们可以获得一个在并发环境下安全使用的List。

需要注意的是,在大多数情况下,如果不需要线程安全的特性,推荐使用ArrayList而不是Vector,因为ArrayList在性能上通常更优。只有在确实需要线程安全时,才会考虑使用Vector或通过Collections工具类获得线程安全的List。

方法

Collection相关方法:

这些方法属于Collection类的一部分,可以被List和Set等子类继承并使用。以下是一些常见的Collection类方法:

  1. boolean add(E element):向集合中添加一个元素。
  2. boolean addAll(Collection<? extends E> collection):将一个集合中的所有元素添加到当前集合中。
  3. void clear():清空集合中的所有元素。
  4. boolean contains(Object object):判断集合是否包含指定对象。
  5. boolean containsAll(Collection<?> collection):判断集合是否包含给定集合中的所有元素。
  6. boolean isEmpty():判断集合是否为空。
  7. Iterator<E> iterator():返回一个用于迭代集合元素的迭代器。
  8. boolean remove(Object object):从集合中移除指定的对象。
  9. boolean removeAll(Collection<?> collection):从集合中移除给定集合中的所有元素。
  10. boolean retainAll(Collection<?> collection):仅保留集合中在给定集合中出现的元素,移除其他元素。
  11. int size():返回集合中的元素个数。
  12. Object[] toArray():将集合转化为数组。
  13. <T> T[] toArray(T[] array):将集合转化为指定类型的数组。

List接口:

List是Collection接口的子接口,拥有Collection所有方法外,还有一些对索引操作的方法。

  • void add(int index, E element):在索引index处插入元素element。
  • boolean addAll(int index, Collection<? extends E> c):将集合c中的所有元素插入到索引index处。
  • E remove(int index):移除并返回索引index处的元素。
  • int indexOf(Object o):返回对象o在ArrayList中第一次出现的索引。
  • int lastIndexOf(Object o):返回对象o在ArrayList中最后一次出现的索引。
  • E set(int index, E element):将索引index处的元素替换为新的element对象,并返回被替换的旧元素。
  • E get(int index):返回索引index处的元素。
  • List<E> subList(int fromIndex, int toIndex):返回从索引fromIndex(包含)到索引toIndex(不包含)的子列表。
  • void sort(Comparator<? super E> c):根据指定的Comparator对ArrayList中的元素进行排序。
  • void replaceAll(UnaryOperator<E> operator):使用指定的计算规则operator重新设置ArrayList的所有元素。
  • ListIterator<E> listIterator():返回一个ListIterator对象,该接口继承了Iterator接口,在Iterator接口基础上增加了以下方法,允许向前迭代并添加元素。
  • bookean hasPrevious():返回迭代器关联的集合是否还有上一个元素;
  • E previous();:返回迭代器上一个元素;
  • void add(E e);:在指定位置插入元素;

更多 API 方法可以查看:ArrayList

ArrayList的遍历方式

  1. 使用for循环和索引:
    for (int i = 0; i < arrayList.size(); i++) {
        E element = arrayList.get(i);
        // 处理元素
    }
    
  2. 使用for-each循环:
    for (E element : arrayList) {
        // 处理元素
    }
    
  3. 使用迭代器(Iterator)进行遍历:
    Iterator<E> iterator = arrayList.iterator();
    while (iterator.hasNext()) {
        E element = iterator.next();
        // 处理元素
    }
    

ArrayList<E>使用泛型

泛型数据类型,用于设置 objectName(对象名) 的数据类型,只能为引用数据类型

对于ArrayList的泛型使用,可以通过在定义ArrayList时指定泛型类型来确保集合中只能存储指定类型的元素。例如:

ArrayList<String> stringList = new ArrayList<>();
stringList.add("Hello");
stringList.add("World");
// 只能添加String类型的元素

String element = stringList.get(0);
System.out.println(element);  // 输出: Hello

通过使用泛型,可以提供类型安全,并且在编译期间就能够捕获类型不匹配的错误。 

Arrays工具类

Arrays工具类是Java提供的用于操作数组的工具类,以下是一些常用的方法:

  1. boolean equals(a, b):比较两个数组是否相等。
  2. void fill(array, value):将指定的值填充到数组中的所有元素。
  3. void sort(array):对数组进行排序。
  4. int binarySearch(array, key):在已排序的数组中使用二分查找来查找指定的元素。
  5. void arraycopy(src, srcPos, dest, destPos, length):将源数组中的某个范围的元素复制到目标数组的指定位置。

2.1.2  链表(LinkedList):

  1. LinkedList是基于链表实现的双向链表,内部通过节点(Node)来存储元素并连接起来。
  2. 节点中包含了当前元素的值,以及指向前一个节点和后一个节点的引用。
  3. 链表支持快速插入和删除操作,因为只需要修改节点的引用关系即可,不涉及移动其他元素。
  4. 链表适用于频繁插入和删除元素的场景,因为在链表中插入和删除元素的开销相对较小。
  5. 由于链表的存储方式不同于数组,因此在访问某个位置的元素时需要遍历链表,因此随机访问的效率较低。

常用方法:

  • void addFirst(E element):在链表的开头插入元素。
  • void addLast(E element):在链表的末尾插入元素。
  • E getFirst():获取链表中的第一个元素。
  • E getLast():获取链表中的最后一个元素。
  • E removeFirst():移除并返回链表中的第一个元素。
  • E removeLast():移除并返回链表中的最后一个元素。
  • boolean contains(Object element):判断链表是否包含指定元素。
  • int size():返回链表中的元素个数。
  • void clear():清空链表中的所有元素。

更多 API 方法可以查看:LinkedList

2.1.3  使用选择:

根据具体需求,选择ArrayList还是LinkedList有以下一些考虑因素:

  1. 如果需要频繁读取和随机访问元素,可以选择ArrayList。
  2. 如果需要频繁插入和删除元素,尤其是在列表的中间位置,可以选择LinkedList。
  3. 如果对内存空间的利用比较敏感,LinkedList可能会占用更多的内存,而ArrayList使用的内存通常较为紧凑。

总的来说,ArrayList适用于读取和随机访问操作更多的场景,而LinkedList适用于插入和删除操作更频繁的场景。

2.1.4  示例代码:

下面一个简单的示例代码,展示了如何使用ArrayList和LinkedList进行基本操作:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class ListExample {
    public static void main(String[] args) {
        // 使用ArrayList
        List<String> arrayList = new ArrayList<>();

        // 添加元素
        arrayList.add("Apple");
        arrayList.add("Banana");
        arrayList.add("Orange");

        // 获取元素
        String firstElement = arrayList.get(0);
        System.out.println("ArrayList中第一个元素:" + firstElement);

        // 遍历元素
        System.out.println("ArrayList的元素:");
        for (String element : arrayList) {
            System.out.println(element);
        }

        // 删除元素
        arrayList.remove("Banana");

        // 使用LinkedList
        List<Integer> linkedList = new LinkedList<>();

        // 添加元素
        linkedList.add(10);
        linkedList.add(20);
        linkedList.add(30);

        // 获取元素
        int lastElement = linkedList.get(linkedList.size() - 1);
        System.out.println("LinkedList中最后一个元素:" + lastElement);

        // 遍历元素
        System.out.println("LinkedList的元素:");
        for (int element : linkedList) {
            System.out.println(element);
        }

        // 删除元素
        linkedList.remove(0);
    }
}

运行结果:

ArrayList中第一个元素:Apple
ArrayList的元素:
Apple
Banana
Orange
LinkedList中最后一个元素:30
LinkedList的元素:
10
20
30

2.2  集(Set):

集是一种无序的集合,不允许重复元素,例如 HashSet、TreeSet。

2.2.1  哈希集(HashSet):

  1. HashSet是基于哈希表实现的集合,具有快速查找性能。
  2. 哈希集不保证元素的顺序,且不允许重复元素。如果试图插入重复元素,插入操作将被忽略。
  3. 它还继承了Set接口和Collection接口的其他方法
  4. HashSet允许存储null元素。
  5. 添加、删除和查找元素的平均时间复杂度为O(1)

HashSet 中的元素实际上是对象,一些常见的基本类型可以使用它的包装类。

基本类型对应的包装类表如下:

基本类型引用类型
booleanBoolean
byteByte
shortShort
intInteger
longLong
floatFloat
doubleDouble
charCharacter

HashSet的常用方法包括:

  1. boolean add(E element):向集合中添加指定元素,如果元素已经存在,则返回false。
  2. boolean remove(Object element):从集合中移除指定元素,如果元素存在并成功移除,则返回true。
  3. boolean contains(Object element):检查集合中是否包含指定元素,如果包含则返回true。
  4. int size():返回集合中元素的数量。
  5. void clear():清空集合中的所有元素。 

更多 API 方法可以查看:HashSet 

2.2.2  树集(TreeSet):

  1. TreeSet是基于红黑树(自平衡二叉搜索树)实现的有序集合。
  2. 树集中的元素按照自然顺序或自定义比较器进行排序,默认情况下按照元素的自然排序方式进行排序。
  3. 它还继承了Set接口和Collection接口的其他方法
  4. 树集不允许插入null元素。
  5. 插入、删除和查找元素的时间复杂度为O(log N),其中N为树集中的元素个数。

TreeSet的常用方法包括:

  1. boolean add(E element):向集合中添加指定元素,如果元素已经存在,则返回false。
  2. boolean remove(Object element):从集合中移除指定元素,如果元素存在并成功移除,则返回true。
  3. boolean contains(Object element):检查集合中是否包含指定元素,如果包含则返回true。
  4. int size():返回集合中元素的数量。
  5. void clear():清空集合中的所有元素。
  6. E first():返回集合中的第一个(最小)元素。
  7. E last():返回集合中的最后一个(最大)元素。
  8. Iterator<E> iterator():返回在此集合上进行迭代的迭代器。

2.2.3  使用选择:

  1. 使用HashSet时,你可以快速添加、删除和查找元素,并且元素的顺序可能不同。
  2. 如果你希望元素有一定的顺序,你可以使用TreeSet,它会根据元素的排序规则保持元素的有序性。

2.2.4  示例代码:

下面一个简单的示例代码,展示了如何使用HashSet和TreeSet进行基本操作:

import java.util.HashSet;// 引入 HashSet 类
import java.util.TreeSet;// 引入 TreeSet 类

public class myClass {
    public static void main(String[] args) {
        // 使用HashSet
        HashSet<String> hashSet = new HashSet<>();

        // 添加元素
        hashSet.add("Apple");
        hashSet.add("Banana");
        hashSet.add("Orange");
        hashSet.add("Grape");

        // 输出集合中的元素
        System.out.println("HashSet:");
        for (String fruit : hashSet) {
            System.out.println(fruit);
        }

        // 检查元素是否存在
        System.out.println("HashSet contains 'Apple': " + hashSet.contains("Apple")); // true

        // 删除元素
        hashSet.remove("Orange");

        // 输出修改后的集合
        System.out.println("HashSet after removal:");
        for (String fruit : hashSet) {
            System.out.println(fruit);
        }

        // 使用TreeSet
        TreeSet<Integer> treeSet = new TreeSet<>();

        // 添加元素
        treeSet.add(5);
        treeSet.add(10);
        treeSet.add(3);
        treeSet.add(8);

        // 输出集合中的元素
        System.out.println("TreeSet:");
        for (int num : treeSet) {
            System.out.println(num);
        }

        // 获取最小元素和最大元素
        System.out.println("Min element: " + treeSet.first()); // 3
        System.out.println("Max element: " + treeSet.last()); // 10
    }
}

运行结果:

HashSet:
Apple
Grape
Orange
Banana
HashSet contains 'Apple': true
HashSet after removal:
Apple
Grape
Banana
TreeSet:
3
5
8
10
Min element: 3
Max element: 10

2.3  映射(Map):

由键值对组成的集合,每个键唯一,例如 HashMap、TreeMap。

2.3.1  哈希映射(HashMap):

  1. 它是基于哈希表实现的映射结构。
  2. HashMap是一个散列表,它存储的内容是键值对(key-value)映射。
  3. HashMap使用键的哈希码来确定存储位置,实现了 Map 接口,通过键快速查找值。
  4. 它具有较快的插入和查找操作,但不保证元素的顺序。

常用方法:

  1. put(key, value): 将键值对插入到哈希映射中。
  2. get(key): 根据键获取对应的值。
  3. containsKey(key): 检查哈希映射中是否包含指定的键。
  4. remove(key): 移除哈希映射中指定键的键值对。
  5. size(): 返回哈希映射中键值对的数量。

更多 API 方法可以查看:HashMap

2.3.2  树映射(TreeMap):

  1. 它是基于红黑树实现的有序映射结构。
  2. TreeMap将键按照自然顺序或通过自定义的比较器进行排序,并在内部维护一个有序的键值对集合。因此,可以根据键的顺序快速检索、遍历和范围查找元素。

常用方法:

  1. put(key, value): 将键值对插入到树映射中。
  2. get(key): 根据键获取对应的值。
  3. containsKey(key): 检查树映射中是否包含指定的键。
  4. remove(key): 移除树映射中指定键的键值对。
  5. size(): 返回树映射中键值对的数量。
  6. firstKey(): 返回树映射中最小的键。
  7. lastKey(): 返回树映射中最大的键。
  8. subMap(fromKey, toKey): 返回树映射中键的一个子集,范围从 fromKey(包括)到 toKey(不包括)。

除了上述方法,哈希映射和树映射还提供了其他一些类似的方法,如获取所有键的集合、清空映射等。具体的方法使用可以参考Java的官方文档或相关教程。

2.3.3  使用选择

这两种映射都是非常常用的数据结构,在不同的场景下使用。

  • HashMap适用于需要快速查找和插入元素的情况,并且不关心元素的顺序。
  • TreeMap适用于需要有序性的场景,可以按照键的顺序进行操作和遍历,在维护有序性的同时支持各种基本操作。

2.3.4  示例代码

下面一个简单的示例代码,展示了如何使用HashMap和TreeMap进行基本操作:

import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

public class myClass {
    public static void main(String[] args) {
        // 使用HashMap
        Map<String, Integer> hashMap = new HashMap<>();

        // 添加键值对到HashMap
        hashMap.put("Apple", 1);
        hashMap.put("Banana", 2);
        hashMap.put("Orange", 3);

        // 获取指定键的值
        int appleValue = hashMap.get("Apple");
        System.out.println("Apple的值为:" + appleValue);

        // 检查HashMap是否包含指定键
        boolean containsKey = hashMap.containsKey("Banana");
        System.out.println("HashMap是否包含Banana:" + containsKey);

        // 移除指定键的键值对
        hashMap.remove("Orange");

        // 遍历HashMap的键值对
        for (String key : hashMap.keySet()) {
            int value = hashMap.get(key);
            System.out.println("键:" + key + ",值:" + value);
        }

        System.out.println("----------------------");

        // 使用TreeMap
        Map<String, Integer> treeMap = new TreeMap<>();

        // 添加键值对到TreeMap
        treeMap.put("Apple", 1);
        treeMap.put("Banana", 2);
        treeMap.put("Orange", 3);

        // 获取最小的键
        String firstKey = ((TreeMap<String, Integer>) treeMap).firstKey();
        System.out.println("最小的键:" + firstKey);

        // 获取最大的键
        String lastKey = ((TreeMap<String, Integer>) treeMap).lastKey();
        System.out.println("最大的键:" + lastKey);

        // 遍历TreeMap的键值对
        for (String key : treeMap.keySet()) {
            int value = treeMap.get(key);
            System.out.println("键:" + key + ",值:" + value);
        }
    }
}

运行结果:

Apple的值为:1
HashMap是否包含Banana:true
键:Apple,值:1
键:Banana,值:2
----------------------
最小的键:Apple
最大的键:Orange
键:Apple,值:1
键:Banana,值:2
键:Orange,值:3

三.栈(Stack)和队列(Queue):

栈是一种后进先出(LIFO)的数据结构,常用操作有入栈和出栈;队列是一种先进先出(FIFO)的数据结构,常用操作有入队和出队。Java 提供了 Stack 类和 Queue 接口,并有相关实现类如 LinkedList。

  • 栈(Stack):是一种后进先出(LIFO)的数据结构,只允许在栈顶进行插入(入栈)和删除(出栈)操作。相当于把元素放在一个类似于竖起的桶中,每次插入和删除只能在桶的顶部进行。
  • 队列(Queue):是一种先进先出(FIFO)的数据结构,从队尾插入元素(入队),从队头删除元素(出队)。可以理解为排队,先进来的人先出去。

在Java中,可以使用Stack类表示栈,它是Vector的子类。而Queue接口是Java集合框架的一部分,它定义了队列的基本操作,如入队、出队、获取队头元素等。Java提供了多个Queue接口的实现类,其中常用的是LinkedList,它既实现了List接口,又实现了Deque接口,可以作为队列或双端队列使用。

3.1方法

Stack的常用方法包括:

  1. push(element):将元素压入栈顶。
  2. pop():弹出并返回栈顶的元素。
  3. peek():返回栈顶的元素,但不会将其从栈中移除。
  4. isEmpty():判断栈是否为空。
  5. size():返回栈中元素的个数。

Queue的常用方法包括:

  1. add(element):将元素添加到队尾。
  2. offer(element):将元素添加到队尾,并返回是否成功。
  3. remove():移除并返回队头的元素。
  4. poll():移除并返回队头的元素,如果队列为空则返回null。
  5. peek():返回队头的元素,但不会将其从队列中移除。
  6. element():返回队头的元素,如果队列为空则抛出异常。
  7. isEmpty():判断队列是否为空。
  8. size():返回队列中元素的个数。

3.2示例代码

下面一个简单的示例代码,展示了如何使用Stack和Queue进行基本操作:

import java.util.Stack;
import java.util.LinkedList;
import java.util.Queue;

public class myClass {
    public static void main(String[] args) {
        // 使用Stack
        Stack<Integer> stack = new Stack<>();

        // 入栈操作
        stack.push(1);
        stack.push(2);
        stack.push(3);

        // 出栈操作
        int poppedElement = stack.pop();
        System.out.println("出栈元素:" + poppedElement);

        // 获取栈顶元素
        int topElement = stack.peek();
        System.out.println("栈顶元素:" + topElement);

        // 判断栈是否为空
        boolean empty = stack.isEmpty();
        System.out.println("栈是否为空:" + empty);

        System.out.println("----------------------");

        // 使用Queue
        Queue<String> queue = new LinkedList<>();

        // 入队操作
        queue.offer("Apple");
        queue.offer("Banana");
        queue.offer("Orange");

        // 出队操作
        String polledElement = queue.poll();
        System.out.println("出队元素:" + polledElement);

        // 获取队头元素
        String peekedElement = queue.peek();
        System.out.println("队头元素:" + peekedElement);

        // 判断队列是否为空
        boolean emptyQueue = queue.isEmpty();
        System.out.println("队列是否为空:" + emptyQueue);
    }
}

运行结果:

出栈元素:3
栈顶元素:2
栈是否为空:false
----------------------
出队元素:Apple
队头元素:Banana
队列是否为空:false

四.树(Tree):

树是一种非线性的数据结构,由节点和边组成,用于表示具有层级关系的数据结构。常见的树结构包括二叉树、平衡树、红黑树等。Java 提供了 TreeSet 和 TreeMap 来实现树结构。

4.1  二叉树(Binary Tree):

是一种特殊的树结构,每个节点最多有两个子节点:左子节点和右子节点。一个节点可以没有子节点,也可以只有一个子节点。

4.2二叉搜索树(Binary Search Tree):

也称为二叉查找树或排序二叉树,是一种特殊的二叉树。它具有以下性质:

  1. 对于任意节点,其左子树上的所有节点的值都小于该节点的值。
  2. 对于任意节点,其右子树上的所有节点的值都大于该节点的值。
  3. 左子树和右子树都必须是二叉搜索树。

由于二叉搜索树的性质,我们可以利用它来高效地进行查找、插入和删除操作。对于任意节点,其左子树的节点值都小于该节点,因此在查找、插入或删除时,可以通过比较节点的值,有选择性地在左子树或右子树中进行操作,从而提高效率。

Java中可以使用TreeSet和TreeMap来实现二叉搜索树。它们基于红黑树(Red-Black Tree)实现,红黑树是一种自平衡的二叉搜索树,保持了良好的平衡性能。

  1. TreeSet是一个基于红黑树实现的有序集合,它存储的元素按照自然顺序或者指定的比较器进行排序,并且不允许出现重复元素。
  2. TreeMap是一个基于红黑树实现的有序映射,它存储键值对,并按照键的自然顺序或者指定的比较器进行排序。与TreeSet类似,TreeMap也不允许出现重复的键。

通过使用TreeSet和TreeMap,我们可以方便地操作二叉搜索树的相关操作,如插入、删除、查找等,并保持元素的有序性。

4.3  操作方法

  1. 创建树IntTree(&T):创建1个空树T。
  2. 销毁树DestroyTree(&T)
  3. 构造树CreatTree(&T,deinition)
  4. 置空树ClearTree(&T):将树T置为空树。
  5. 判空树TreeEmpty(T)
  6. 求树的深度TreeDepth(T)
  7. 获得树根Root(T)
  8. 获取结点Value(T,cur_e,&e):将树中结点cur_e存入e单元中。
  9. 数据赋值Assign(T,cur_e,value):将结点value,赋值于树T的结点cur_e中。
  10. 获得双亲Parent(T,cur_e):返回树T中结点cur_e的双亲结点。
  11. 获得最左孩子LeftChild(T,cur_e):返回树T中结点cur_e的最左孩子。
  12. 获得右兄弟RightSibling(T,cur_e):返回树T中结点cur_e的右兄弟。
  13. 插入子树InsertChild(&T,&p,i,c):将树c插入到树T中p指向结点的第i个子树之前。
  14. 删除子树DeleteChild(&T,&p,i):删除树T中p指向结点的第i个子树。
  15. 遍历树TraverseTree(T,visit())

4.4  树的遍历

4.4.1树的遍历包括两种主要方式:

  1. 深度优先遍历(DFS):

    1. 先序遍历(Preorder):根节点 -> 左子树 -> 右子树
    2. 中序遍历(Inorder):左子树 -> 根节点 -> 右子树
    3. 后序遍历(Postorder):左子树 -> 右子树 -> 根节点
  2. 广度优先遍历(BFS): 从根节点开始,按层级顺序逐层遍历树的节点,从左到右依次访问每个节点。

无论是深度优先遍历还是广度优先遍历,都有各自的应用场景。可以根据具体需求选择适合的遍历方式来处理树中的节点。

4.4.2  树的两种基本遍历方式:

  • 先序遍历(Preorder traversal):
    1. 访问根节点。
    2. 递归地对左子树进行先序遍历。
    3. 递归地对右子树进行先序遍历。

先序遍历的顺序是先访问根节点,然后按照从左到右的顺序依次访问左子树和右子树。

  • 中序遍历(Inorder traversal):
    1. 递归地对左子树进行中序遍历。
    2. 访问根节点。
    3. 递归地对右子树进行中序遍历。

中序遍历的顺序是先按照从左到右的顺序递归访问左子树,然后访问根节点,最后按照从左到右的顺序递归访问右子树。

这两种遍历方法都是通过递归实现的,可以用来遍历二叉树或其他类型的树结构。它们在不同的情况下有各自的应用,具体取决于问题的需求。

4.5  示例代码

下面一个简单的示例代码,展示了如何使用Binary Tree和Binary Search Tree进行基本操作:

// 定义二叉树节点类
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

// 二叉树类
class BinaryTree {
    TreeNode root;

    public BinaryTree() {
        root = null;
    }

    // 插入节点
    public void insert(int val) {
        root = insertNode(root, val);
    }

    private TreeNode insertNode(TreeNode node, int val) {
        if (node == null) {
            return new TreeNode(val);
        }

        // 如果值小于当前节点,则插入左子树
        if (val < node.val) {
            node.left = insertNode(node.left, val);
        }
        // 如果值大于等于当前节点,则插入右子树
        else {
            node.right = insertNode(node.right, val);
        }

        return node;
    }

    // 先序遍历
    public void preOrderTraversal() {
        preOrder(root);
    }

    private void preOrder(TreeNode node) {
        if (node == null) {
            return;
        }

        System.out.print(node.val + " ");
        preOrder(node.left);
        preOrder(node.right);
    }
}

// 二叉搜索树类
class BinarySearchTree {
    TreeNode root;

    public BinarySearchTree() {
        root = null;
    }

    // 插入节点
    public void insert(int val) {
        root = insertNode(root, val);
    }

    private TreeNode insertNode(TreeNode node, int val) {
        if (node == null) {
            return new TreeNode(val);
        }

        // 如果值小于当前节点,则插入左子树
        if (val < node.val) {
            node.left = insertNode(node.left, val);
        }
        // 如果值大于等于当前节点,则插入右子树
        else {
            node.right = insertNode(node.right, val);
        }

        return node;
    }

    // 中序遍历
    public void inOrderTraversal() {
        inOrder(root);
    }

    private void inOrder(TreeNode node) {
        if (node == null) {
            return;
        }

        inOrder(node.left);
        System.out.print(node.val + " ");
        inOrder(node.right);
    }
}

// 测试代码
public class myClass {
    public static void main(String[] args) {
        // 创建二叉树,并插入节点
        BinaryTree binaryTree = new BinaryTree();
        binaryTree.insert(5);
        binaryTree.insert(3);
        binaryTree.insert(7);
        binaryTree.insert(2);
        binaryTree.insert(4);
        binaryTree.insert(6);
        binaryTree.insert(8);

        // 先序遍历二叉树
        System.out.print("二叉树 -先序遍历: ");
        binaryTree.preOrderTraversal();
        System.out.println();

        // 创建二叉搜索树,并插入节点
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        binarySearchTree.insert(5);
        binarySearchTree.insert(3);
        binarySearchTree.insert(7);
        binarySearchTree.insert(2);
        binarySearchTree.insert(4);
        binarySearchTree.insert(6);
        binarySearchTree.insert(8);

        // 中序遍历二叉搜索树
        System.out.print("二叉搜索树 - 中序遍历: ");
        binarySearchTree.inOrderTraversal();
        System.out.println();
    }
}

运行结果:

二叉树 -先序遍历: 5 3 2 4 7 6 8 
二叉搜索树 - 中序遍历: 2 3 4 5 6 7 8 

五.图(Graph):

图(Graph)是由节点(Vertex)和边(Edge)组成的一种非线性数据结构,用于表示对象之间的关联关系。可以将节点视为图中的元素,并且节点可以与其他节点通过边相连接。

在实际应用中,图可用于解决各种问题,如社交网络分析、路径搜索、最短路径算法等。在 Java 中,可以自行实现图的数据结构和相关算法,或使用第三方库(如JGraphT、Java Universal Network/Graph Framework等)来操作和处理图结构。

  • 有向图(Directed Graph):也称为有向图、定向图或有向网络。有向图中的边具有方向性,表示节点之间的单向关系。如果节点 A 到节点 B 之间存在一条有向边,那么从节点 A 出发可以到达节点 B,但反过来不行。
  • 无向图(Undirected Graph):也称为无向图、非定向图或无向网络。无向图中的边没有方向,表示节点之间的双向关系。如果节点 A 和节点 B 之间有一条边相连,则可以从节点 A 到节点 B 或者从节点 B 到节点 A。

六.堆(Heap):

堆是一种特殊的树形数据结构,满足堆属性。用于有效地找到最大值或最小值的数据结构。Java 提供了优先级队列(PriorityQueue)来实现堆。

  • 最大堆(Max Heap):每个父节点的值都大于或等于其子节点的值。
  • 最小堆(Min Heap):每个父节点的值都小于或等于其子节点的值。

七.链表(LinkedList):

链表是一种线性数据结构,也叫动态数据结构,但是并不会按线性的顺序存储数据,由节点和指针组成,每个节点包含数据和指向下一个节点的指针。

链表可分为单向链表和双向链表。

一个单向链表包含两个值: 当前节点的值和一个指向下一个节点的链接。

一个双向链表有三个整数值: 数值、向后的节点链接、向前的节点链接。

八.MAP

Map是一种用于存储键值对的接口。它提供了一种将键映射到值的方式,可以通过键快速查找对应的值。在Map中,键是唯一的,每个键最多只能映射到一个值。常见的Map实现类包括HashMap、TreeMap、LinkedHashMap等。这些实现类提供了不同的性能特点和迭代顺序,可以根据具体需求选择适合的实现类。使用Map可以方便地进行数据检索、插入、删除和更新操作,非常适合处理需要快速查找的场景。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/78250.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【TA 挖坑02】RayMarching SDF 物体黏合

写在前面 由于实习和忙着论文很久没经营博客了&#xff0c;最近以各种方式收集到了一些想实现的效果&#xff0c;其中一个就是卡通云融合、变大变小、聚散收拢的效果如何实现的问题&#xff0c;这就不得不提搁置了很久的RayMarching... 挖坑&#xff01;整理一下有帮助的文章…

Octree八叉树python

原理 简单示例&#xff1a; 假设我们有以下一组三维点云数据&#xff1a; points [[0.1, 0.1, 0.1],[0.4, 0.1, 0.1],[0.1, 0.4, 0.1],[0.4, 0.4, 0.1],[0.1, 0.1, 0.4],[0.4, 0.1, 0.4],[0.1, 0.4, 0.4],[0.4, 0.4, 0.4], ] 我们可以使用八叉树将这些点云数据存储在三维空…

MATLAB高分辨率图片

把背景调黑&#xff0c;把曲线调黄&#xff0c;把grid调白&#xff0c;调调字体字号的操作 close all a0:0.1:10; noise2*rand(1,length(a)); bsin(a)sin(3*a)noise;plot(a,b,y,linewidth,2); ylim([-3 4]) %y轴范围 set(gca,xgrid,on,ygrid,on,gridlinestyle,-,Grid…

8.13黄金是否进入下行通道?下周开盘如何布局

近期有哪些消息面影响黄金走势&#xff1f;黄金多空该如何研判&#xff1f; ​黄金消息面解析&#xff1a;周五(8月11日)现货黄金小幅收低&#xff0c;受累于美元走强和美国国债收益率上升&#xff0c;本周录得6月底以来最差单周表现。投资者在评估最新一批通胀报告和消费者信…

【hive】简单介绍hive的几种join

文章目录 前言1. Common Join2. Map Join介绍&#xff1a;使用方法&#xff1a;限制&#xff1a; 3. Bucket Map Join介绍&#xff1a;好处&#xff1a;使用条件&#xff1a;使用方法&#xff1a; 4. Sort Merge Bucket Map Join介绍&#xff1a;如何使用&#xff1a; 5. Skew …

使用 HTML、CSS 和 JavaScript 创建多步骤表单

使用 HTML、CSS 和 JavaScript 创建多步骤表单 为了处理又长又复杂的表单&#xff0c;我们需要将它们分成多个步骤。通过一次只在屏幕上显示一些输入&#xff0c;表单会感觉更容易理解&#xff0c;并防止用户感到被大量的表单字段淹没。 在本文中&#xff0c;我将逐步指导如何…

OSI七层模型及TCP/IP四层模型

目录 OSI七层模型 TCP/IP四层模型 OIS七层模型和TCP/IP模型图 七层详解 两种模型比较 为什么OSI七层体系结构不常用 四层详解 网络为什么要分层&#xff1f; 说说 OSI 七层模型和 TCP/IP 四层模型的关系和区别 OSI七层模型 OSI&#xff08;Open System Interconnect&a…

编译redis-5.0.9报错zmalloc.h:50:31: 致命错误:jemalloc/jemalloc.h:没有那个文件或目录问题解决

上图 解决&#xff1a; make && make install MALLOClibc原因: 原因是jemalloc重载了Linux下的ANSI C的malloc和free函数。

【Spring Boot】构建RESTful服务 — 实战:实现Web API版本控制

实战&#xff1a;实现Web API版本控制 前面介绍了Spring Boot如何构建RESTful风格的Web应用接口以及使用Swagger生成API的接口文档。如果业务需求变更&#xff0c;Web API功能发生变化时应该如何处理呢&#xff1f;可以通过Web API的版本控制来处理。 1.为什么进行版本控制 …

JVM中对象和GC Root之间的四种引用关系

1. 强引用 只有所有 GC Roots 对象都不通过【强引用】引用该对象&#xff0c;该对象才能被垃圾回收 由GC Root直接new出来的对象是强引用&#xff0c;只有当GC Root不再引用该对象的时候&#xff0c;才会被回收 例子&#xff1a; List<String> list new ArrayList<&…

【STM32】FreeRTOS事件组学习

事件组&#xff08;Event Group&#xff09; 一个任务执行之前需要经过多个条件进行判断&#xff0c;当条件全部满足或多个条件中的某一个条件满足才执行。 实验&#xff1a;创建两个任务&#xff0c;一个事件组&#xff0c;当按键一二三都按过一遍才打印。 实现&#xff1a…

STM32 CubeMX (Freertos任务通信:队列、信号量、互斥量,事件组,任务通知)第二步

STM32 CubeMX STM32 CubeMX ____Freertos任务通信&#xff1a;队列、信号量、互斥量&#xff0c;事件组&#xff0c;任务通知 STM32 CubeMX一、STM32 CubeMX设置时钟配置HAL时基选择TIM1&#xff08;不要选择滴答定时器&#xff1b;滴答定时器留给OS系统做时基&#xff09;使用…

【STM32+ESP8266上云连载①】给ESP8266烧录AT固件

文章目录 一、给NodeMCU烧录固件1.1硬件准备1.2软件准备1.3AT固件下载1.4配置设置1.5开始烧录 二、给ESP8266-01S烧录固件2.1硬件准备2.2AT固件下载2.3连线2.4烧录配置 三、给ESP-12E/F/S单片烧录固件四、指令测试4.1HTTP测试4.2MQTT测试 我在使用ESP8266的时候遇到了一些问题&…

智能仓储管理系统(自动化仓库管理解决方案)

企业实际的仓储管理中&#xff0c;往往会出现那样这样的错误&#xff0c;归根结底&#xff0c;主要是由于没使用合适的仓库管理工具。相反&#xff0c;人工使用合适的仓库管理工具&#xff0c;不仅可以在日常仓库管理方法中根据采集到的产品信息数据&#xff0c;大大地提高管理…

vue3学习笔记(一)

一、API风格 Vue 的组件可以按两种不同的风格书写&#xff1a;选项式 API 和组合式 API。 二、组合式API 1.&#xff08;组合式 API 的核心思想是直接在函数作用域内定义响应式状态变量&#xff0c;并将从多个函数中得到的状态组合起来处理复杂问题。这种形式更加自由&#x…

vue项目根据word模版导出word文件

一、安装依赖 //1、docxtemplaternpm install docxtemplater pizzip -S//2、jszip-utilsnpm install jszip-utils -S//3、pizzipnpm install pizzip -S//4、FileSaver npm install file-saver --save二、创建word模版 也就是编辑一个word文档&#xff0c;文档中需要动态取值的…

用 React+ts 实现无缝滚动的走马灯

一、走马灯的作用 走马灯是一种常见的网页交互组件&#xff0c;可以展示多张图片或者内容&#xff0c;通过自动播放或者手动切换的方式&#xff0c;让用户能够方便地浏览多张图片或者内容。 本次实现的不是轮播图而是像传送带一样的无限滚动的形式。 二、需求梳理 走马灯可设…

大数据培训前景怎么样?企业需求量大吗

大数据行业对大家来说并不陌生&#xff0c;大数据行业市场人才需求量大&#xff0c;越早入行越有优势&#xff0c;发展机会和上升空间等大。不少人通过大数据培训来提升自己的经验和自身技术能力&#xff0c;以此来获得更好的就业机会。 2023大数据培训就业前景怎么样呢?企业需…

034_小驰私房菜_[问题复盘] Qcom平台,某些三方相机拍照旋转90度

全网最具价值的Android Camera开发学习系列资料~ 作者:8年Android Camera开发,从Camera app一直做到Hal和驱动~ 欢迎订阅,相信能扩展你的知识面,提升个人能力~ 【一、问题】 某些三方相机,预览正常,拍照旋转90度 【二、问题排查】 1 ) HAL这边Jpeg编码数据在哪个地方…

Baumer工业相机堡盟工业相机如何通过BGAPI SDK设置相机的固定帧率(C++)

Baumer工业相机堡盟工业相机如何通过BGAPI SDK设置相机的固定帧率&#xff08;C&#xff09; Baumer工业相机Baumer工业相机的固定帧率功能的技术背景CameraExplorer如何查看相机固定帧率功能在BGAPI SDK里通过函数设置相机固定帧率 Baumer工业相机通过BGAPI SDK设置相机固定帧…