Java常见基础数据结构

Java常见基础数据结构攻略

Java是一种面向对象的编程语言，拥有丰富的数据结构，大多数基础数据结构都包含在Java API中。在本文中，我们将讨论Java中常见的基础数据结构，包括数组、链表、栈、队列、集合和映射。我们将探讨每种数据结构的定义、用法和基本操作，并提供两个示例说明。

数组

数组是Java中最基本的数据结构之一。它是一个有序的集合，可以包含任何类型的元素。在使用数组之前，必须先定义它的大小。以下是声明和初始化一个整数类型数组的语法：

int[] arr = new int[10];

下面以求和为例，介绍数组的基本操作。

访问数组元素

数组中的每个元素都有一个唯一的索引或位置，可以使用数组名称和元素的索引来访问。Java中的数组索引从0开始，因此第一个元素的索引为0。以下是一个例子：

int[] arr = {1, 2, 3, 4, 5};
int sum = arr[0] + arr[1] + arr[2] + arr[3] + arr[4];
System.out.println(sum); // 输出15

更改数组元素

可以使用数组名称和元素的索引来更改数组中的元素。以下是一个例子：

int[] arr = {1, 2, 3, 4, 5};
arr[2] = 6;
System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 6, 4, 5]

数组长度

可以使用数组的length属性获取数组的长度。以下是一个例子：

int[] arr = {1, 2, 3, 4, 5};
System.out.println(arr.length); // 输出 5

链表

链表是由一系列节点组成的。每个节点包含一个元素和一个指向下一个节点的引用。最后一个节点通常包含一个空引用。以下是一个定义节点的Java类：

class Node<T> {
    T data;
    Node<T> next;

    public Node(T data) {
        this.data = data;
    }
}

下面以遍历链表为例，介绍链表的基本操作。

遍历链表

遍历链表是指访问链表中的所有节点。可以使用循环遍历每个节点，直到到达链表的末尾。以下是一个例子：

Node<String> head = new Node<>("A");
head.next = new Node<>("B");
head.next.next = new Node<>("C");

Node<String> current = head;
while (current != null) {
    System.out.print(current.data + " ");
    current = current.next;
}
// 输出A B C

插入节点

可以在链表的任何位置插入一个新节点。插入节点之前，必须找到插入位置的前一个节点。以下是一个插入节点的例子：

Node<String> head = new Node<>("A");
head.next = new Node<>("B");
head.next.next = new Node<>("C");

Node<String> newNode = new Node<>("D");
newNode.next = head.next;
head.next = newNode;

Node<String> current = head;
while (current != null) {
    System.out.print(current.data + " ");
    current = current.next;
}
// 输出 A D B C

栈

栈是一种后进先出（LIFO）的数据结构。栈有两个基本操作：推入元素和弹出元素。以下是一个定义栈的Java类：

class Stack<T> {
    private List<T> list = new ArrayList<>();

    public void push(T item) {
        list.add(item);
    }

    public T pop() {
        if (list.isEmpty()) {
            throw new RuntimeException("Stack is Empty!");
        }
        return list.remove(list.size() - 1);
    }

    public boolean isEmpty() {
        return list.isEmpty();
    }

    public int size() {
        return list.size();
    }
}

下面以十进制转二进制为例，介绍栈的基本操作。

推入元素

可以使用push方法将元素推入栈中。以下是一个十进制转二进制的例子：

int decimal = 10;
Stack<Integer> stack = new Stack<>();

while (decimal > 0) {
    int remainder = decimal % 2;
    stack.push(remainder);
    decimal /= 2;
}

while (!stack.isEmpty()) {
    System.out.print(stack.pop());
}
// 输出 1010

弹出元素

可以使用pop方法将栈顶元素弹出栈。以下是一个计算基本表达式的例子：

String expression = "2 + 3 * 4";
Stack<Integer> stack = new Stack<>();

