背景

本文是《Java 后端从小白到大神》修仙系列第五篇，正式进入Java后端世界，本篇文章主要聊Java基础中的数据结构。若想详细学习请点击首篇博文，我们开始吧。

章节概览

集合（Collection）
队列/双端队列（Queue/Deque）
数据结构选择指南

1. 集合（Collection）

集合是Java中用于存储和管理对象的容器，是Java Collections Framework的核心组件。

1.1 集合框架概述

Java Collections Framework (JCF) 是Java提供的一套用于存储和操作对象的统一架构，包含以下核心组件：

接口：定义集合的行为规范（如 Collection, List, Set, Map）
实现类：提供具体实现（如 ArrayList, LinkedList, HashSet, HashMap）
工具类：提供便捷操作（如 Collections, Arrays）

集合框架的层次结构：

Collection
├── List (有序，可重复)
│   ├── ArrayList (基于数组)
│   ├── LinkedList (基于链表)
│   └── Vector (线程安全)
├── Set (无序，不可重复)
│   ├── HashSet (基于哈希表)
│   ├── LinkedHashSet (基于链表+哈希表)
│   └── TreeSet (基于红黑树)
└── Queue (队列)
    ├── LinkedList (实现Deque接口)
    └── PriorityQueue (优先队列)

Map (键值对)
├── HashMap (基于哈希表)
├── LinkedHashMap (基于链表+哈希表)
├── TreeMap (基于红黑树)
└── Hashtable (线程安全)

1.1.1 核心底层数据结构：哈希表（Hash Table）

哈希表是 HashSet、HashMap 等集合的底层实现，核心是数组 + 哈希函数 + 冲突解决，是实现 O(1) 平均时间复杂度查询/插入的关键结构。

1. 核心结构

[ 哈希表底层结构（JDK8+） ]

index:   [0]   [1]   [2]   [3]   [4]   [5]   ...  ← 数组（桶 bucket）
          ↓     ↓     ↓     ↓     ↓     ↓
        null  node→  null  node→  null  node→
                     |           |           |
                     ↓           ↓           ↓
                   node→node    node        node→node→node  ← 链表（解决冲突）
                                      ↑
                                      |
                                    root（红黑树，链表≥8时转换）

2. 核心原理

数组：作为“桶”容器，每个下标对应一个存储位置。
哈希函数：通过 hashCode() 计算元素的哈希值，再对数组长度取模，得到元素应存放的数组下标。
哈希冲突：不同元素计算出相同下标时，通过链表（JDK8+ 链表过长时转为红黑树）将元素串联在同一下标下。

3. 关键特性

查询/插入效率：平均 O(1)，最坏 O(n)（冲突严重时），JDK8+ 红黑树优化后最坏为 O(log n)。
无序性：元素位置由哈希值决定，不保证插入顺序。
应用场景：HashSet（存元素）、HashMap（存键值对）均基于此结构，是 Java 集合中最常用的高效存储方案。

1.2 List 接口

List 只是一个接口，不是真正存数据的结构。

它只规定了一组规则：

元素有顺序（放进去什么顺序，取出来什么顺序）
可以重复
可以通过 下标（索引） 获取元素

真正存数据的，是它的实现类： ArrayList、LinkedList

1.2.1 ArrayList：基于动态数组的列表

底层结构

动态数组 → 内存里一整块连续空间
就像：一排连续的座位

优点

按下标找元素极快 get(i) → O(1)
遍历速度快

缺点

中间插入、删除慢 → 后面所有元素都要移动
满了要扩容（新开辟一块 1.5 倍大的空间，复制过去）

一句话总结

读多、改少、要快查 → 用 ArrayList

代码示例：

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class ArrayListDemo {
    public static void main(String[] args) {

        // ===================== 创建 ArrayList =====================
        List<String> list = new ArrayList<>();

        // 添加元素
        list.add("Java");
        list.add("Python");
        list.add("C++");

        // ===================== 随机访问（最快） =====================
        String first = list.get(0); // 按下标获取，O(1) 效率极高


        // ===================== 3 种遍历方式（精简版） =====================

        // 1. 普通 for 循环：需要索引时使用
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }

        // 2. 增强 for 循环：最简洁、最常用
        for (String lang : list) {
            System.out.println(lang);
        }

        // 3. 迭代器：遍历过程中【安全删除元素】唯一正确方式
        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            String element = iterator.next();
            if ("Python".equals(element)) {
                iterator.remove(); // 安全删除
            }
        }
    }
}

