集合和Map的总结

栈和队列

栈Stack

java.util.Stack 类是一个基于向量（Vector）实现的后进先出（LIFO）的堆栈数据结构。以下是 Stack 类的一些常用方法：

push(E item): 将指定的元素压入堆栈顶部。

1
2
3

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);

pop(): 移除堆栈顶部的对象，并返回该对象。
1
int poppedElement = stack.pop();
peek(): 查看堆栈顶部的对象，但不从堆栈中移除它。
1
int topElement = stack.peek();
empty(): 测试堆栈是否为空。
1
boolean isEmpty = stack.empty();
search(Object o): 返回对象在堆栈中的位置，以 1 为基数。
1
int position = stack.search(2);
elementAt(int index): 返回指定索引位置的元素（从堆栈顶部开始计数，以 1 为基数）。
1
int element = stack.elementAt(1);
size(): 返回堆栈的大小。
1
int size = stack.size();
capacity(): 返回堆栈的当前容量（已废弃，不推荐使用）。
1
int capacity = stack.capacity();

这是 Stack 类的一些常用方法。请注意，Stack 类自Java 1.0以来就存在，但由于它是基于向量的，而向量本身在Java Collections Framework 中不再推荐使用，所以在现代Java编程中，通常建议使用 Deque 接口的实现类，如 LinkedList 作为堆栈的替代。

官方文档中也有：

Deque 接口及其实现提供了 LIFO 堆栈操作的更完整和更一致的 set，应该优先使用此 set，而非此类。例如：

1	Deque<Integer> stack = new ArrayDeque<Integer>();

队列

Queue

Queue 接口是 Java Collections Framework 中定义的队列接口，它扩展了Collection接口。队列是一种先进先出（FIFO）的数据结构，即最先进入队列的元素最先被移除。以下是Queue接口定义的一些主要方法：

add(E e): 将指定的元素插入队列，如果队列已满则抛出异常。
1
2
Queue<Integer> queue = new LinkedList<>();
queue.add(1);
offer(E e): 将指定的元素插入队列，如果队列已满则返回false。
1
boolean added = queue.offer(2);
remove(): 移除并返回队列的头部元素，如果队列为空则抛出异常。
1
int removedElement = queue.remove();
poll(): 移除并返回队列的头部元素，如果队列为空则返回null。
1
Integer polledElement = queue.poll();
element(): 获取但不移除队列的头部元素，如果队列为空则抛出异常。
1
int headElement = queue.element();
peek(): 获取但不移除队列的头部元素，如果队列为空则返回null。
1
Integer headElement = queue.peek();

上述方法是 Queue 接口的核心方法，适用于实现了 Queue 接口的具体队列类，如 LinkedList、ArrayDeque 和 PriorityQueue。Queue 接口还有一些其他方法，如 clear()、size() 等，可以根据具体需求进行使用。请注意，Queue 接口主要用于表示队列的基本行为，具体实现类可能提供额外的方法和功能。

Deque

Deque（Double Ended Queue，双端队列）是Java Collections Framework中定义的双端队列接口。它继承自Queue接口，提供了在队列两端进行元素添加、移除和检查的操作。Deque 接口允许在队列的两端进行元素的操作，使其比普通队列更加灵活。

以下是Deque 接口的一些主要方法：

addFirst(E e): 在双端队列的开头添加元素。

1 2	Deque<Integer> deque = new LinkedList<>(); deque.addFirst(1);

addLast(E e): 在双端队列的末尾添加元素。
1
deque.addLast(2);
offerFirst(E e): 在双端队列的开头添加元素，如果队列已满，则返回false。
1
boolean added = deque.offerFirst(3);
offerLast(E e): 在双端队列的末尾添加元素，如果队列已满，则返回false。
1
boolean added = deque.offerLast(4);
removeFirst(): 移除并返回双端队列的开头元素。
1
int removedElement = deque.removeFirst();
removeLast(): 移除并返回双端队列的末尾元素。
1
int removedElement = deque.removeLast();
pollFirst(): 移除并返回双端队列的开头元素，如果队列为空，则返回null。
1
Integer removedElement = deque.pollFirst();
pollLast(): 移除并返回双端队列的末尾元素，如果队列为空，则返回null。
1
Integer removedElement = deque.pollLast();
getFirst(): 获取但不移除双端队列的开头元素，如果队列为空，则抛出异常。
1
int firstElement = deque.getFirst();
getLast(): 获取但不移除双端队列的末尾元素，如果队列为空，则抛出异常。
1
int lastElement = deque.getLast();
peekFirst(): 获取但不移除双端队列的开头元素，如果队列为空，则返回null。
1
Integer firstElement = deque.peekFirst();
peekLast(): 获取但不移除双端队列的末尾元素，如果队列为空，则返回null。
1
Integer lastElement = deque.peekLast();

