java的 queue

在 Java 中，Queue 是一个接口，属于 Java 集合框架的一部分，提供了队列的数据结构。队列遵循先进先出 (FIFO) 的顺序，最早添加的元素最先被移除。Java 中的 Queue 主要在 java.util 包中定义。

Queue 接口

Queue 接口扩展自 Collection 接口，包含了基本的队列操作方法。

public interface Queue<E> extends Collection<E> {boolean add(E e);boolean offer(E e);E remove();E poll();E element();E peek();
}

Queue 接口的主要方法

1. 添加元素
   • boolean add(E e): 将指定的元素插入此队列，如果成功返回 true，如果队列已满，则抛出 IllegalStateException。
   • boolean offer(E e): 将指定的元素插入此队列，如果成功返回 true，如果队列已满，则返回 false。
2. 移除元素
   • E remove(): 移除并返回此队列的头部，如果队列为空，则抛出 NoSuchElementException。
   • E poll(): 移除并返回此队列的头部，如果队列为空，则返回 null。
3. 查看元素
   • E element(): 获取但不移除此队列的头部，如果队列为空，则抛出 NoSuchElementException。
   • E peek(): 获取但不移除此队列的头部，如果队列为空，则返回 null。

常用的 Queue 实现类

1. LinkedList
   LinkedList 是一个双向链表，可以用作队列实现。
   Queue queue = new LinkedList<>();
   queue.offer(1);
   queue.offer(2);
   queue.offer(3);
   System.out.println(queue.poll()); // 输出 1
2. PriorityQueue
   PriorityQueue 是一个基于优先级堆的队列，元素按自然顺序或指定的比较器顺序排列。
   Queue queue = new PriorityQueue<>();
   queue.offer(3);
   queue.offer(1);
   queue.offer(2);
   System.out.println(queue.poll()); // 输出 1
3. ArrayDeque
   ArrayDeque 是一个基于数组的双端队列，可以用作栈和队列。
   Queue queue = new ArrayDeque<>();
   queue.offer(1);
   queue.offer(2);
   queue.offer(3);
   System.out.println(queue.poll()); // 输出 1

阻塞队列

在 java.util.concurrent 包中，有几种特殊的队列实现，这些队列支持阻塞操作。

1. ArrayBlockingQueue
   一个由数组支持的有界阻塞队列。
   BlockingQueue queue = new ArrayBlockingQueue<>(10);
   queue.put(1); // 如果队列满，则等待
   System.out.println(queue.take()); // 如果队列为空，则等待

2. LinkedBlockingQueue
   一个由链表支持的可选有界阻塞队列。
   BlockingQueue queue = new LinkedBlockingQueue<>();
   queue.put(1);
   System.out.println(queue.take());

3. PriorityBlockingQueue
   一个支持优先级排序的无界阻塞队列。
   BlockingQueue queue = new PriorityBlockingQueue<>();
   queue.put(3);
   queue.put(1);
   queue.put(2);
   System.out.println(queue.take()); // 输出 1

4. DelayQueue
   一个使用优先级队列实现的无界阻塞队列，其中的元素只有在其延迟期满时才能被获取。
   import java.util.concurrent.BlockingQueue;
   import java.util.concurrent.DelayQueue;
   import java.util.concurrent.Delayed;
   import java.util.concurrent.TimeUnit;

   class DelayedElement implements Delayed {private final long delayTime;private final long expire;private final String data;public DelayedElement(long delay, String data) {this.delayTime = delay;this.data = data;this.expire = System.currentTimeMillis() + delay;}@Overridepublic long getDelay(TimeUnit unit) {long diff = expire - System.currentTimeMillis();return unit.convert(diff, TimeUnit.MILLISECONDS);}@Overridepublic int compareTo(Delayed o) {if (this.expire < ((DelayedElement) o).expire) {return -1;}if (this.expire > ((DelayedElement) o).expire) {return 1;}return 0;}public String getData() {return data;}public static void main(String[] args) throws InterruptedException {BlockingQueue<DelayedElement> queue = new DelayQueue<>();queue.put(new DelayedElement(5000, "Delayed message"));System.out.println(queue.take().getData()); // 输出 "Delayed message" 经过 5 秒延迟}
   }
   

Deque

Deque（双端队列）接口扩展了 Queue 接口，允许在两端进行插入和移除操作。常用的实现类包括 ArrayDeque 和 LinkedList。

Deque 接口的主要方法

1. 在两端添加元素
   • void addFirst(E e): 在队列的开头插入指定的元素。
   • void addLast(E e): 在队列的末尾插入指定的元素。
   • boolean offerFirst(E e): 在队列的开头插入指定的元素（非阻塞）。
   • boolean offerLast(E e): 在队列的末尾插入指定的元素（非阻塞）。
2. 在两端移除元素
   • E removeFirst(): 移除并返回队列的第一个元素。
   • E removeLast(): 移除并返回队列的最后一个元素。
   • E pollFirst(): 移除并返回队列的第一个元素，若队列为空则返回 null。
   • E pollLast(): 移除并返回队列的最后一个元素，若队列为空则返回 null。
3. 在两端查看元素
   • E getFirst(): 获取但不移除队列的第一个元素。
   • E getLast(): 获取但不移除队列的最后一个元素。
   • E peekFirst(): 获取但不移除队列的第一个元素，若队列为空则返回 null。
   • E peekLast(): 获取但不移除队列的最后一个元素，若队列为空则返回 null。

使用 ArrayDeque 实现一个双端队列：

Deque<Integer> deque = new ArrayDeque<>();
deque.addFirst(1);
deque.addLast(2);
deque.addFirst(3);System.out.println(deque.removeLast()); // 输出 2
System.out.println(deque.removeFirst()); // 输出 3

ConcurrentLinkedQueue

ConcurrentLinkedQueue 是一个基于链接节点的无界线程安全队列。它采用无锁算法来实现高效并发访问，适合高并发环境下的使用。

Queue<Integer> queue = new ConcurrentLinkedQueue<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);System.out.println(queue.poll()); // 输出 1
System.out.println(queue.poll()); // 输出 2

阻塞队列与生产者-消费者模式

阻塞队列通常用于实现生产者-消费者模式。在这种模式中，生产者线程向队列中添加元素，而消费者线程从队列中取出元素。使用 LinkedBlockingQueue 实现生产者-消费者模式：

import java.util.concurrent.*;class Producer implements Runnable {private final BlockingQueue<Integer> queue;Producer(BlockingQueue<Integer> queue) {this.queue = queue;}@Overridepublic void run() {try {for (int i = 0; i < 10; i++) {queue.put(i);System.out.println("Produced: " + i);}queue.put(-1); // 结束标记} catch (InterruptedException e) {Thread.currentThread().interrupt();}}
}class Consumer implements Runnable {private final BlockingQueue<Integer> queue;Consumer(BlockingQueue<Integer> queue) {this.queue = queue;}@Overridepublic void run() {try {while (true) {Integer value = queue.take();if (value == -1) { // 结束标记break;}System.out.println("Consumed: " + value);}} catch (InterruptedException e) {Thread.currentThread().interrupt();}}
}public class ProducerConsumerExample {public static void main(String[] args) {BlockingQueue<Integer> queue = new LinkedBlockingQueue<>(10);Thread producerThread = new Thread(new Producer(queue));Thread consumerThread = new Thread(new Consumer(queue));producerThread.start();consumerThread.start();}
}