1.2.2 LinkedList：基于双向链表的列表

LinkedList 是 List 接口的实现类，底层是双向链表，真正存数据的结构。元素在内存中不连续，靠“指针”互相连接。

核心特性

底层结构：双向链表，元素分散存储，前后互相指向
查找效率：随机查找慢（不能直接跳位置，必须从头/尾遍历）
增删效率：头尾增删极快，不用移动其他元素
中间增删：比 ArrayList 快（不用拷贝移动数组）
额外能力：实现了队列/栈接口，可直接当队列、栈使用

优点

头尾添加、删除非常快（addFirst、addLast、removeFirst）
不需要扩容，用多少存多少
天然适合做队列、栈、双端队列

缺点

根据下标 get(i) 查找慢
占用内存比 ArrayList 多（要存前后指针）

最适合的场景

频繁在头部/尾部添加/删除
需要用队列、栈结构
元素数量经常变动、不怎么按下标查找

一句话总结

头尾增删多用 LinkedList，按下标查找多用 ArrayList。

代码示例：

import java.util.LinkedList;

public class LinkedListDemo {
    public static void main(String[] args) {
        // 创建 LinkedList
        LinkedList<String> list = new LinkedList<>();

        // 增删（头尾操作极快）
        list.add("Java");
        list.addFirst("头部元素");  // 头部添加
        list.addLast("尾部元素");   // 尾部添加

        // 取元素（头尾最快，中间慢）
        String first = list.getFirst();
        String last = list.getLast();

        // 当作 队列 使用
        list.offer("入队");
        String out = list.poll(); // 出队

        // 当作 栈 使用
        list.push("入栈");
        String pop = list.pop(); // 出栈
    }
}

1.2.3 Vector：线程安全的列表

Vector 是 古老版本的线程安全 ArrayList，也是 List 接口的实现类。

核心特性

底层结构：和 ArrayList 一样，基于动态数组
线程安全：方法都加了 synchronized 锁，多线程下不会乱
性能：因为要加锁解锁，比 ArrayList 慢很多
扩容：满了默认扩容为原来的 2 倍（ArrayList 是 1.5 倍）

优点

多线程环境下直接使用，不用自己加锁
简单、稳定、JDK 自带

缺点

并发性能差，高并发场景很慢
基本已经被淘汰，现代开发很少用

实际应用场景

老项目、遗留代码中还在使用
简单多线程场景，对性能要求不高
现在更推荐用 CopyOnWriteArrayList 替代

一句话总结

Vector = 线程安全但很慢的老式 ArrayList，现在基本不用。

代码示例

import java.util.Vector;

public class VectorDemo {
    public static void main(String[] args) {
        // 创建 Vector
        Vector<String> vector = new Vector<>();

        // 添加元素
        vector.add("Java");
        vector.add("Python");

        // 获取元素
        System.out.println(vector.get(0));
    }
}

1.2.4 List实现类对比

特性	ArrayList	LinkedList	Vector
底层实现	动态数组	双向链表	动态数组
随机访问	O(1)	O(n)	O(1)
中间插入/删除	O(n)	O(n)	O(n)
头尾插入/删除	O(n)	O(1)	O(n)
线程安全	否	否	是
内存占用	低	高（需存储指针）	低
适用场景	频繁随机访问	频繁增删	多线程环境

1.3 Set 接口（无序集合，元素唯一）

Set是无序的集合，不允许存储重复元素，适合需要保证元素唯一性的场景。

1.3.1 HashSet

核心特性：

底层实现：基于哈希表（HashMap）
元素顺序：无序，不保证插入顺序
查询效率：平均时间复杂度O(1)
允许null：允许存储一个null元素

实际应用场景：

需要快速去重的场景
不需要保持元素顺序的场景
频繁查询元素是否存在的场景

代码示例：

Set<String> hashSet = new HashSet<>();
// 添加元素
hashSet.add("Apple");
hashSet.add("Banana");
hashSet.add("Apple"); // 重复元素，不会被添加

// 检查元素是否存在
boolean contains = hashSet.contains("Apple"); // true

// 遍历
for (String fruit : hashSet) {
    System.out.println(fruit);
}

