队列

队列定义

队列（Queue）是一种先进先出（FIFO）的线性数据结构，它有两个主要操作：

入队（Enqueue）：将元素添加到队列的尾部
出队（Dequeue）：从队列的头部移除元素

队列的特点；先进入队列的元素会被先移除，遵循先进先出原则

队列的特性

先进先出（FIFO）：最先进入队列的元素会最先被溢出
操作受限：
- 只能在队尾插入元素（入队）
- 只能在对头移除元素（出队）
动态大小：队列的大小可以动态增长（除非是有界队列）
不允许随机访问：不能直接访问队列中间的元素

队列的基本操作

入队（Enqueue）：
1. 将元素添加到队列的尾部
2. 如果队列已满（有界队列），可能会抛出异常或返回错误
出队（Dequeue）：
1. 移除并返回队列的头部元素
2. 如果队列为空，可能会抛出异常或返回特殊值（null）
查看队头元素（peek）：
1. 返回队列的头部元素，但不移除它
2. 如果队列为空，可能会抛出异常或返回特殊值
判断队列是否为空（isEmpty）：
1. 检查队列是否为空
获取队列大小（Size）
1. 返回队列中元素的数量

队列的实现方式

队列可以通过多种方式实现，常见的有以下两种：

(1) 基于数组的实现

特点：
- 使用数组存储元素。
- 需要维护队头和队尾的指针。
- 可以是 有界队列（固定大小）或 动态扩容队列。
优点：
- 内存连续，访问速度快。
缺点：
- 需要处理数组的扩容问题。
- 如果是有界队列，可能会浪费空间。

循环队列

为了解决数组实现的队列在出队后空间浪费的问题，可以使用 循环队列。
循环队列通过模运算将队尾指针“绕回”数组开头，充分利用数组空间。

(2) 基于链表的实现

特点：
- 使用链表存储元素。
- 需要维护队头和队尾的指针。
优点：
- 动态扩容，无需担心空间浪费。
- 实现简单。
缺点：
- 内存不连续，访问速度较慢。

队列的常见变种

双端队列（Deque）

概念：双端队列是一种允许在队头和队尾进行插入和删除操作的队列。它既可以用作队列，也可以用作栈
底层实现：

Deque接口的两个常见实现类：
- ArrayDeque:
  - 基于动态数组实现
  - 使用循环数组来高效地支持队头和队尾的操作
  - 默认初始容量为16，当数组满时会自动扩容（通常是当前容量的两倍）
  - 优点：内存连续，访问速度快
  - 缺点：扩容时需要复制数据
- Linked List：
  - 基于双向链表实现
  - 每个节点包含前驱和后继指针，支持在队头和队尾的高效操作
  - 优点：动态扩容，不用担心空间浪费
  - 缺点：内存不连续，访问速度较慢
核心操作：
- 队头操作：
  - offerFirst（E e）：在队头插入元素
  - pollFirst（）：移除并返回队头元素
  - peekFirst（）：返回队头元素，但不移除
- 队尾操作：
  - offerLast（E e）：在队尾插入元素
  - pollLast（）：移除并返回队尾元素
  - peekLast（）：返回队尾元素，但不移除

优先级队列（Priority Queue）

概念：优先级队列是一种按优先级排序的队列，优先级高的元素先出队。默认情况下，优先级队列是小顶堆（最小元素在队头），但可以通过Comparator自定义排序规则
底层实现：
- 基于堆（Heap）实现：
  - 优先级队列使用二叉堆（Binary Heap）实现
  - 二叉堆是一种完全二叉树，分为小顶堆和大顶堆
    - 小顶堆：每个节点的值都小于或等于其子节点的值
    - 大顶堆：每个节点的值都大于或等于其子节点的值
  - 堆的插入和删除擦欧总的时间复杂度为O(log n)
- 动态数组：
  - 优先级队列使用动态数组存储堆中的元素
  - 当数组满时，会自动扩容（通常是当前容量的1.5倍）
核心操作：
- offer(E e)：将元素插入队列，并调整堆结构
- poll()：移除并返回队头元素（优先级最高的元素），并调整堆结构
- peek()：返回队头元素，但不移除

阻塞队列（BlockingQueue）

概念：阻塞队列是一种支持阻塞操作的队列。当队列为空时，出队操作会被阻塞，知道队列中有元素；当队列已满时，入队操作会被阻塞，知道队列有空闲空间
底层实现：

BlockingQueue接口的4个常见实现类：
- ArrayBlockingQueue：
  - 基于数组实现的有界阻塞队列。
  - 使用一个锁（ReentrantLock）和两个条件变量（notEmpty 和 notFull）来实现阻塞操作。
  - 优点：内存连续，访问速度快。
  - 缺点：固定大小，无法动态扩容。
- LinkedBlockingQueue：
  - 基于链表实现的可选有界阻塞队列。
  - 使用两个锁（putLock 和 takeLock）来提高并发性能。
  - 优点：动态扩容，性能较高。
  - 缺点：内存不连续，访问速度较慢。
- SynchronousQueue：
  - 一种不存储元素的阻塞队列。
  - 每个插入操作必须等待一个移除操作，反之亦然。
  - 适用场景：用于直接传递任务的场景。
- PriorityBlockingQueue：
  - 基于堆实现的无界阻塞队列。
  - 支持按优先级排序。
  - 优点：动态扩容，支持优先级。
核心操作：
- 插入元素：
  - put(E e)：将元素插入队列，如果队列已满则阻塞。
  - offer(E e, long timeout, TimeUnit unit)：将元素插入队列，如果队列已满则等待指定的时间。
- 移除元素：
  - take()：移除并返回队头元素，如果队列为空则阻塞。
  - poll(long timeout, TimeUnit unit)：移除并返回队头元素，如果队列为空则等待指定的时间。

延迟队列（DelayQueue）

概述：延迟队列（DelayQueue）是一种存储延迟元素的队列。元素只有在指定的延迟时间到达后才能出队。
底层实现：
- 基于优先级队列：
  - 延迟队列内部使用 PriorityQueue 来存储元素。
  - 元素必须实现 Delayed 接口，该接口定义了 getDelay() 方法，用于获取剩余延迟时间。
- 阻塞操作：
  - 当队列为空时，出队操作会被阻塞。
  - 当队头元素的延迟时间未到达时，出队操作也会被阻塞。

核心操作
- 插入元素：
  - offer(E e)：将元素插入队列。
- 移除元素：
  - take()：移除并返回队头元素，如果延迟时间未到达则阻塞。
  - poll(long timeout, TimeUnit unit)：移除并返回队头元素，如果延迟时间未到达则等待指定的时间。