1. 简介

队列（Queue）是一种常用的数据结构，它遵循先进先出（FIFO，First In First Out）的原则。这意味着第一个进入队列的元素将是第一个被移除的元素。队列在计算机科学中有着广泛的应用，比如任务调度、缓冲处理、广度优先搜索算法等。

队列的基本操作通常包括：

1. 入队（Enqueue）：在队列的末尾添加一个元素。

2. 出队（Dequeue）：移除队列的第一个元素。

3. 查看队首（Front）：获取队列第一个元素的值，但不移除它。

4. 查看队尾（Rear）：获取队列最后一个元素的值，但不移除它。

5. 检查是否为空（IsEmpty）：判断队列是否为空。

6. 检查长度（Size）：获取队列中元素的数量。

        队列可以用数组或链表来实现。使用数组实现的队列在入队和出队时可能需要移动元素，这可能导致较高的时间复杂度。而使用链表实现的队列则可以更高效地进行这些操作，因为它们不需要移动元素，只需要改变指针。

2. 分类

2.1 普通队列

普通队列遵循先进先出（FIFO）的原则。

基于数组实现

class ArrayQueue {private int[] arr;private int front;private int rear;private int size;// 队列的构造函数public ArrayQueue(int capacity) {arr = new int[capacity];front = 0;rear = -1;size = 0;}// 判断队列是否为空public boolean isEmpty() {return size == 0;}// 判断队列是否满public boolean isFull() {return size == arr.length;}// 入队操作public void enqueue(int value) {if (isFull()) {System.out.println("队列已满，无法入队");return;}rear = (rear + 1) % arr.length; // 循环队列arr[rear] = value;size++;}// 出队操作public int dequeue() {if (isEmpty()) {System.out.println("队列为空，无法出队");return -1; // 或者抛出异常}int value = arr[front];front = (front + 1) % arr.length; // 循环队列size--;return value;}// 获取队列的大小public int getSize() {return size;}// 获取队列头元素public int peek() {if (isEmpty()) {System.out.println("队列为空");return -1; // 或者抛出异常}return arr[front];}
}public class Main {public static void main(String[] args) {ArrayQueue queue = new ArrayQueue(5);queue.enqueue(10);queue.enqueue(20);queue.enqueue(30);System.out.println(queue.dequeue()); // 输出 10System.out.println(queue.peek());    // 输出 20}
}

基于链表实现

class Node {int data;Node next;public Node(int data) {this.data = data;this.next = null;}
}class LinkedListQueue {private Node front;private Node rear;private int size;// 队列的构造函数public LinkedListQueue() {front = null;rear = null;size = 0;}// 判断队列是否为空public boolean isEmpty() {return front == null;}// 入队操作public void enqueue(int value) {Node newNode = new Node(value);if (isEmpty()) {front = newNode;rear = newNode;} else {rear.next = newNode;rear = newNode;}size++;}// 出队操作public int dequeue() {if (isEmpty()) {System.out.println("队列为空，无法出队");return -1; // 或者抛出异常}int value = front.data;front = front.next;size--;return value;}// 获取队列的大小public int getSize() {return size;}// 获取队列头元素public int peek() {if (isEmpty()) {System.out.println("队列为空");return -1; // 或者抛出异常}return front.data;}
}public class Main {public static void main(String[] args) {LinkedListQueue queue = new LinkedListQueue();queue.enqueue(10);queue.enqueue(20);queue.enqueue(30);System.out.println(queue.dequeue()); // 输出 10System.out.println(queue.peek());    // 输出 20}
}

总结

基于数组实现：使用循环数组来实现队列，最大优点是访问速度快，缺点是容量固定（需要预先指定大小），并且队列满时无法自动扩展。

基于链表实现：使用链表来实现队列，最大优点是队列大小可以动态调整，不需要预先指定大小，缺点是访问速度较慢，因为需要频繁地操作指针。

2.2 循环队列

循环队列（Circular Queue）是一种使用固定大小数组实现的队列，在这种队列中，当元素达到数组的末尾时会循环回到数组的开始位置。这种循环利用可以更有效地使用数组空间，避免在队列达到数组末尾时需要重新分配空间的问题。

循环队列的特点：

1. 固定大小：循环队列有一个固定的大小，这意味着一旦创建，其容量就确定了。

2. 循环利用空间：当队列的尾部到达数组的末尾时，下一个元素会被添加到数组的开始位置。

3. 两个指针：通常需要两个指针（或索引）来标识队列的头部和尾部。一个指向队列的第一个有效元素（头指针），另一个指向队列的最后一个有效元素的下一个位置（尾指针）。

循环队列的操作：

1. 入队（Enqueue）：

   1. 检查队列是否已满。如果尾指针的下一个位置是头指针，说明队列已满。

   2. 将新元素添加到尾指针的位置。

   3. 尾指针向前移动一位（如果到达数组末尾，回到数组的开始位置）。

2. 出队（Dequeue）：

   1. 检查队列是否为空。如果头指针和尾指针相等，说明队列空。

   2. 移除头指针指向的元素。

   3. 头指针向前移动一位（如果到达数组末尾，回到数组的开始位置）。

3. 查看队首（Front）：

   1. 返回头指针指向的元素。

4. 查看队尾（Rear）：

   1. 返回尾指针指向的前一个位置的元素。

5. 检查是否为空（IsEmpty）：

   1. 如果头指针等于尾指针，队列为空。

6. 检查是否已满（IsFull）：

   1. 如果尾指针的下一个位置是头指针，队列满。

基于数组实现

class CircularArrayQueue {private int[] arr;private int front;private int rear;private int size;private int capacity;// 队列的构造函数public CircularArrayQueue(int capacity) {this.capacity = capacity;arr = new int[capacity];front = 0;rear = 0;size = 0;}// 判断队列是否为空public boolean isEmpty() {return size == 0;}// 判断队列是否满public boolean isFull() {return size == capacity;}// 入队操作public void enqueue(int value) {if (isFull()) {System.out.println("队列已满，无法入队");return;}arr[rear] = value;rear = (rear + 1) % capacity; // 循环操作size++;}// 出队操作public int dequeue() {if (isEmpty()) {System.out.println("队列为空，无法出队");return -1; // 或者抛出异常}int value = arr[front];front = (front + 1) % capacity; // 循环操作size--;return value;}// 获取队列的大小public int getSize() {return size;}// 获取队列头元素public int peek() {if (isEmpty()) {System.out.println("队列为空");return -1; // 或者抛出异常}return arr[front];}
}public class Main {public static void main(String[] args) {CircularArrayQueue queue = new CircularArrayQueue(5);queue.enqueue(10);queue.enqueue(20);queue.enqueue(30);System.out.println(queue.dequeue()); // 输出 10queue.enqueue(40);System.out.println(queue.peek());    // 输出 20}
}

基于链表实现

对于基于链表的循环队列，链表本身不需要固定的大小，因此可以动态地增加和删除元素。链表的尾节点指向头节点，从而形成一个环。

class Node {int data;Node next;public Node(int data) {this.data = data;this.next = null;}
}class CircularLinkedListQueue {private Node front;private Node rear;private int size;// 队列的构造函数public CircularLinkedListQueue() {front = null;rear = null;size = 0;}// 判断队列是否为空public boolean isEmpty() {return size == 0;}// 入队操作public void enqueue(int value) {Node newNode = new Node(value);if (isEmpty()) {front = newNode;rear = newNode;rear.next = front;  // 尾节点指向头节点，形成循环} else {rear.next = newNode;rear = newNode;rear.next = front;  // 尾节点指向头节点，保持循环}size++;}// 出队操作public int dequeue() {if (isEmpty()) {System.out.println("队列为空，无法出队");return -1; // 或者抛出异常}int value = front.data;if (front == rear) {front = null;rear = null;  // 队列只有一个元素时，出队后队列为空} else {front = front.next;rear.next = front;  // 保持尾节点指向新的头节点}size--;return value;}// 获取队列的大小public int getSize() {return size;}// 获取队列头元素public int peek() {if (isEmpty()) {System.out.println("队列为空");return -1; // 或者抛出异常}return front.data;}
}public class Main {public static void main(String[] args) {CircularLinkedListQueue queue = new CircularLinkedListQueue();queue.enqueue(10);queue.enqueue(20);queue.enqueue(30);System.out.println(queue.dequeue()); // 输出 10queue.enqueue(40);System.out.println(queue.peek());    // 输出 20}
}

关键点

1. 基于数组的循环队列：通过计算rear和front的索引来进行循环，使用% capacity操作来确保数组的索引不越界，实现环形存储。

2. 基于链表的循环队列：链表的尾节点指向头节点，形成环形结构。每次入队时更新尾节点的next指向新的节点，出队时更新头节点。

总结

• 基于数组实现的循环队列：使用循环数组来实现队列，可以避免队列头部出队后空间浪费的问题。容量是固定的，不支持动态扩展。

• 基于链表实现的循环队列：通过链表的尾节点指向头节点实现循环队列，大小动态变化，但需要额外的内存来存储节点指针。

2.3 双端队列

双端队列（Deque，全称 Double-Ended Queue）是一种具有队列和栈特性的数据结构，它允许我们在两端进行添加和移除操作。这意味着你可以在双端队列的前端（front）和后端（rear）进行入队（enqueue）和出队（dequeue）操作。

双端队列的特点：

1. 两端操作：支持在前端和后端进行入队和出队操作。

2. 灵活性：由于可以在两端进行操作，双端队列比单纯的队列或栈更加灵活。

3. 应用广泛：常用于需要从两端进行操作的场景，如括号匹配、表达式求值等。

双端队列的基本操作：

1. 入队（Enqueue）：

   1. 在后端添加一个元素。

2. 入队前端（EnqueueFront）：

   1. 在前端添加一个元素。

3. 出队（Dequeue）：

   1. 移除后端的元素，并返回它。

4. 出队前端（DequeueFront）：

   1. 移除前端的元素，并返回它。

5. 查看前端（Front）：

   1. 返回前端的元素，但不移除。

6. 查看后端（Rear）：

   1. 返回后端的元素，但不移除。

7. 检查是否为空（IsEmpty）：

   1. 如果队列为空，返回 true。

8. 检查长度（Size）：

   1. 返回队列中的元素数量。

基于数组实现：

需要在数组的两端进行操作，并且需要动态调整队列的大小以避免溢出。

class ArrayDeque {private int[] arr;private int front;private int rear;private int size;private int capacity;// 队列的构造函数public ArrayDeque(int capacity) {this.capacity = capacity;arr = new int[capacity];front = -1;rear = -1;size = 0;}// 判断队列是否为空public boolean isEmpty() {return size == 0;}// 判断队列是否满public boolean isFull() {return size == capacity;}// 在队头插入元素public void insertFront(int value) {if (isFull()) {System.out.println("队列已满，无法在队头插入");return;}if (front == -1) {front = 0;rear = 0;} else {front = (front - 1 + capacity) % capacity; // 循环队列}arr[front] = value;size++;}// 在队尾插入元素public void insertRear(int value) {if (isFull()) {System.out.println("队列已满，无法在队尾插入");return;}if (rear == -1) {front = 0;rear = 0;} else {rear = (rear + 1) % capacity; // 循环队列}arr[rear] = value;size++;}// 从队头删除元素public int deleteFront() {if (isEmpty()) {System.out.println("队列为空，无法从队头删除");return -1; // 或者抛出异常}int value = arr[front];if (front == rear) {front = -1;rear = -1; // 队列为空} else {front = (front + 1) % capacity; // 循环队列}size--;return value;}// 从队尾删除元素public int deleteRear() {if (isEmpty()) {System.out.println("队列为空，无法从队尾删除");return -1; // 或者抛出异常}int value = arr[rear];if (front == rear) {front = -1;rear = -1; // 队列为空} else {rear = (rear - 1 + capacity) % capacity; // 循环队列}size--;return value;}// 获取队列的大小public int getSize() {return size;}// 获取队头元素public int getFront() {if (isEmpty()) {System.out.println("队列为空");return -1; // 或者抛出异常}return arr[front];}// 获取队尾元素public int getRear() {if (isEmpty()) {System.out.println("队列为空");return -1; // 或者抛出异常}return arr[rear];}
}public class Main {public static void main(String[] args) {ArrayDeque deque = new ArrayDeque(5);deque.insertRear(10);deque.insertRear(20);deque.insertFront(5);System.out.println(deque.getFront());  // 输出 5System.out.println(deque.getRear());   // 输出 20deque.deleteFront();  // 删除 5deque.deleteRear();   // 删除 20System.out.println(deque.getFront());  // 输出 10}
}

基于链表实现：

基于链表的双端队列可以动态扩展，并且在两端进行操作时，只需要修改头节点或尾节点的指针。

class Node {int data;Node prev;Node next;public Node(int data) {this.data = data;this.prev = null;this.next = null;}
}class LinkedListDeque {private Node front;private Node rear;private int size;// 队列的构造函数public LinkedListDeque() {front = null;rear = null;size = 0;}// 判断队列是否为空public boolean isEmpty() {return size == 0;}// 在队头插入元素public void insertFront(int value) {Node newNode = new Node(value);if (isEmpty()) {front = newNode;rear = newNode;} else {newNode.next = front;front.prev = newNode;front = newNode;}size++;}// 在队尾插入元素public void insertRear(int value) {Node newNode = new Node(value);if (isEmpty()) {front = newNode;rear = newNode;} else {newNode.prev = rear;rear.next = newNode;rear = newNode;}size++;}// 从队头删除元素public int deleteFront() {if (isEmpty()) {System.out.println("队列为空，无法从队头删除");return -1; // 或者抛出异常}int value = front.data;if (front == rear) {front = null;rear = null; // 队列为空} else {front = front.next;front.prev = null;}size--;return value;}// 从队尾删除元素public int deleteRear() {if (isEmpty()) {System.out.println("队列为空，无法从队尾删除");return -1; // 或者抛出异常}int value = rear.data;if (front == rear) {front = null;rear = null; // 队列为空} else {rear = rear.prev;rear.next = null;}size--;return value;}// 获取队列的大小public int getSize() {return size;}// 获取队头元素public int getFront() {if (isEmpty()) {System.out.println("队列为空");return -1; // 或者抛出异常}return front.data;}// 获取队尾元素public int getRear() {if (isEmpty()) {System.out.println("队列为空");return -1; // 或者抛出异常}return rear.data;}
}public class Main {public static void main(String[] args) {LinkedListDeque deque = new LinkedListDeque();deque.insertRear(10);deque.insertRear(20);deque.insertFront(5);System.out.println(deque.getFront());  // 输出 5System.out.println(deque.getRear());   // 输出 20deque.deleteFront();  // 删除 5deque.deleteRear();   // 删除 20System.out.println(deque.getFront());  // 输出 10}
}

关键点

• 基于数组实现的双端队列：利用循环数组来管理队列，前后两个指针分别指向队头和队尾，可以在两端进行插入和删除。队列满时，需要扩展数组或者抛出溢出异常。

• 基于链表实现的双端队列：链表的头节点和尾节点分别对应队列的两端，插入和删除操作仅需要修改指针，队列的大小是动态的，不需要担心空间溢出。

总结

• 基于数组的双端队列：对于队列大小固定或不需要频繁扩展的情况，基于数组的实现效率较高。

• 基于链表的双端队列：链表实现可以动态调整大小，不受容量限制，但需要额外的内存来存储节点的前后指针，性能上比数组稍慢。

3. Java中的队列

3.1 阻塞队列（BlockingQueue）

阻塞队列 是一种线程安全的队列，它用于多线程环境中的生产者-消费者模式。其主要特点是：当队列为空时，消费者线程会被阻塞；当队列满时，生产者线程会被阻塞。BlockingQueue 提供了多种操作，可以处理线程的等待和唤醒机制。

主要特点

• 线程安全。

• 支持阻塞操作。

• 可用于生产者-消费者模型。

• 提供了如 put()、take()、offer() 和 poll() 等方法来处理线程阻塞。

常见实现

• ArrayBlockingQueue：基于数组实现的有界队列，大小固定。

• LinkedBlockingQueue：基于链表实现的阻塞队列，支持有界和无界队列。

• PriorityBlockingQueue：优先级队列的阻塞实现，无界。

• DelayQueue：一个特殊类型的阻塞队列，用于处理延迟任务。

---

3.2 优先队列（PriorityQueue）

优先队列 是一种根据元素的优先级顺序来存取元素的队列。底层使用了堆（通常是最小堆），它不像传统的队列那样按插入顺序处理元素，而是根据元素的优先级顺序进行排序。PriorityQueue 默认使用自然顺序（Comparable 接口），但也可以通过传入自定义的 Comparator 来指定元素的优先级。

主要特点

• 按优先级排序：队列中的元素按优先级进行排序，队头元素是优先级最高的元素。

• 不阻塞：PriorityQueue 不支持阻塞操作，适用于普通的队列处理。

• 无界队列：默认情况下，PriorityQueue 是无界的，可以存储任意数量的元素，直到内存耗尽。

常见用法

• 适用于任务调度、A* 算法等需要优先级排序的场景。

public class PriorityQueue<E> extends AbstractQueue<E>implements Queue<E>, Serializable {private transient Object[] queue;private int size;// 向队列尾部插入元素，并重新排序public boolean offer(E e) {// 如果队列已满，扩容ensureCapacity(size + 1);// 插入新元素并进行堆化siftUp(size, e);size++;return true;}// 从队列头部移除元素（即堆顶元素）public E poll() {if (size == 0) {return null;}E result = (E) queue[0];E x = (E) queue[--size];queue[size] = null;if (size > 0) {siftDown(0, x);  // 重新堆化}return result;}// 查看队头元素（堆顶元素）public E peek() {return (size == 0) ? null : (E) queue[0];}// 向上堆化private void siftUp(int k, E e) {while (k > 0) {int parent = (k - 1) >>> 1;Object parentVal = queue[parent];if (((Comparable<? super E>) e).compareTo((E) parentVal) >= 0) {break;}queue[k] = parentVal;k = parent;}queue[k] = e;}// 向下堆化private void siftDown(int k, E e) {int half = size >>> 1;  // size/2while (k < half) {int leftChild = (k << 1) + 1;int rightChild = leftChild + 1;Object leftVal = queue[leftChild];Object rightVal = (rightChild < size) ? queue[rightChild] : null;int minChild = (rightChild < size && ((Comparable<? super E>) leftVal).compareTo((E) rightVal) > 0)? rightChild : leftChild;if (((Comparable<? super E>) e).compareTo((E) queue[minChild]) <= 0) {break;}queue[k] = queue[minChild];k = minChild;}queue[k] = e;}
}

---

1. 延迟队列（DelayQueue）

延迟队列 是一种特殊的队列,基于优先队列，元素在队列中存放一定的延迟时间，直到该元素“到期”时才会被移除。延迟队列通常用于需要按指定时间延迟执行的任务，比如定时任务、延迟消息等。DelayQueue 只能存储实现了 Delayed 接口的元素。

主要特点

• 元素按延迟时间排序：延迟队列中的元素会根据它们的延迟时间进行排序，最早到期的元素排在队列头部。

• 阻塞操作：take() 方法会阻塞当前线程，直到有元素到期且可以被移除。

• 无界队列：DelayQueue 默认是无界的，直到内存不足。

常见实现

• DelayQueue：本身就是延迟队列的实现，元素必须实现 Delayed 接口。

public class DelayQueue<E extends Delayed> extends AbstractQueue<E>implements BlockingQueue<E>, java.io.Serializable {private final PriorityQueue<DelayedElement> queue;public DelayQueue() {queue = new PriorityQueue<>();}// 插入元素public boolean offer(E e) {if (e == null) throw new NullPointerException();return queue.offer(new DelayedElement(e));}// 获取并移除队头元素（即最早到期的元素）public E poll() {return extract();}// 获取队头元素（即最早到期的元素），不移除public E peek() {DelayedElement first = queue.peek();return (first == null || first.getDelay(TimeUnit.MILLISECONDS) > 0) ? null : first.getElement();}// 阻塞式获取元素（只有元素到期后才能取出）public E take() throws InterruptedException {DelayedElement first;while ((first = queue.peek()) != null && first.getDelay(TimeUnit.MILLISECONDS) > 0) {synchronized (this) {wait(first.getDelay(TimeUnit.MILLISECONDS));}}return extract();}// 提取队头元素private E extract() {DelayedElement first = queue.poll();return (first == null) ? null : first.getElement();}// 延迟队列中的元素类private static class DelayedElement<E> implements Delayed {private final E element;private final long expirationTime;DelayedElement(E element) {this.element = element;this.expirationTime = System.nanoTime() + 1000000000L;  // 设置延迟为1秒}public E getElement() {return element;}public long getDelay(TimeUnit unit) {long remainingDelay = expirationTime - System.nanoTime();return unit.convert(remainingDelay, TimeUnit.NANOSECONDS);}public int compareTo(Delayed o) {if (this.expirationTime < ((DelayedElement<?>) o).expirationTime) {return -1;}if (this.expirationTime > ((DelayedElement<?>) o).expirationTime) {return 1;}return 0;}}
}

---

3.4 对比总结

特性	阻塞队列 (BlockingQueue)	优先队列 (PriorityQueue)	延迟队列 (DelayQueue)
线程安全	是	否（除非手动加锁）	是
元素顺序	按插入顺序（FIFO）	按优先级排序（高优先级在前）	按延迟时间排序（早到期在前）
阻塞行为	支持阻塞（put() 和 take()）	不支持阻塞操作	支持阻塞（take()，直到元素到期）
容量限制	可设置为有界或无界	无界	无界
适用场景	生产者-消费者模型，线程间协调	需要优先级排序的任务处理	延迟任务调度，定时任务

---

3.5 适用场景

• 阻塞队列：适用于生产者-消费者模式，尤其在多线程并发环境下，用于处理线程间的协调和同步。

• 优先队列：适用于任务调度系统、A* 搜索算法等需要按优先级处理元素的场景。

• 延迟队列：适用于定时任务、延迟消息、缓存过期策略等场景，元素只有到期后才能被取出。

不积跬步，无以至千里 --- xiaokai