1.3.2 LinkedHashSet

核心特性：

底层实现：基于哈希表和双向链表
元素顺序：维护插入顺序
查询效率：接近O(1)，略低于HashSet
内存占用：高于HashSet（需维护链表结构）

实际应用场景：

需要去重且保持插入顺序的场景
需要按插入顺序遍历的场景

代码示例：

Set<String> linkedHashSet = new LinkedHashSet<>();
linkedHashSet.add("Zebra");
linkedHashSet.add("Apple");
linkedHashSet.add("Monkey");

// 按插入顺序遍历：Zebra, Apple, Monkey
for (String animal : linkedHashSet) {
    System.out.println(animal);
}

1.3.3 TreeSet

核心特性：

底层实现：基于红黑树
元素顺序：自然排序或自定义排序
查询效率：时间复杂度O(log n)
不允许null：不允许存储null元素

实际应用场景：

需要排序的场景
需要范围查询的场景（如获取最小值、最大值、子范围等）

代码示例：

// 自然排序
TreeSet<Integer> treeSet = new TreeSet<>();
treeSet.add(5);
treeSet.add(1);
treeSet.add(3);

// 自动排序：1, 3, 5
for (Integer number : treeSet) {
    System.out.println(number);
}

// 获取最小值和最大值
System.out.println("Min: " + treeSet.first()); // 1
System.out.println("Max: " + treeSet.last());  // 5

// 自定义排序
TreeSet<String> customSet = new TreeSet<>(Comparator.reverseOrder());
customSet.add("B");
customSet.add("A");
customSet.add("C");
// 输出：C, B, A

1.3.4 Set实现类对比

特性	HashSet	LinkedHashSet	TreeSet
底层实现	哈希表	哈希表+双向链表	红黑树
元素顺序	无序	插入顺序	自然排序或自定义排序
查询效率	O(1)	O(1)	O(log n)
插入/删除效率	O(1)	O(1)	O(log n)
内存占用	低	中	高
允许null	是	是	否
适用场景	快速去重	去重+保持顺序	排序+范围查询

1.4 Map 接口（键值对集合）

Map是存储键值对的集合，通过键来访问值，键不能重复。

1.4.1 HashMap

核心特性：

底层实现：基于哈希表（数组+链表/红黑树）
元素顺序：无序，不保证插入顺序
查询效率：平均时间复杂度O(1)
允许null：允许一个null键和多个null值
线程安全：非线程安全

实际应用场景：

需要通过键快速查找值的场景
不需要保持键值对顺序的场景
单线程环境下的键值对存储

代码示例：

Map<String, Integer> hashMap = new HashMap<>();
// 添加键值对
hashMap.put("Java", 100);
hashMap.put("Python", 95);
hashMap.put("C++", 90);

// 获取值
int javaScore = hashMap.get("Java"); // 100

// 遍历方式
// 1. 遍历键
for (String key : hashMap.keySet()) {
    System.out.println(key + ": " + hashMap.get(key));
}

