队列
队列：一种遵循先进先出(First-In-First-Out，FIFO)原则的线性数据结构，在Java中，Queue 是一个接口，它继承自 Collection 接口，并提供了处理队列数据结构的方法。
普通队列
使用LinkedList类
Queue<Integer> queue = new LinkedList<>();
LinkedList基于双向链表实现，链表中的节点在内存中是离散存储的，每个节点包含数据和指向前一个节点和后一个节点的引用。要访问链表中第 i 个元素，需要从链表的头节点或尾节点开始，依次遍历链表，直到找到第 i 个节点，时间复杂度为O(n)。
时间复杂度：
正常情况下O(1)；
如果使用get(int index)方法根据索引访问元素，由于链表不支持随机访问，需要从链表头或尾开始遍历到指定位置，平均时间复杂度为O(n)。
如果使用remove(Object o)方法删除指定对象时，需要遍历链表找到该元素，最坏情况下要遍历整个链表，时间复杂度为O(n)。
LinkedList相关方法
入队：
add(E e)：将指定的元素插入此队列，如果插入成功则返回true，由于LinkedList没有容量限制，因此不会出现容量限制插入失败则抛出IllegalStateException；
offer(E e)：将指定的元素插入此队列，如果可以插入元素，则返回true；否则返回false。与add方法不同，该方法不会抛出异常。出队：
remove()：移除并返回队列头部元素。若队列为空，则抛出NoSuchElementException；
poll()：移除并返回队列的头部元素。若队列为空，则返回null。检查元素：
element()：返回队列头部元素，但不移除。若队列为空，抛出NoSuchElementException；
peek()：返回队列的头部元素，但不移除。如果队列为空，则返回null。
判断队列是否为空：
isEmpty()：判断队列是否为空，如果队列为空则返回true，否则返回false。
返回元素个数：
size()：返回队列中的元素个数。移除队列所有元素：
clear()：移除队列中的所有元素。
使用ArrayDeque类
Queue<Integer> queue = new ArrayDeque<>();
ArrayDeque基于可动态调整大小的循环数组实现，数组中的元素在内存中是连续存储的。该数组有一个头指针和一个尾指针，分别指向队列的头部元素和下一个要插入元素的位置。
当需要在队列头部或尾部添加元素时，会根据头指针或尾指针的位置进行操作。如果数组空间不足，会创建一个更大的新数组，并将原数组中的元素复制到新数组中。
要访问队列中第 i 个元素，可以直接通过数组的索引计算来定位该元素，由于数组元素在内存中是连续存储的，所以可以直接通过计算得到的索引快速访问元素，时间复杂度为O(1) 。
在队列头部或尾部进行插入和删除操作时，只要数组还有空间，操作可以在常数时间内完成，即时间复杂度为O(1) 。如果插入操作导致数组空间不足而触发扩容操作，扩容时需要将原数组元素复制到新数组，此时时间复杂度为O(n) ，但从均摊的角度来看，插入和删除操作的均摊时间复杂度仍然为O(1) 。
时间复杂度：
正常情况下O(1)；
如果插入操作导致数组空间不足而触发扩容操作，扩容时需要将原数组元素复制到新数组，此时时间复杂度为O(n)。
ArrayDeque相关方法
入队：
add(E e)：将指定的元素插入此队列，如果插入成功则返回true，由于ArrayDeque会自动扩容，一般不会因容量限制而插入失败，若在一些极端自定义场景下无法添加元素，会抛出IllegalStateException；
offer(E e)：将指定的元素插入此队列，如果可以插入元素，则返回true；否则返回false。与 add 方法不同，该方法不会抛出异常。出队：
remove()：移除并返回队列头部元素。若队列为空，则抛出NoSuchElementException；
poll()：移除并返回队列的头部元素。若队列为空，则返回null。检查元素：
element()：返回队列头部元素，但不移除。若队列为空，抛出NoSuchElementException；
peek()：返回队列的头部元素，但不移除。如果队列为空，则返回null。
判断队列是否为空：
isEmpty()：判断队列是否为空，如果队列为空则返回 true，否则返回false。
返回元素个数：
size()：返回队列中的元素个数。移除队列所有元素：
clear()：移除队列中的所有元素。ArrayDeque特有的方法：
双端队列入队：
addFirst(E e)用于在双端队列的头部插入元素，addLast(E e)用于在双端队列的尾部插入元素。
双端队列出队：
removeFirst()移除并返回双端队列的第一个元素，removeLast()移除并返回双端队列的最后一个元素。
使用PriorityQueue类
Queue<Integer> queue = new PriorityQueue<>();
PriorityQueue基于堆(通常为二叉堆)这种数据结构实现的，堆在逻辑上是一棵完全二叉树，物理上使用数组来存储节点元素。在当作普通队列使用时，若插入元素不指定比较规则，它默认按照元素的自然顺序(对于 Integer 类型就是数值大小)构建最小堆。
当把PriorityQueue用作普通队列时，实际上是按照先进先出(FIFO)的规则来使用这个优先队列，不过PriorityQueue本身是基于堆结构实现的，默认会根据元素的自然顺序或者指定的比较器来维护堆的性质。
当向当作普通队列使用的PriorityQueue中添加元素时，元素会被插入到堆中。由于要维护堆的性质，插入元素的操作和普通优先队列插入一致，会将元素添加到堆的末尾位置，然后通过"上浮"操作来调整堆的结构。"上浮"操作是将新插入的元素与其父节点比较，如果不满足堆的性质(对于默认的最小堆，若新元素比父节点小)，则交换它们的位置，继续向上比较，直到满足堆的性质或到达堆顶。
当向当作普通队列使用的PriorityQueue中移除元素时，会移除堆顶元素。虽然普通队列移除的是最先进入的元素，而PriorityQueue移除的是堆顶最小元素，但可以通过为元素赋予特殊的优先级，比如按元素入队顺序递增的优先级，来模拟FIFO顺序。移除堆顶元素后，会将堆的最后一个元素移动到堆顶位置，然后通过“下沉”操作来调整堆的结构。"下沉"操作是将堆顶元素与其子节点比较，如果不满足堆的性质(对于最小堆，若堆顶元素比子节点大)，则将其与较小的子节点交换位置，继续向下比较，直到满足堆的性质或到达叶子节点。
要访问当作普通队列使用的PriorityQueue中的元素，由于堆结构的特性，不能直接通过索引定位元素。若要查找队列中的第 i 个元素，需要对堆进行遍历，时间复杂度为O(n)。
在向当作普通队列使用的 PriorityQueue 中插入元素时，插入操作本身是将元素添加到堆的末尾，这一步时间复杂度为O(1)，但插入后为了维护堆的性质需要进行"上浮"操作，在最坏情况下，"上浮"操作需要从堆的末尾一直到堆顶，时间复杂度为O(logn)。
当作普通队列使用的PriorityQueue中删除元素时，删除堆顶元素后将最后一个元素移到堆顶并进行“下沉”操作，"下沉"操作在最坏情况下需要从堆顶一直到叶子节点，时间复杂度也为O(logn)。
当堆需要扩容时，会创建一个更大的新数组，并将原数组中的元素复制到新数组中，这一步操作的时间复杂度为O(n)，但扩容操作不是每次插入都会触发，从均摊的角度来看，插入和删除操作的均摊时间复杂度仍然为O(logn)。
时间复杂度：
插入和删除操作的时间复杂度为O(logn)，因为每次插入或删除元素后都需要进行堆调整操作，堆调整操作的时间复杂度与堆的高度相关，而堆的高度为O(logn)。
查找队列中的第 i 个元素，时间复杂度为O(n)，因为不能直接通过索引定位元素，需要遍历堆来查找。
PriorityQueue相关方法
入队：
add(E e)：将指定的元素插入此队列，如果插入成功则返回true，由于PriorityQueue没有容量限制，因此不会出现容量限制插入失败则抛出IllegalStateException；
offer(E e)：将指定的元素插入此队列，如果可以插入元素，则返回true；否则返回false。与add方法不同，该方法不会抛出异常，由于PriorityQueue没有容量限制，一般不会返回false。出队：
remove()：移除并返回队列头部元素。若队列为空，则抛出NoSuchElementException；
poll()：移除并返回队列的头部元素。若队列为空，则返回null。检查元素：
element()：返回队列头部元素，但不移除。若队列为空，抛出NoSuchElementException；
peek()：返回队列的头部元素，但不移除。如果队列为空，则返回null。
判断队列是否为空：
isEmpty()：判断队列是否为空，如果队列为空则返回 true，否则返回false。
返回元素个数：
size()：返回队列中的元素个数。移除队列所有元素：
clear()：移除队列中的所有元素。
优先队列
PriorityQueue<Integer> pq = new PriorityQueue<>();
优先队列中的元素按照优先级排序，默认情况下，使用元素的自然顺序(对于实现了 Comparable 接口的元素)，可以通过自定义比较器来改变排序规则。Java中使用PriorityQueue类实现优先队列。
PriorityQueue基于堆(通常是二叉堆)这种数据结构实现。在逻辑上，堆表现为一棵完全二叉树，而在物理存储上，使用数组来存放节点元素。当不指定比较规则时，对于实现了 Comparable 接口的元素(如 Integer 类型)，会按照元素的自然顺序构建最小堆，即堆顶元素是队列中的最小元素。
插入过程：当向优先队列中添加元素时，元素会被插入到堆的末尾位置。这是因为堆在物理上使用数组存储，新元素直接添加到数组的末尾，此操作时间复杂度为O(1)。
堆调整：插入元素后，为了维护堆的性质，需要进行"上浮"操作。"上浮"操作是将新插入的元素与其父节点进行比较，如果不满足堆的性质(对于最小堆，若新元素比父节点小)，则交换它们的位置，然后继续向上与新的父节点比较，直到满足堆的性质或者到达堆顶。在最坏情况下，新元素可能需要从堆的末尾一直上浮到堆顶，涉及的比较和交换次数与堆的高度相关，由于堆是完全二叉树，其高度为O(logn)，所以"上浮"操作的时间复杂度为O(logn)。
移除元素：移除操作会移除堆顶元素，因为堆顶元素是当前队列中优先级最高的元素(对于最小堆就是最小元素)。移除堆顶元素后，为了保持堆的结构完整性，会将堆的最后一个元素移动到堆顶位置。
堆调整：接着进行“下沉”操作。"下沉"操作是将堆顶元素与其子节点比较，如果不满足堆的性质(对于最小堆，若堆顶元素比子节点大)，则将其与较小的子节点交换位置，然后继续向下与新的子节点比较，直到满足堆的性质或者到达叶子节点。在最坏情况下，"下沉"操作需要从堆顶一直到叶子节点，时间复杂度同样为O(logn)。
查找队列中的第i个元素：需要对堆进行遍历，在遍历过程中，需要检查堆中的每个元素，因此时间复杂度为O(n)。
扩容操作：当堆中的元素数量达到数组的容量上限时，需要进行扩容操作。扩容时会创建一个更大的新数组，并将原数组中的元素复制到新数组中，这个过程涉及到对原数组中所有元素的复制，时间复杂度为O(n)。不过，扩容操作并不是每次插入都会触发，从均摊的角度来看，插入和删除操作的均摊时间复杂度仍然为O(logn)。
优先级调整：在优先队列中，元素的优先级决定了它们在堆中的位置。可以通过自定义比较器来指定元素的优先级规则。例如，对于自定义对象，可以根据对象的某个属性来定义比较规则，从而实现不同的优先级策略。
时间复杂度：
插入和删除操作的均摊时间复杂度为O(logn)
查找任意元素的时间复杂度为O(n)。
PriorityQueue构造方法
PriorityQueue()：创建一个初始容量为 11 的优先队列，元素按照自然顺序排序。
PriorityQueue(int initialCapacity)：创建一个指定初始容量的优先队列，元素按照自然顺序排序。
PriorityQueue(Comparator<? super E> comparator)：创建一个使用指定比较器的优先队列。
阻塞队列
BlockingQueue<Integer> blockingQueue = new ArrayBlockingQueue<>(2);
阻塞队列是一种特殊的队列，当队列为空时，从队列中取元素的操作会被阻塞，直到队列中有元素；当队列满时，向队列中添加元素的操作会被阻塞，直到队列中有空闲位置。Java 中提供了多种阻塞队列的实现，如ArrayBlockingQueue、LinkedBlockingQueue等。
插入过程：当向阻塞队列中添加元素时，根据队列的不同实现，元素会被添加到队列的末尾。例如，在 ArrayBlockingQueue中，元素会被添加到数组的相应位置；在LinkedBlockingQueue中，会创建一个新的节点并连接到链表尾部。对于无界队列(如LinkedBlockingQueue不指定容量时)，只要系统内存足够，插入操作通常可以立即完成。而对于有界队列(如ArrayBlockingQueue)，当队列已满时，插入操作会阻塞当前线程，直到队列中有空间可用。
阻塞机制：BlockingQueue提供了不同的插入方法来处理队列满的情况。put(E e)方法是一个阻塞方法，如果队列已满，它会让当前线程进入等待状态，直到队列有空间可以插入元素；offer(E e, long timeout, TimeUnit unit)方法允许设置一个超时时间，如果在指定时间内队列仍没有空间，插入操作会失败并返回false。插入操作本身在队列有空间时时间复杂度通常为O(1)。
移除元素：移除操作会从队列的头部取出元素。在ArrayBlockingQueue中，会移除数组头部的元素，并移动相应的索引；在LinkedBlockingQueue中，会移除链表的头节点。如果队列为空，不同的方法有不同的处理方式。
阻塞机制：take() 方法是一个阻塞方法，如果队列为空，它会让当前线程进入等待状态，直到队列中有元素可供移除；poll(long timeout, TimeUnit unit)方法允许设置一个超时时间，如果在指定时间内队列仍为空，移除操作会失败并返回null。移除操作在队列不为空时时间复杂度通常为O(1)。
元素访问：与普通队列类似，阻塞队列主要支持对队头元素的访问。peek()方法可以查看队头元素，但不移除它，如果队列为空则返回null。由于队列是按顺序存储元素的，不能直接通过索引随机访问队列中的元素。如果要查找队列中的特定元素，需要遍历队列，时间复杂度为O(n)。
阻塞队列的一个重要特性是支持多线程并发操作。它内部使用了锁和条件变量来保证线程安全。例如，在ArrayBlockingQueue中使用了ReentrantLock来控制对队列的访问，当一个线程进行插入或移除操作时，会获取锁，其他线程需要等待锁释放才能进行相应操作。这种并发控制机制确保了在多线程环境下队列操作的正确性和一致性。
阻塞队列相关方法
新增：
add(E e)：将指定的元素插入到此队列中(如果立即可行且不会违反容量限制)，成功时返回true。如果当前没有可用的空间，则抛出IllegalStateException。
offer(E e)：将指定的元素插入到此队列中(如果立即可行且不会违反容量限制)，成功时返回true。如果当前没有可用的空间，则返回false。
offer(E e, long timeout, TimeUnit unit)：将指定的元素插入此队列，如果队列已满，则在指定的等待时间内等待空间变得可用。如果在等待时间内空间可用，则插入元素并返回true；如果超时仍无空间，则返回false。
put(E e)：将指定的元素插入此队列，如果队列已满，则阻塞当前线程，直到队列有空间可用。移除元素：
remove()：移除并返回队列的头部元素。如果队列为空，则抛出NoSuchElementException。
poll()：移除并返回队列的头部元素。如果队列为空，则返回null。
poll(long timeout, TimeUnit unit)：移除并返回队列的头部元素。如果队列为空，则在指定的等待时间内等待元素变得可用。如果在等待时间内有元素可用，则移除并返回该元素；如果超时仍无元素，则返回null。
take()：移除并返回队列的头部元素。如果队列为空，则阻塞当前线程，直到队列中有元素可用。查看元素：
peek()：返回队列的头部元素，但不移除它。如果队列为空，则返回null。
双端队列
双端队列是一种允许在队列的两端进行插入和删除操作的数据结构。
Java中的双端队列实现：ArrayDeque与LinkedList。
双端队列相关方法
插入元素：
addFirst(E e)：将指定的元素插入此双端队列的开头。如果立即可行且不会违反容量限制，则插入元素；如果当前没有可用的空间，则抛出IllegalStateException。
addLast(E e)：将指定的元素插入此双端队列的末尾。如果立即可行且不会违反容量限制，则插入元素；如果当前没有可用的空间，则抛出IllegalStateException。
offerFirst(E e)：将指定的元素插入此双端队列的开头。如果立即可行且不会违反容量限制，则插入元素并返回 true；如果当前没有可用的空间，则返回false。
offerLast(E e)：将指定的元素插入此双端队列的末尾。如果立即可行且不会违反容量限制，则插入元素并返回 true；如果当前没有可用的空间，则返回false。移除元素：
removeFirst()：移除并返回此双端队列的第一个元素。如果双端队列为空，则抛出NoSuchElementException。
removeLast()：移除并返回此双端队列的最后一个元素。如果双端队列为空，则抛出 NoSuchElementException。
pollFirst()：移除并返回此双端队列的第一个元素。如果双端队列为空，则返回null。
pollLast()：移除并返回此双端队列的最后一个元素。如果双端队列为空，则返回null。查看元素：
getFirst()：返回此双端队列的第一个元素，但不移除它。如果双端队列为空，则抛出NoSuchElementException。
getLast()：返回此双端队列的最后一个元素，但不移除它。如果双端队列为空，则抛出NoSuchElementException。
peekFirst()：返回此双端队列的第一个元素，但不移除它。如果双端队列为空，则返回null。
peekLast()：返回此双端队列的最后一个元素，但不移除它。如果双端队列为空，则返回null。
