数据结构

需求	适合的数据结构	Java 实现方式	特点
后进先出	栈（Stack）	`Deque<T> stack = new ArrayDeque<>();`	操作快，比`Stack`类更推荐
先进先出	队列（Queue）	`Queue<T> queue = new LinkedList<>();` 或 `ArrayDeque<>();`	`LinkedList`双端、`ArrayDeque`快
双端操作	双端队列（Deque）	`Deque<T> deque = new ArrayDeque<>();`	可做单调队列、滑动窗口
快速查找	哈希表	`HashMap<K,V>`，`HashSet<E>`	常用于计数、查重
有序集合	TreeSet / TreeMap	`TreeSet<>`，`TreeMap<>`	基于红黑树，自动排序
区间操作	树状数组 / 线段树	自己实现类	用于区间求和、区间最值等
优先处理	堆（优先队列）	`PriorityQueue<T>`	默认小顶堆，可自定义比较器
图	邻接表 / 邻接矩阵	用 `List<List<Integer>>` 或 `int[][]`	视题目需求选择稀疏或稠密
树结构	树节点类 + DFS/BFS	自定义 `TreeNode` 结构	常结合递归和栈使用

优先队列

**原理:**基于堆结构实现（大根堆或小根堆），自动对元素进行排序，每次取出堆顶元素（最大或最小元素）。插入和删除操作的时间复杂度均为 O (log n)。

**应用:**处理需要频繁获取最大或最小元素的问题，如 Dijkstra 算法中用于选取当前距离最小的节点、任务调度问题（每次选取优先级最高的任务）等。

哈希表

**原理:**过哈希函数将键映射到数组中的某个位置，实现快速的查找、插入和删除操作。哈希函数的设计至关重要，要尽量减少冲突，常用的解决冲突的方法有开放寻址法和链地址法。

**应用:**快速查找数据（如判断某个元素是否存在于集合中）、统计元素的出现次数（如在 “字母异位词分组” 问题中，用哈希表记录每个字母排序后的字符串对应的分组）等。

并查集

**原理:**每个集合用一个根节点表示，每个节点存储其父节点，通过路径压缩和按秩合并优化，使得查找和合并操作的时间复杂度接近 O (1)。

**应用:**解决不相交集的合并

int fa[MAXN];
inline void init(int n)
{
    for (int i = 1; i <= n; ++i)
        fa[i] = i;
}
int find(int x)
{
    if(x == fa[x])
        return x;
    else{
        fa[x] = find(fa[x]);  //父节点设为根节点
        return fa[x];         //返回父节点
    }
}
inline void merge(int i, int j)
{
    fa[find(i)] = find(j);
}

inline void init(int n)
{
    for (int i = 1; i <= n; ++i)
    {
        fa[i] = i;
        rank[i] = 1;
    }
}
inline void merge(int i, int j)
{
    int x = find(i), y = find(j);    //先找到两个根节点
    if (rank[x] <= rank[y])
        fa[x] = y;
    else
        fa[y] = x;
    if (rank[x] == rank[y] && x != y)
        rank[y]++;                   //如果深度相同且根节点不同，则新的根节点的深度+1
}

单调栈

**原理:**栈中的元素保持单调递增或递减的顺序。当新元素入栈时，弹出栈中不满足单调性的元素，直到栈顶元素满足单调性条件，然后将新元素入栈。

**应用:**求解序列中每个数最左边或最右边第一个大于（或小于）其的数

求解序列中所有子序列的最值和

        int[] left = new int[n];
        int[] right = new int[n];
        Deque<Integer> q = new LinkedList<>();
        //找下一个小于的,满足条件就出栈,出栈的代表已经找到了,他记录找到的坐标
        for (int i = 0; i < n; i++) {
            while (!q.isEmpty() && arr[q.peekLast()] >= arr[i]) {
                int index = q.pollLast();
                left[index]=i;
            }
            q.offerLast(i);
        }
        //最后没有找到记录为-1
        while (!q.isEmpty()) {
            int index = q.pollLast();
            left[index]=-1;
        }
        q.clear();
        //反向找也是最小
        for (int i = n-1; i >=0; i--) {
            while (!q.isEmpty() && arr[q.peekLast()] >= arr[i]) {
                int index = q.pollLast();
                right[index]=i;
            }
            q.offerLast(i);
        }
        while (!q.isEmpty()) {
            int index = q.pollLast();
            right[index]=-1;
        }
        System.out.println(Arrays.toString(left));
        System.out.println(Arrays.toString(right));

单调队列

**原理:**队列中的元素保持单调递增或递减的顺序。当新元素进入队列时，从队列尾部删除比新元素大（或小）的元素，然后将新元素加入队尾；同时，从队列头部删除超出窗口范围的元素。

**应用:**求解序列中每个长度为 k 的窗口的最值（最大值或最小值）。

        int[] V = {1, 3, -1, -3, 5, 3, 6, 7};
        int n = V.length;
        int m = 3; // 窗口大小
        Deque<Integer> Q = new LinkedList<>(); // 存储的是索引

        for (int i = 0; i < n; ++i) {
            // 如果队首元素的索引已滑出窗口，则弹出
            if (!Q.isEmpty() && i - Q.peekFirst() >= m) {
                Q.pollFirst();
            }
            // 保持队列单调递减：将所有比 V[i] 小的元素“退役”
            while (!Q.isEmpty() && V[Q.peekLast()] < V[i]) {
                Q.pollLast();
            }
            Q.offerLast(i); // 新元素入队

            // 如果已经形成一个完整窗口，就输出当前最大值
            if (i >= m - 1) {
                System.out.print(V[Q.peekFirst()] + " ");
            }
        }