// 2. 遍历键值对
for (Map.Entry<String, Integer> entry : hashMap.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

// 3. 遍历值
for (Integer value : hashMap.values()) {
    System.out.println(value);
}

1.4.2 LinkedHashMap

核心特性：

底层实现：基于哈希表和双向链表
元素顺序：维护插入顺序或访问顺序（可配置）
查询效率：接近O(1)，略低于HashMap
内存占用：高于HashMap（需维护链表结构）

实际应用场景：

需要保持插入顺序的场景
需要实现LRU缓存的场景（访问顺序模式）

代码示例：

// 插入顺序模式
Map<String, Integer> linkedHashMap = new LinkedHashMap<>();
linkedHashMap.put("Z", 3);
linkedHashMap.put("A", 1);
linkedHashMap.put("M", 2);

// 按插入顺序遍历：Z, A, M
for (Map.Entry<String, Integer> entry : linkedHashMap.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

// LRU缓存模式（访问顺序）
Map<String, Integer> lruCache = new LinkedHashMap<>(16, 0.75f, true);
lruCache.put("A", 1);
lruCache.put("B", 2);
lruCache.put("C", 3);

// 访问A，使其成为最近使用的元素
lruCache.get("A");

// 遍历顺序：B, C, A（最近访问的在最后）

1.4.3 TreeMap

核心特性：

底层实现：基于红黑树
元素顺序：按键自然排序或自定义排序
查询效率：时间复杂度O(log n)
不允许null：不允许null键，允许null值

实际应用场景：

需要按键排序的场景
需要范围查询的场景（如获取子Map、首尾键等）

代码示例：

// 自然排序
TreeMap<String, Integer> treeMap = new TreeMap<>();
treeMap.put("B", 2);
treeMap.put("A", 1);
treeMap.put("C", 3);

// 按键排序遍历：A, B, C
for (Map.Entry<String, Integer> entry : treeMap.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

// 获取首尾键
System.out.println("First key: " + treeMap.firstKey()); // A
System.out.println("Last key: " + treeMap.lastKey());   // C

// 范围查询
SortedMap<String, Integer> subMap = treeMap.subMap("A", "C"); // 包含A，不包含C

1.4.4 Hashtable

核心特性：

底层实现：基于哈希表
线程安全：所有方法都有synchronized修饰
性能：由于同步开销，性能比HashMap差
不允许null：不允许null键和null值

实际应用场景：

多线程环境下需要线程安全的键值对存储
对性能要求不高的场景

代码示例：

Hashtable<String, Integer> hashtable = new Hashtable<>();
hashtable.put("Key1", 10);
hashtable.put("Key2", 20);
System.out.println(hashtable.get("Key1")); // 10

1.4.5 Map实现类对比

特性	HashMap	LinkedHashMap	TreeMap	Hashtable
底层实现	哈希表	哈希表+双向链表	红黑树	哈希表
元素顺序	无序	插入顺序或访问顺序	按键排序	无序
查询效率	O(1)	O(1)	O(log n)	O(1)
插入/删除效率	O(1)	O(1)	O(log n)	O(1)
线程安全	否	否	否	是
允许null	是	是	键可空值不可空	键值都不许空
适用场景	快速查找	保持顺序或LRU缓存	排序+范围查询	多线程环境

1.5 集合的实际应用示例

1.5.1 使用HashSet进行数据去重

场景：从用户输入中去重，确保每个元素只出现一次。

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class DuplicateRemover {
    public static void main(String[] args) {
        // 模拟用户输入的重复数据
        String[] userInputs = {"apple", "banana", "apple", "orange", "banana", "grape"};
        
        // 使用HashSet去重
        Set<String> uniqueFruits = new HashSet<>(Arrays.asList(userInputs));
        
        System.out.println("去重后的水果：");
        for (String fruit : uniqueFruits) {
            System.out.println(fruit);
        }
        // 输出：apple, banana, orange, grape（顺序可能不同）
    }
}

1.5.2 使用LinkedHashMap实现LRU缓存

场景：实现一个简单的LRU（最近最少使用）缓存，当缓存容量达到上限时，移除最久未使用的元素。

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache<K, V> {
    private final int capacity;
    private final Map<K, V> cache;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        // 第三个参数为true，表示按访问顺序排序
        this.cache = new LinkedHashMap<K, V>(capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return size() > capacity;
            }
        };
    }
    
    public V get(K key) {
        return cache.get(key);
    }
    
    public void put(K key, V value) {
        cache.put(key, value);
    }
    
    public void display() {
        System.out.println("缓存内容：" + cache);
    }
    
    public static void main(String[] args) {
        LRUCache<String, Integer> cache = new LRUCache<>(3);
        
        cache.put("A", 1);
        cache.put("B", 2);
        cache.put("C", 3);
        cache.display(); // 输出：{A=1, B=2, C=3}
        
        // 访问A，使其成为最近使用的
        cache.get("A");
        cache.display(); // 输出：{B=2, C=3, A=1}
        
        // 添加新元素D，会移除最久未使用的B
        cache.put("D", 4);
        cache.display(); // 输出：{C=3, A=1, D=4}
    }
}

1.5.3 使用TreeMap实现区间查询

场景：根据分数区间查询学生信息。

import java.util.TreeMap;
import java.util.SortedMap;

public class StudentScore {
    public static void main(String[] args) {
        // 存储学生分数，键为分数，值为学生姓名
        TreeMap<Integer, String> scoreMap = new TreeMap<>();
        scoreMap.put(85, "Alice");
        scoreMap.put(92, "Bob");
        scoreMap.put(78, "Charlie");
        scoreMap.put(95, "David");
        scoreMap.put(88, "Eve");
        
        // 查询80-90分之间的学生
        SortedMap<Integer, String> rangeMap = scoreMap.subMap(80, 91);
        System.out.println("80-90分的学生：");
        for (Map.Entry<Integer, String> entry : rangeMap.entrySet()) {
            System.out.println(entry.getValue() + ": " + entry.getKey());
        }
        // 输出：
        // Alice: 85
        // Eve: 88
        
        // 查询最高分和最低分
        System.out.println("最高分：" + scoreMap.lastEntry().getValue() + ": " + scoreMap.lastKey());
        System.out.println("最低分：" + scoreMap.firstEntry().getValue() + ": " + scoreMap.firstKey());
    }
}

1.6 集合的常用方法

1.6.1 Stream API 操作

Java 8 引入的 Stream API 提供了丰富的集合操作方法，能以声明式的方式处理集合元素。

过滤操作：

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

public class FilterExample {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        List<Integer> filteredList = list.stream().filter(i -> i > 1).collect(Collectors.toList());
        System.out.println(filteredList); // 输出：[2, 3]
    }
}

