数据结构在不同领域的应用场景解析

2. 栈与队列

核心概念

• 栈：遵循后进先出（LIFO）原则，适合处理嵌套结构或回溯场景。
• 队列：遵循先进先出（FIFO）原则，常用于任务排队或缓冲处理。

应用场景

• 编译器设计：表达式求值、函数调用栈等逻辑常用栈来实现。
• 操作系统：任务调度、消息传递等场景中广泛使用队列。

代码实现 Java 标准库提供了现成的实现，这里展示基本的入栈出栈和入队出队操作：

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(10);
        stack.push(20);
        stack.push(30);
        System.out.println("Stack: " + stack);
        System.out.println("Popped: " + stack.pop());
        System.out.println("After popping: " + stack);
    }
}

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

public class QueueExample {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(10);
        queue.add(20);
        queue.add(30);
        System.out.println("Queue: " + queue);
        System.out.println("Removed: " + queue.remove());
        System.out.println("After removing: " + queue);
    }
}

3. 堆

核心概念 堆是一种特殊的完全二叉树，分为最大堆和最小堆。父节点与子节点的大小关系决定了堆的类型，常用于维护优先级。

应用场景

• 优先级队列：任务调度、事件处理等需要按优先级排序的应用。
• 堆排序：基于堆的高效排序算法，时间复杂度稳定在 O(n log n)。

代码实现 利用 Java 的 PriorityQueue 可以轻松构建最小堆：

import java.util.PriorityQueue;

public class MinHeapExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        minHeap.add(10);
        minHeap.add(20);
        minHeap.add(15);
        minHeap.add(5);
        System.out.println("Min Heap: " + minHeap);
        System.out.println("Removed: " + minHeap.poll());
        System.out.println("After removing: " + minHeap);
    }
}

4. 图

核心概念 图由顶点（节点）和边组成，是非线性数据结构。边可以是有向或无向的，也可以带有权重，用于表示复杂的关系网络。

应用场景

• 社交网络分析：用户之间的关系可以用图来表示。
• 路由算法：如 Dijkstra 算法和 A*算法，用于寻找最短路径。
• 推荐系统：基于用户行为构建图模型，进行个性化推荐。

代码实现 以下是无向图的邻接矩阵表示及 Dijkstra 最短路径算法的核心逻辑：

public class Graph {
    private final int V; // 顶点数量
    private int[][] adjMatrix; // 邻接矩阵

    public Graph(int v) {
        V = v;
        adjMatrix = new int[V][V];
    }

    public void addEdge(int v, int w) {
        adjMatrix[v][w] = 1;
        adjMatrix[w][v] = 1; // 无向图
    }

    public void printGraph() {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                System.out.print(adjMatrix[i][j] + " ");
            }
            System.out.println();
        }
    }
}

import java.util.Arrays;
import java.util.PriorityQueue;

public class DijkstraAlgorithm {
    private static final int INF = Integer.MAX_VALUE;

    public static int[] dijkstra(int[][] graph, int src) {
        int V = graph.length;
        int[] dist = new int[V];
        Arrays.fill(dist, INF);
        dist[src] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        pq.offer(new int[]{src, 0});

        while (!pq.isEmpty()) {
            int[] u = pq.poll();
            int uNode = u[0], uDist = u[1];
            if (uDist > dist[uNode]) continue;
            for (int v = 0; v < V; v++) {
                if (graph[uNode][v] != 0) { // 有边
                    int newDist = uDist + graph[uNode][v];
                    if (newDist < dist[v]) {
                        dist[v] = newDist;
                        pq.offer(new int[]{v, newDist});
                    }
                }
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        int[][] graph = {
            {0, 4, 0, 0, 0, 0, 0, 8, 0},
            {4, 0, 8, 0, 0, 0, 0, 11, 0},
            {0, 8, 0, 7, 0, 4, 0, 0, 2},
            {0, 0, 7, 0, 9, 14, 0, 0, 0},
            {0, 0, 0, 9, 0, 10, 0, 0, 0},
            {0, 0, 4, 14, 10, 0, 2, 0, 0},
            {0, 0, 0, 0, 0, 2, 0, 1, 6},
            {8, 11, 0, 0, 0, 0, 1, 0, 7},
            {0, 0, 2, 0, 0, 0, 6, 7, 0}
        };
        int[] distances = dijkstra(graph, 0);
        System.out.println("Shortest distances from source 0: " + Arrays.toString(distances));
    }
}

5. Trie 树

核心概念 Trie 树（前缀树）专门用于存储字符串集合，特别适合快速查找和插入操作，在处理大量文本数据时表现优异。

应用场景

• 搜索引擎：利用 Trie 树进行关键词索引，加速搜索过程。
• 词频统计：在文本处理中快速统计单词出现频率。
• 自动补全：输入法中的候选词推荐功能。

代码实现 Trie 树的节点通常包含子节点数组和一个标记位，指示是否构成完整单词：

class TrieNode {
    private final int ALPHABET_SIZE = 26;
    TrieNode[] children = new TrieNode[ALPHABET_SIZE];
    boolean isEndOfWord;

    public TrieNode() {
        isEndOfWord = false;
        for (int i = 0; i < ALPHABET_SIZE; i++) {
            children[i] = null;
        }
    }
}

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String key) {
        TrieNode pCrawl = root;
        for (int level = 0; level < key.length(); level++) {
            int index = key.charAt(level) - 'a';
            if (pCrawl.children[index] == null)
                pCrawl.children[index] = new TrieNode();
            pCrawl = pCrawl.children[index];
        }
        pCrawl.isEndOfWord = true;
    }

    public boolean search(String key) {
        TrieNode pCrawl = root;
        for (int level = 0; level < key.length(); level++) {
            int index = key.charAt(level) - 'a';
            if (pCrawl.children[index] == null)
                return false;
            pCrawl = pCrawl.children[index];
        }
        return (pCrawl != null && pCrawl.isEndOfWord);
    }

    public void delete(TrieNode root, String key, int depth) {
        if (root == null) return;
        if (depth == key.length()) {
            if (root.isEndOfWord) root.isEndOfWord = false;
            if (isEmpty(root)) root = null;
            return;
        }
        int index = key.charAt(depth) - 'a';
        delete(root.children[index], key, depth + 1);
        if (isEmpty(root) && !root.isEndOfWord) {
            root = null;
        }
    }

    private boolean isEmpty(TrieNode node) {
        for (int i = 0; i < 26; i++) {
            if (node.children[i] != null) return false;
        }
        return true;
    }
}

6. 并查集

核心概念 并查集用于管理不相交集合，支持合并两个集合以及查询两个元素是否属于同一个集合的操作，通常配合路径压缩和按秩合并优化性能。

应用场景

• 社交网络：确定用户之间的关系网。
• 图像分割：基于像素相似性对图像进行区域划分。
• 最小生成树算法：如 Kruskal 算法，在构建过程中使用并查集避免形成环。

代码实现 这是并查集的标准实现，重点在于 find 方法的路径压缩和 union 方法的按秩合并：

public class UnionFind {
    private int[] parent;
    private int[] rank;

    public UnionFind(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }

    public boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }
}

数组与链表为基本的数据存储提供了基础支持，而栈与队列为特定的操作模式提供了高效的解决方案。堆则在优先级队列和排序算法中发挥着重要作用，图结构则广泛应用于复杂的关系建模。Trie 树和并查集作为高级数据结构，在处理特定问题时提供了更优的性能。