for (String token : expression.split(" ")) {
    if (token.equals("+")) {
        int b = stack.pop();
        int a = stack.pop();
        stack.push(a + b);
    } else if (token.equals("*")) {
        int b = stack.pop();
        int a = stack.pop();
        stack.push(a * b);
    } else {
        stack.push(Integer.parseInt(token));
    }
}

System.out.println(stack.pop()); // 输出 14

队列

队列是一种先进先出（FIFO）的数据结构。队列有两个基本操作：入队和出队。以下是一个定义队列的Java类：

class Queue<T> {
    private List<T> list = new ArrayList<>();

    public void enqueue(T item) {
        list.add(item);
    }

    public T dequeue() {
        if (list.isEmpty()) {
            throw new RuntimeException("Queue is Empty!");
        }
        return list.remove(0);
    }

    public boolean isEmpty() {
        return list.isEmpty();
    }

    public int size() {
        return list.size();
    }
}

下面以BFS为例，介绍队列的基本操作。

入队元素

可以使用enqueue方法将元素入队。以下是一个BFS（广度优先搜索）的例子：

class Node {
    List<Node> neighbors = new ArrayList<>();
    String label;

    public Node(String label) {
        this.label = label;
    }
}

Node graph = new Node("A");
graph.neighbors.add(new Node("B"));
graph.neighbors.add(new Node("C"));
graph.neighbors.get(0).neighbors.add(new Node("D"));
graph.neighbors.get(0).neighbors.add(new Node("E"));

Queue<Node> queue = new Queue<>();
Set<Node> visited = new HashSet<>();

queue.enqueue(graph);
visited.add(graph);

while (!queue.isEmpty()) {
    Node current = queue.dequeue();
    System.out.print(current.label + " ");

    for (Node neighbor : current.neighbors) {
        if (!visited.contains(neighbor)) {
            queue.enqueue(neighbor);
            visited.add(neighbor);
        }
    }
}
// 输出 A B C D E

出队元素

可以使用dequeue方法将队头元素出队。以下是一个打印队列中的所有元素的例子：

Queue<String> queue = new Queue<>();
queue.enqueue("A");
queue.enqueue("B");
queue.enqueue("C");

while (!queue.isEmpty()) {
    System.out.print(queue.dequeue() + " ");
}
// 输出 A B C

集合

集合是一种不包含重复元素的数据结构。Java API提供了Set接口，可以用来实现集合。以下是一个使用Set的例子：

Set<String> set = new HashSet<>();
set.add("A");
set.add("B");
set.add("C");
set.add("B"); // 重复元素

System.out.println(set); // 输出[A, B, C]

可以使用Stream API来操作集合。以下是一个过滤集合中的奇数元素并求和的例子：

Set<Integer> set = new HashSet<>(Arrays.asList(1, 2, 3, 4, 5));
int sum = set.stream()
    .filter(n -> n % 2 == 0)
    .mapToInt(Integer::intValue)
    .sum();

System.out.println(sum); // 输出6

映射

映射是一种将键和值进行映射的数据结构。Java API提供了Map接口，可以用来实现映射。以下是一个使用Map的例子：

Map<String, Integer> map = new HashMap<>();
map.put("A", 1);
map.put("B", 2);
map.put("C", 3);

System.out.println(map.get("B")); // 输出 2

可以使用Stream API来操作键或值的集合。以下是一个过滤映射中的奇数值并求和的例子：

Map<String, Integer> map = new HashMap<>();
map.put("A", 1);
map.put("B", 2);
map.put("C", 3);

int sum = map.values().stream()
    .filter(n -> n % 2 == 0)
    .mapToInt(Integer::intValue)
    .sum();

System.out.println(sum); // 输出2

总结

在Java中，有很多种不同的数据结构可供选择。本文介绍了Java中的常见基础数据结构，包括数组、链表、栈、队列、集合和映射。掌握这些数据结构可以让我们在编写Java程序时更加高效和灵活。