映射操作：

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

public class MapExample {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        List<String> stringList = list.stream().map(i -> String.valueOf(i)).collect(Collectors.toList());
        System.out.println(stringList); // 输出：["1", "2", "3"]
    }
}

归约操作：

/**
 * 
规约（Reduce）的核心是：把一个集合（比如 List）里的多个元素，通过指定的规则，“合并 / 汇总” 成一个单一的值（可以是数字、字符串、对象等）
初始状态：累计值 = 初始值 0
第一步：累计值(0) + 当前元素(1) → 新累计值=1
第二步：累计值(1) + 当前元素(2) → 新累计值=3
第三步：累计值(3) + 当前元素(3) → 新累计值=6
最终返回：6
 */
import java.util.ArrayList;
import java.util.List;

public class ReduceExample {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        Integer sum = list.stream().reduce(0, (a, b) -> a + b);
        System.out.println(sum); // 输出：6
    }
}

1.6.2 Collections 工具类方法

排序操作：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class SortExample {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(3);
        list.add(1);
        list.add(2);
        Collections.sort(list);
        System.out.println(list); // 输出：[1, 2, 3]
    }
}

线程安全包装：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class SynchronizedListExample {
    public static void main(String[] args) {
        List<String> originalList = new ArrayList<>();
        List<String> synchronizedList = Collections.synchronizedList(originalList);
        // 现在synchronizedList是线程安全的
    }
}

不可变包装：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class UnmodifiableListExample {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("apple");
        List<String> unmodifiableList = Collections.unmodifiableList(list);
        try {
            unmodifiableList.add("banana"); // 会抛出异常
        } catch (UnsupportedOperationException e) {
            System.out.println("修改不可修改的列表会抛出异常");
        }
    }
}

2. 队列/双端队列（Queue/Deque）

队列是一种先进先出（FIFO）的数据结构，双端队列（Deque）则允许在两端进行元素的插入和删除操作。

2.1 Queue接口

Queue接口定义了队列的基本操作，主要方法包括：

offer(E e)：添加元素到队尾，成功返回true
poll()：移除并返回队首元素，队列为空返回null
peek()：返回队首元素但不移除，队列为空返回null
size()：返回队列元素数量
isEmpty()：判断队列是否为空

2.2 PriorityQueue：优先级队列

核心特性：

底层实现：基于优先级堆（二叉堆）
元素顺序：按自然顺序或自定义Comparator排序
出队顺序：优先级最高的元素先出队（默认是最小元素）
时间复杂度：插入和删除操作的时间复杂度为O(log n)
不允许null：不允许存储null元素

实际应用场景：

任务调度系统（按优先级处理任务）
事件处理系统（按事件优先级处理）
图算法（如Dijkstra最短路径算法）
模拟系统（按事件发生时间排序）

代码示例：