Deque 接口有多个实现类，其中包括 ArrayDeque 和 LinkedList。具体选择哪个实现类取决于你的需求和性能要求。ArrayDeque 提供了基于数组的实现，而 LinkedList 则基于链表。根据具体场景，你可以选择适合你需求的实现。

ArrayDeque

ArrayDeque 是 Java 中的双端队列实现，基于可变数组（循环数组）的数据结构。它实现了 Deque 接口，允许在队列两端进行高效的元素插入和删除操作。以下是 ArrayDeque 类的一些主要方法：

1.添加元素

addFirst(E e)  //在数组前面添加元素
addLast(E e)  //在数组后面添加元素
offerFirst(E e)   //在数组前面添加元素，并返回是否添加成功
offerLast(E e)   //在数组后天添加元素，并返回是否添加成功

2.删除元素

removeFirst() //删除第一个元素，并返回删除元素的值,如果元素为null，将抛出异常
pollFirst()  //删除第一个元素，并返回删除元素的值，如果元素为null，将返回null
removeLast()  //删除最后一个元素，并返回删除元素的值，如果为null，将抛出异常 
pollLast()  //删除最后一个元素，并返回删除元素的值，如果为null，将返回null
removeFirstOccurrence(Object o)  //删除第一次出现的指定元素
removeLastOccurrence(Object o)  //删除最后一次出现的指定元素

3.获取元素

1 2	getFirst() //获取第一个元素,如果没有将抛出异常 getLast() //获取最后一个元素，如果没有将抛出异常

4.队列操作

add(E e)  //在队列尾部添加一个元素
offer(E e) //在队列尾部添加一个元素，并返回是否成功
remove() //删除队列中第一个元素，并返回该元素的值，如果元素为null，将抛出异常(其实底层调用的是removeFirst())
poll()  //删除队列中第一个元素，并返回该元素的值,如果元素为null，将返回null(其实调用的是pollFirst())
element() //获取第一个元素，如果没有将抛出异常
peek() //获取第一个元素，如果返回null

5.栈操作

1
2
3

push(E e)  //栈顶添加一个元素
pop(E e)  //移除栈顶元素,如果栈顶没有元素将抛出异常
peek()    //获取栈顶元素

6.其他

size() 获取队列中元素个数
isEmpty() 判断队列是否为空
iterator() 迭代器，从前向后迭代
descendingIterator() 迭代器，从后向前迭代
contain(Object o) 判断队列中是否存在该元素
toArray() 转成数组
clear() 清空队列
clone() 克隆(复制)一个新的队列

LinkedList

LinkedList 是Java中的一个双向链表实现，实现了List接口和Deque接口。以下是 LinkedList 类的一些常用方法：

1.添加元素

public boolean add(E e)，链表末尾添加元素，返回是否成功；
public void add(int index, E element)，向指定位置插入元素；
public boolean addAll(Collection<? extends E> c)，将一个集合的所有元素添加到链表后面，返回是否成功；
public boolean addAll(int index, Collection<? extends E> c)，将一个集合的所有元素添加到链表的指定位置后面，返回是否成功；
public void addFirst(E e)，添加到第一个元素；
public void addLast(E e)，添加到最后一个元素；
public boolean offer(E e)，向链表末尾添加元素，返回是否成功；
public boolean offerFirst(E e)，头部插入元素，返回是否成功；
public boolean offerLast(E e)，尾部插入元素，返回是否成功；

2.删除元素

public void clear()，清空链表；
public E removeFirst()，删除并返回第一个元素；
public E removeLast()，删除并返回最后一个元素；
public boolean remove(Object o)，删除某一元素，返回是否成功；
public E remove(int index)，删除指定位置的元素；
public E poll()，删除并返回第一个元素；
public E remove()，删除并返回第一个元素；

3.获取元素

