Java中常见的数据结构及相关函数的使用方法
Java中常见的数据结构有数组、链表、栈、队列、堆、树、图等等。下面简要介绍这些数据结构及相关函数的使用方法。
1. 数组（Array）
数组是一种最基本的数据结构，它是由相同类型的元素组成，使用下标进行访问和操作。Java语言中，数组的声明和初始化如下：
int[] arr = new int[10]; // 创建一个长度为10的int类型数组
int[] brr = {1, 2, 3, 4}; // 直接初始化一个长度为4的int类型数组
数组的一些常用操作：
// 遍历数组
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
// 计算数组元素之和
int sum = 0;
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
}
// 查找指定元素的下标
int index = -1;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
index = i;
break;
}
}
2. 链表（Linked List）
链表是由节点组成的线性结构，每个节点包含一个数据元素和指向下一个节点的指针。Java中提供了链表的实现类LinkedList，它支持队列、栈和双向链表等操作。链表的一些常用操作：
// 创建链表
LinkedList<Integer> list = new LinkedList<Integer>();
// 添加元素
list.add(1);
list.addLast(2);
list.addFirst(3);
// 获取元素
int first = list.getFirst();
int last = list.getLast();
int index = list.indexOf(2);
// 删除元素
list.remove(1);
list.removeFirst();
list.removeLast();
// 插入元素
list.add(1, 4);
3. 栈（Stack）
栈是一种后进先出（LIFO）的数据结构，它只允许在一端进行插入和删除操作。Java中提供了栈的实现类Stack，它支持压栈、出栈、查看栈顶元素等操作。
// 创建栈
Stack<Integer> stack = new Stack<>();
// 入栈
stack.push(1);
stack.push(2);
stack.push(3);
// 出栈
int top = stack.pop();
int peek = stack.peek(); // 查看栈顶元素
// 判断栈是否为空
boolean empty = stack.empty();
4. 队列（Queue）
队列是一种先进先出（FIFO）的数据结构，它支持在队尾插入元素，在队头删除元素。Java中提供了队列的实现类LinkedList，它支持添加、删除、查看队头队尾元素等操作。
// 创建队列
LinkedList<Integer> queue = new LinkedList<>();
// 入队
queue.offer(1);
queue.offer(2);
queue.offer(3);
// 出队
int poll = queue.poll();
int peek = queue.peek(); // 查看队头元素
// 判断队列是否为空
boolean empty = queue.isEmpty();
5. 堆（Heap）
堆是一种特殊的树形数据结构，父节点的值总是大于（或小于）其子节点的值。Java中提供了堆的实现类PriorityQueue，它支持插入、删除、查看堆顶元素等操作。
// 创建最大堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
// 创建最小堆
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// 插入元素
maxHeap.offer(1);
maxHeap.offer(2);
maxHeap.offer(3);
// 删除堆顶元素
int max = maxHeap.poll();
int min = minHeap.poll();
// 查看堆顶元素
int peek = maxHeap.peek();
6. 树（Tree）
树是一种非线性数据结构，它由一组节点构成，节点之间存在一定的关系，形成了层次结构。Java中常见的树结构有二叉树、红黑树、AVL树等。树的一些常用操作有遍历、搜索、增删改查等。
// 创建二叉树
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public TreeNode createTree() {
// 创建一颗如下的二叉树
// 1
// / \
// 2 3
// / \
// 4 5
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
return root;
}
// 前序遍历
public void preOrder(TreeNode root) {
if (root == null) return;
System.out.print(root.val + " ");
preOrder(root.left);
preOrder(root.right);
}
// 中序遍历
public void inOrder(TreeNode root) {
if (root == null) return;
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}
// 后序遍历
public void postOrder(TreeNode root) {
if (root == null) return;
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val + " ");
}
// 层次遍历
public void levelOrder(TreeNode root) {
if (root == null) return;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
System.out.print(node.val + " ");
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
}
7. 图（Graph）
图是一种非线性数据结构，由一组节点和一组边组成，节点之间和边之间存在一定的关系。Java中常见的图结构有有向图、无向图、加权图等。图的一些常用操作有遍历、搜索、增删改查等。
// 创建无向图
class Graph {
private int V; // 图中节点的个数
private ArrayList<Integer>[] adj; // 邻接表表示图
public Graph(int v) {
this.V = v;
adj = new ArrayList[v];
for (int i = 0; i < v; i++) {
adj[i] = new ArrayList<>();
}
}
// 添加边
public void addEdge(int u, int v) {
adj[u].add(v);
adj[v].add(u);
}
}
// DFS遍历
public void dfs(int s, boolean[] visited) {
visited[s] = true;
System.out.print(s + " ");
for (int v : adj[s]) {
if (!visited[v]) {
dfs(v, visited);
}
}
}
// BFS遍历
public void bfs(int s, boolean[] visited) {
Queue<Integer> queue = new LinkedList<>();
visited[s] = true;
queue.offer(s);
while (!queue.isEmpty()) {
int u = queue.poll();
System.out.print(u + " ");
for (int v : adj[u]) {
if (!visited[v]) {
visited[v] = true;
queue.offer(v);
}
}
}
}
以上是Java中常见的数据结构及相关函数的使用方法，各个数据结构在实际应用中都有广泛的应用。学好数据结构和算法是成为一名优秀的程序员的必要条件之一。