import java.util.Comparator;
import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // 默认最小优先队列
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        minHeap.offer(5);
        minHeap.offer(1);
        minHeap.offer(3);
        System.out.println(minHeap.poll()); // 输出 1
        System.out.println(minHeap.poll()); // 输出 3
        System.out.println(minHeap.poll()); // 输出 5

        // 最大优先队列（使用自定义Comparator）
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
        maxHeap.offer(5);
        maxHeap.offer(1);
        maxHeap.offer(3);
        System.out.println(maxHeap.poll()); // 输出 5
        System.out.println(maxHeap.poll()); // 输出 3
        System.out.println(maxHeap.poll()); // 输出 1

        // 自定义对象的优先级队列
        class Task {
            private String name;
            private int priority;
            
            public Task(String name, int priority) {
                this.name = name;
                this.priority = priority;
            }
            
            public int getPriority() {
                return priority;
            }
            
            @Override
            public String toString() {
                return name + "(" + priority + ")";
            }
        }

        // 按优先级降序排列的任务队列
        PriorityQueue<Task> taskQueue = new PriorityQueue<>
            (Comparator.comparingInt(Task::getPriority).reversed());
        taskQueue.offer(new Task("Task1", 1));
        taskQueue.offer(new Task("Task2", 5));
        taskQueue.offer(new Task("Task3", 3));

        while (!taskQueue.isEmpty()) {
            System.out.println(taskQueue.poll());
        }
        // 输出：
        // Task2(5)
        // Task3(3)
        // Task1(1)
    }
}

2.3 ArrayDeque：数组双端队列

核心特性：

底层实现：基于循环数组
操作效率：两端的插入和删除操作时间复杂度为O(1)
容量管理：自动扩容，无容量限制
元素类型：可存储null元素
实现接口：实现了Deque接口，可作为队列、双端队列或栈使用

实际应用场景：

实现队列（FIFO）
实现栈（LIFO）
实现双端队列（两端操作）
需要高效两端操作的场景

代码示例：

import java.util.ArrayDeque;
import java.util.Deque;

public class ArrayDequeExample {
    public static void main(String[] args) {
        // 作为队列使用（FIFO）
        Deque<String> queue = new ArrayDeque<>();
        queue.offer("First");  // 添加到队尾
        queue.offer("Second");
        queue.offer("Third");
        System.out.println(queue.poll()); // 输出 First（队首）
        System.out.println(queue.poll()); // 输出 Second

        // 作为栈使用（LIFO）
        Deque<String> stack = new ArrayDeque<>();
        stack.push("First");   // 添加到栈顶
        stack.push("Second");
        stack.push("Third");
        System.out.println(stack.pop()); // 输出 Third（栈顶）
        System.out.println(stack.pop()); // 输出 Second

        // 作为双端队列使用
        Deque<String> deque = new ArrayDeque<>();
        deque.offerFirst("Front");    // 添加到队首
        deque.offerLast("Rear");     // 添加到队尾
        deque.offerFirst("Very Front");

        System.out.println(deque.pollFirst()); // 输出 Very Front
        deque.offerLast("Very Rear");
        System.out.println(deque.pollLast());  // 输出 Very Rear
        System.out.println(deque.pollFirst()); // 输出 Front
        System.out.println(deque.pollLast());  // 输出 Rear
    }
}

2.4 LinkedList：链表双端队列

核心特性：

底层实现：基于双向链表
操作效率：两端的插入和删除操作时间复杂度为O(1)
内存占用：比ArrayDeque更高（需要存储指针）
实现接口：实现了Deque接口，可作为队列、双端队列或栈使用

实际应用场景：

需要频繁在两端操作的场景
元素数量变化较大的场景
实现队列、栈或双端队列

代码示例：

import java.util.Deque;
import java.util.LinkedList;

public class LinkedListDequeExample {
    public static void main(String[] args) {
        // 作为队列使用
        Deque<String> queue = new LinkedList<>();
        queue.offer("A");
        queue.offer("B");
        queue.offer("C");
        System.out.println(queue.poll()); // 输出 A

        // 作为栈使用
        Deque<String> stack = new LinkedList<>();
        stack.push("X");
        stack.push("Y");
        stack.push("Z");
        System.out.println(stack.pop()); // 输出 Z

        // 作为双端队列使用
        Deque<String> deque = new LinkedList<>();
        deque.offerFirst("1");
        deque.offerLast("3");
        deque.offerFirst("0");
        deque.offerLast("4");
        System.out.println(deque.pollFirst()); // 输出 0
        System.out.println(deque.pollLast());  // 输出 4
    }
}

2.5 队列实现类对比