public boolean contains(Object o)，判断是否含有某一元素；
public E get(int index)，返回指定位置的元素；
public E getFirst(), 返回第一个元素；
public E getLast()，返回最后一个元素；
public int indexOf(Object o)，查找指定元素从前往后第一次出现的索引；
public int lastIndexOf(Object o)，查找指定元素最后一次出现的索引；
public E peek()，返回第一个元素；
public E element()，返回第一个元素；
public E peekFirst()，返回头部元素；
public E peekLast()，返回尾部元素；

4.更改元素

1	public E set(int index, E element)，设置指定位置的元素；

5.其他

public Object clone()，克隆该列表；
public Iterator<E> descendingIterator()，返回倒序迭代器；
public int size()，返回链表元素个数；
public ListIterator<E> listIterator(int index)，返回从指定位置开始到末尾的迭代器；
public Object[] toArray()，返回一个由链表元素组成的数组；
public <T> T[] toArray(T[] a)，返回一个由链表元素转换类型而成的数组；

6.队列操作

1
2
3

peek() //返回此双端队列的第一个元素。
poll() //返回并删除队列中的第一个元素。
offer() //往队列中添加一个元素

7.栈操作

1
2
3

push(E e)  //栈顶添加一个元素
pop(E e)  //移除栈顶元素,如果栈顶没有元素将抛出异常
peek()    //获取栈顶元素

更多方法见官方文档Java LinkedList。

PriorityQueue

PriorityQueue 是 Java 中的优先级队列实现，它实现了 Queue 接口。优先级队列根据元素的优先级来确定出队顺序，具有较高优先级的元素会先被移出队列,非线程安全。以下是 PriorityQueue 类的一些常用方法：

add(E e): 将指定的元素插入此优先级队列。

1 2	PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(); priorityQueue.add(3);

offer(E e): 将指定的元素插入此优先级队列。
1
boolean added = priorityQueue.offer(5);

remove(): 移除并返回队列的头部元素。

1	int removedElement = priorityQueue.remove();

poll(): 移除并返回队列的头部元素，如果队列为空，则返回null。
1
Integer polledElement = priorityQueue.poll();
element(): 获取但不移除队列的头部元素，如果队列为空则抛出异常。
1
int headElement = priorityQueue.element();
peek(): 获取但不移除队列的头部元素，如果队列为空则返回null。
1
Integer headElement = priorityQueue.peek();
size(): 返回队列的元素个数。
1
int size = priorityQueue.size();
isEmpty(): 如果队列不包含任何元素，则返回true。
1
boolean isEmpty = priorityQueue.isEmpty();
clear(): 从队列中移除所有元素。
1
priorityQueue.clear();
comparator(): 返回用于确定元素顺序的比较器，如果队列使用自然顺序，则返回null。
1
Comparator<Integer> comparator = priorityQueue.comparator();
toArray(): 返回一个包含队列元素的数组。
1
Object[] elementsArray = priorityQueue.toArray();
toArray(T[] a): 返回一个包含队列元素的数组，如果提供的数组足够大，则将元素填充到该数组中。
1
Integer[] elementsArray = priorityQueue.toArray(new Integer[0]);

这是 PriorityQueue 类的一些主要方法。请注意，PriorityQueue 是根据元素的自然顺序或通过提供的比较器进行排序的。在构造 PriorityQueue 时，你可以传递一个比较器或者使用元素的自然顺序。

PriorityQueue 是 Java 集合框架中的一种实现，它是一个优先级队列，具有以下特点：

优先级排序： 元素在队列中并不是按照它们被插入的顺序排列，而是按照元素的优先级。优先级队列使用一个比较器（Comparator）或者元素的自然顺序来确定元素的顺序。
最小堆实现： Java 中的 PriorityQueue 实际上是使用最小堆（min-heap）来实现的，堆顶元素是最小的元素。这使得你可以快速找到并移除队列中最小的元素。
动态调整： 在插入和删除元素时，PriorityQueue 会动态地调整内部结构以保持堆的性质，因此具有较好的性能。

优先级排序是一种将元素按照优先级进行排列的排序方式。在 Java 中，PriorityQueue 是一个支持优先级排序的集合类，通常用于实现优先级队列。它的内部实现基于最小堆（min-heap）或最大堆（max-heap）。

最小堆和最大堆：

最小堆： 在一个最小堆中，每个节点的值都小于或等于其子节点的值。因此，堆顶元素是最小的元素。
最大堆： 在一个最大堆中，每个节点的值都大于或等于其子节点的值。因此，堆顶元素是最大的元素。

