作者：研J小政
课堂：wclass
（有什么弊端请私信我，目前参考众多资料精华整理过程过中）
章节：单列集合！
进度：持续更新迭代！
录课状态：待录
参考文献
Java的 Collection 框架是一组用于存储和操作对象的接口和类。
它提供了一种方便的方式来管理和操作数据集合。
Collection是Java集合框架的根接口，它定义了一些基本的操作和行为，如添加、删除、遍历等。
它有两个主要的子接口：List 和 Set
常见的实现类有ArrayList、LinkedList和Vector。
常见的实现类有HashSet、TreeSet和LinkedHashSet。
java.util.List接口继承自Collection接口，是单列集合的一个重要分支，习惯性地会将实现了List接口的对
象称为List集合，在List集合中允许出现重复的元素，所有的元素是以一种线性方式进行存储的，在程序中
可以通过索引来访问集合中的指定元素，另外List集合还有一个特点就是元素有序，即元素的存入顺序和取
出顺序一致。
Set 接口继承自 Collection 接口，并提供了不允许重复元素的集合。
以下是一些常用的 Set 接口方法：
以下是一个使用 HashSet 实现 Set 接口的示例代码：
import java.util.HashSet;
import java.util.Set;
public class SetExample {
public static void main(String[] args) {
Set<String> fruits = new HashSet<>();
fruits.add("Apple");
fruits.add("Banana");
fruits.add("Orange");
fruits.add("Apple"); // 重复元素，不会被添加
System.out.println("Fruits: " + fruits);
fruits.remove("Banana");
System.out.println("Fruits after removal: " + fruits);
boolean containsApple = fruits.contains("Apple");
System.out.println("Contains Apple: " + containsApple);
}
}在上述示例中，我们创建了一个 HashSet 实例，并添加了一些水果。
由于 HashSet 不允许重复元素，所以重复的苹果不会被添加到集合中。
然后，我们从集合中移除了一个元素，并判断集合是否包含苹果。
最后，我们打印了集合的内容。
队列是一种特殊的线性表，遵循先入先出、后入后出的基本原则，一般来说，它只允许在表的前端进行删
除操作，而在表的后端进行插入操作，但是java的某些队列运行在任何地方插入删除；比如我们常用的
LinkedList 集合，它实现了Queue 接口，因此，我们可以理解为LinkedList 就是一个队列；
队列主要分为阻塞和非阻塞，有界和无界、单向链表和双向链表之分；
阻塞队列
入列(添加元素)时，如果元素数量超过队列总数，会进行等待（阻塞），待队列的中的元素出列后，元素数量未超
过队列总数时，就会解除阻塞状态，进而可以继续入列；
出列(删除元素)时，如果队列为空的情况下，也会进行等待（阻塞），待队列有值的时候即会解除阻塞状态，进而
继续出列；
阻塞队列的好处是可以防止队列容器溢出；只要满了就会进行阻塞等待；也就不存在溢出的情况；
只要是阻塞队列，都是线程安全的；
非阻塞队列
不管出列还是入列，都不会进行阻塞，
入列时，如果元素数量超过队列总数，则会抛出异常，
出列时，如果队列为空，则取出空值；
一般情况下，非阻塞式队列使用的比较少，一般都用阻塞式的对象比较多；
阻塞和非阻塞队列在使用上的最大区别就是阻塞队列提供了以下2个方法：
有界：有界限，大小长度受限制
无界：无限大小，其实说是无限大小，其实是有界限的，只不过超过界限时就会进行扩容，就行ArrayList 一样，
在内部动态扩容
单向链表 ： 每个元素中除了元素本身之外，还存储一个指针，这个指针指向下一个元素；
双向链表 ：除了元素本身之外，还有两个指针，一个指针指向前一个元素的地址，另一个指针指向后一个
元素的地址；
| add | 增加一个元索 | 如果队列已满，则抛出一个IIIegaISlabEepeplian异常 |
| remove | 移除并返回队列头部的元素 | 如果队列为空，则抛出一个NoSuchElementException异常 |
| element | 返回队列头部的元素 | 如果队列为空，则抛出一个NoSuchElementException异常 |
| offer | 添加一个元素并返回true | 如果队列为空，则返回null |
| poll | 移除并返问队列头部的元素 | 如果队列为空，则返回null |
| peek | 返回队列头部的元素 | 如果队列为空，则返回null |
| put | 添加一个元素 | 如果队列满，则阻塞 |
| take | 一次性取出队列所有元素 | 如果队列为空，则阻塞 |
| drainTo(list) | 一次性取出队列所有元素 |
知识点： remove、element、offer 、poll、peek 其实是属于Queue接口。
单向链表结构的无界并发队列, 非阻塞队列，由CAS实现线程安全，内部基于节点实现
双向链表结构的无界并发队列, 非阻塞队列，由CAS实现线程安全
内部基于数组实现，线程不安全的队列
一个支持延时获取元素的无界阻塞队列
一个由链表结构组成的无界阻塞队列
有界队列，阻塞式,初始化时必须指定队列大小，且不可改变；，底层由数组实现；
最多只能存储一个元素，每一个put操作必须等待一个take操作，否则不能继续添加元素
一个带优先级的队列，而不是先进先出队列。元素按优先级顺序被移除，而且它也是无界的，也就是没有容量上
限，虽然此队列逻辑上是无界的，但是由于资源被耗尽，所以试图执行添加操作可能会导致 OutOfMemoryError
错误；
队列在 Queue 接口已经说过，不免讲解两次，加深印象！
队列：只可以在一段进行插入操作，在另一端进行删除操作的线性表，队列具有先进先出的特性，在插入
操作的一端称作队尾，进行删除操作的一端称作队头。
如上图：
Queue（队列）是一个接口，底层是一个双向链表来实现的，所以Queue不能直接实例化一个对象，
只能是接口引用一个具体类（LinkedList）的方式来实例化。
| 方法名 | 描述 |
| boolean offer（E e） | 入队列 |
| E poll（） | 出队列 |
| peek（） | 获取队头元素 |
| int size（） | 获取队列中的有效元素个数 |
| boolean isEmpty（） | 判断队列是否为空 |
public static void main(String[] args) {
//尾插法和头部删除
MyQueue queue = new MyQueue();
queue.offer(1);
queue.offer(2);
queue.offer(3);
System.out.println(queue.peek());//1
System.out.println(queue.poll());//1
System.out.println(queue.peek());//2
System.out.println(queue.isEmpty());//false
System.out.println(queue.usedSize);//3
}注：双向链表是最合适实现一个队列的，双向链表可以在尾部插入，也可以在尾部进行删除，因为每个节
点都有前驱和后继节点，插入和删除的时间复杂度都是O(1)，但是如果是单链表此时只能使用尾插法插
入，使用头删法（在头部进行删除）时间复杂度才是O(1)
//单链表实现一个队列
public class MyQueue {
static class Node {
public int val;
public Node next;
public Node(int val) {
this.val = val;
}
}
public Node head;
public Node last;
public int usedSize;
//入队
public void offer(int val) {
Node node = new Node(val);
if (head == null) {
head = node;
last = node;
}else {
last.next = node;
last = node;
}
usedSize++;
}
//出队
public int poll() {
if (isEmpty()) {
throw new EmptyException("队列是空的！");
}
int ret = head.val;
head = head.next;
if (head == null) {
last = null;//如果只有一个节点，那么last也要置空
}
usedSize--;
return ret;
}
//判断队列是否为空
public boolean isEmpty() {
return usedSize == 0;
}
//获取队列队顶元素
public int peek() {
if (isEmpty()) {
throw new EmptyException("队列是空的！");
}
return head.val;
}
//获取队列有效元素的个数
public int getUsedSize() {
return usedSize;
}
}如下图：
此时一个数组实现的顺序队列正在一边入队元素，一边出队元素，如果队列中的元素满了，此时元素再进
行出队，但是后边的元素是入不进来的，虽然前面的格子空出来了，但是此时元素只能从队尾进入，队头
出，可以看出，此时的队列的利用效率不是很高。
基于上述队列的缺点，此时就有了循环队列，如下图：
| 描述 |
| 1. 有front指针和rear指针同时指向数组的0下标，入队元素就让rear指针往后走一个，之后出队元素时，就让front指针向后移动。 |
| 2. 当循环队列满了，此时rear指针可以往前走一步，到达0下标，然后继续入队元素。 |
| 描述 |
| 1. 当队列满，如何让rear指针指向0下标？ |
| 2. 当队列满时，rear = front；当队列为空时，rear = front，所以如何判断队列的空和满？ |
package Review;
// 循环队列底层就是一个数组
// 浪费掉最后一个空间来表示队列是否是满的
// 就是每次都让rear往后走一步，之后进行判断如果rear的下一个位置就是0下标
// 此时队列就是满的，如果front == rear，此时队列是空的
class MyCircularQueue {
private int[] elem;
private int front;//队列的头
private int rear;//队列的尾
public MyCircularQueue(int k){
this.elem = new int[k+1];
}
public boolean enQueue(int value) {
//1.检查队列是否是满的
if (isFull()) {
return false;
}
//2.入队元素，之后让rear引用往后走一步
elem[rear] = value;
rear = (rear + 1) % elem.length;
return true;
}
public boolean deQueue() {
if (isEmpty()) {
return false;
}
//front++;
front = (front + 1) % elem.length;
return true;
}
public int Front() {
if (isEmpty()) {
return -1;
}
return elem[front];
}
public int Rear() {
if (isEmpty()) return -1;
//return elem[rear - 1];
//此时还有一个问题需要注意，如果rear到了0下标，之后就数组越界了
//数组是没有-1下标的，
//也就是让rear返回数组的最后一个下标
int index = (rear == 0) ? elem.length - 1 : rear - 1;
return elem[index];
}
public boolean isFull() {
return (rear + 1) % elem.length == front;
}
public boolean isEmpty() {
return front == rear;
}
}双端队列就是可以在两端都可以入队，也可以出队的队列，元素可以从队头入队和出队，
也可以从队尾出队和入队。
在实际使用中，Deque接口使用的是比较多的，栈和队列都可以使用该接口，这个接口中有栈的方法，
也有队列的方法
public static void main9(String[] args) {
//底层是一个双向链表
Deque<Integer> deque = new LinkedList<>();
//数组实现的双端队列：底层就是一个数组
Deque<Integer> deque1 = new ArrayDeque<>();
//顺序的双端队列也可以当作栈来使用
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
stack.push(3);//顺序的双端队列（底层是用数组来实现的）也提供了栈的相关的方法
}
public static void main8(String[] args) {
//双端队列
Deque<Integer> deque = new LinkedList<>();
//普通队列
//Queue中既有offer方法，也有add方法，add在无法添加一个元素时，会抛出一个异常
//offer方法优于add方法，如果无法添加元素，offer方法不会抛出异常
Queue<Integer> queue = new LinkedList<>();
//链式栈 虽然是具体的类但是里面有栈的方法
//LinkedList类中的方法是最多的，因为它实现了很多接口，此时一定会重写接口中的方法
LinkedList<Integer> stack = new LinkedList<>();
//双向链表
List<Integer> list = new LinkedList<>();
//其他的都是使用接口来引用的：只有接口中的方法
}