特性	PriorityQueue	ArrayDeque	LinkedList
底层实现	优先级堆	循环数组	双向链表
元素顺序	按优先级排序	插入顺序	插入顺序
出队顺序	优先级最高	FIFO（队列）/ LIFO（栈）	FIFO（队列）/ LIFO（栈）
两端操作	仅队首操作	支持两端操作	支持两端操作
时间复杂度	插入/删除：O(log n)	两端操作：O(1)	两端操作：O(1)
内存占用	低	低	高
适用场景	优先级任务处理	高效队列/栈	频繁两端操作

2.6 队列的实际应用

消息队列：
- 异步处理任务
- 系统间通信
- 流量削峰
任务调度：
- 线程池任务队列
- 定时任务调度
- 优先级任务处理
广度优先搜索（BFS）：
- 图的遍历
- 最短路径算法
- 层次遍历
缓冲区：
- 数据采集缓冲区
- 网络数据缓冲区
- 生产-消费者模式

代码示例：使用队列实现广度优先搜索

import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

public class BFSExample {
    public static void main(String[] args) {
        // 简单的图结构
        Map<String, List<String>> graph = new HashMap<>();
        graph.put("A", List.of("B", "C"));
        graph.put("B", List.of("D", "E"));
        graph.put("C", List.of("F"));
        graph.put("D", Collections.emptyList());
        graph.put("E", List.of("F"));
        graph.put("F", Collections.emptyList());
        
        // 调用BFS
        bfs(graph, "A"); // 输出：A B C D E F
    }
    
    // BFS遍历
    public static void bfs(Map<String, List<String>> graph, String start) {
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        
        queue.offer(start);
        visited.add(start);
        
        while (!queue.isEmpty()) {
            String current = queue.poll();
            System.out.print(current + " ");
            
            for (String neighbor : graph.get(current)) {
                if (!visited.contains(neighbor)) {
                    queue.offer(neighbor);
                    visited.add(neighbor);
                }
            }
        }
    }
}

3. 数据结构选择指南

选择合适的数据结构是提高程序效率和可维护性的关键。以下是根据不同场景选择数据结构的指南：

3.1 根据操作类型选择

操作类型	推荐数据结构	原因
频繁随机访问	`ArrayList`	时间复杂度O(1)
频繁增删元素	`LinkedList`	两端操作时间复杂度O(1)
需要元素唯一	`HashSet`	快速去重，查询O(1)
需要按键查找	`HashMap`	键值对映射，查询O(1)
需要排序	`TreeSet` / `TreeMap`	自动排序，支持范围查询
需要优先级	`PriorityQueue`	按优先级处理元素
需要FIFO操作	`ArrayDeque` / `LinkedList`	高效队列操作
需要LIFO操作	`ArrayDeque` / `LinkedList`	高效栈操作

3.2 根据内存使用选择

内存限制	推荐数据结构	原因
内存紧张	数组 / `ArrayList`	内存占用低
内存充足	`LinkedList` / `HashSet`	功能更丰富

3.3 根据线程安全选择

并发需求	推荐数据结构	原因
单线程	所有非线程安全集合	性能更好
多线程	`Vector` / `Hashtable` / 同步包装集合	线程安全
高并发	`ConcurrentHashMap` / `CopyOnWriteArrayList`	并发性能更好

3.4 实际应用场景选择

应用场景	推荐数据结构	原因
用户列表	`ArrayList`	频繁访问，较少修改
黑名单	`HashSet`	快速判断元素是否存在
配置信息	`HashMap`	键值对存储，快速查找
任务调度	`PriorityQueue`	按优先级处理任务
消息队列	`ArrayDeque`	高效FIFO操作
浏览器历史	`LinkedList`	频繁增删操作
缓存	`LinkedHashMap`	支持LRU缓存策略

总结

Java提供了丰富的数据结构实现，每种数据结构都有其独特的特点和适用场景：

集合：
- List：有序，允许重复，适合需要索引访问的场景。
- Set：无序，元素唯一，适合去重和快速查找。
- Map：键值对存储，适合通过键快速查找值。
队列：
- PriorityQueue：按优先级处理元素。
- ArrayDeque：高效双端队列，适合队列和栈操作。
- LinkedList：双向链表实现，适合频繁两端操作。

选择数据结构时，应根据具体的操作需求、内存限制和并发场景来综合考虑，以达到最佳的性能和可维护性。通过合理选择和使用数据结构，可以显著提高程序的效率和质量。