优先级队列的实现：

PriorityQueue 默认使用自然顺序来排序元素，或者通过在构造时提供一个比较器（Comparator）。下面是一个简单的例子：

PriorityQUeue<Integer> minHeap = new PriorityQueue<>(); //默认是最小堆
minHeap.add(3);
minHeap.add(2);
minHeap.add(1);
// 输出最小堆的元素 
while (!minHeap.isEmpty()) {
    System.out.println(minHeap.poll()); // 输出 1, 2, 3 
}

//如果要使用最大堆，可以提供一个比较器：
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>(){
    @Override
    public int compare(Integer a , Integer b){
        return a-b;
    }
}); // 使用最大堆
maxHeap.add(3);
maxHeap.add(1);
maxHeap.add(2);

// 输出最大堆的元素
while (!maxHeap.isEmpty()) {
    System.out.println(maxHeap.poll()); // 输出 3, 2, 1
}

异同比较

ArrayDeque 和 LinkedList 都是 Java Collections Framework 中的实现类，它们都实现了 Deque 接口，表示双端队列（double-ended queue）。尽管它们都支持在队列的两端进行高效的元素插入和删除操作，但它们在底层实现上有一些重要的区别。

ArrayDeque:

底层数据结构： ArrayDeque 使用可变数组实现，内部使用循环数组来存储元素。
随机访问： 支持通过索引直接访问元素，具有 O(1) 时间复杂度。
空间效率： 在一般情况下，ArrayDeque 使用的空间比 LinkedList 更小，因为它不需要额外的指针和链表节点开销。
线程安全： ArrayDeque 不是线程安全的，如果需要线程安全，可以通过 Collections.synchronizedDeque() 方法包装成线程安全的队列。

LinkedList:

底层数据结构： LinkedList 使用双向链表实现，每个元素都是一个节点，包含对前一个和后一个节点的引用。
随机访问： 不支持通过索引直接访问元素，获取元素需要遍历链表，具有 O(n) 时间复杂度。
空间效率： LinkedList 的空间开销相对较大，因为每个元素都需要额外的链表节点对象。
线程安全： LinkedList 也不是线程安全的，如果需要线程安全，可以通过 Collections.synchronizedList() 方法包装成线程安全的列表。

共同点:

两者都实现了 Deque 接口，支持双端队列的操作，如在队列头部和尾部进行元素的插入、删除等操作。
都允许 null 元素。

如何选择：

如果需要高效的随机访问和较小的空间开销，可以选择使用 ArrayDeque。
如果需要频繁在中间插入或删除元素，并且不太关心随机访问的性能，可以选择使用 LinkedList。
在某些情况下，性能可能因具体使用场景而异，因此根据实际需求进行选择。

声明的注意事项

在Java中，ArrayDeque是Deque接口的实现类，因此两者之间的关系是ArrayDeque实现了Deque接口。现在让我们来看一下给定的两个声明：

1 2	ArrayDeque<Integer> arrayDeque = new ArrayDeque<>(); Deque<Integer> arrayDeque = new ArrayDeque<>();

这两者的主要区别在于对变量的声明类型。在第一个声明中，arrayDeque的类型是具体的ArrayDeque，而在第二个声明中，arrayDeque的类型是Deque接口。

ArrayDeque arrayDeque = new ArrayDeque<>();

这里arrayDeque的类型是ArrayDeque，因此你可以使用ArrayDeque类的所有方法和属性。这种声明方式提供了更多的具体实现细节。
Deque arrayDeque = new ArrayDeque<>();

这里arrayDeque的类型是Deque接口，这是一种更抽象的声明方式。你只能使用Deque接口中定义的方法，而不能直接访问ArrayDeque特有的方法。这种声明方式更加灵活，因为你可以随时更改具体的实现类，而不需要修改引用变量的类型。

一般来说，为了编写更灵活、可维护的代码，建议使用接口类型（如Deque）而不是具体实现类型（如ArrayDeque），除非有特殊需要。这样你可以更容易地更改实现类而不影响其余代码。

// 使用接口类型声明变量 
Deque<Integer> deque; 

// 实例化具体的实现类 
deque = new ArrayDeque<>(); 
// 现在deque引用的是ArrayDeque实例 

// 在需要时切换到另一个实现类 
deque = new LinkedList<>(); 
// 现在deque引用的是LinkedList实例