引言
Java中的Queue是一种非常常用且重要的数据结构，在各种场合都有着广泛的应用。它既可以实现先进先出的队列结构，也可以实现后进先出的栈结构。在多线程环境下，它还可以实现并发访问控制。因此，深入理解Java Queue既可以让我们更好地理解Java的数据结构，也可以让我们在实现某些功能时更加得心应手。本文将从多个方面对Java Queue进行详细的阐述。
Java Queue的分类
Java中的Queue有多种实现方式，其中常见的有以下三种：
1. LinkedList实现Queue
import java.util.LinkedList;
import java.util.Queue;
public class LinkedListQueueExample {
public static void main(String[] args) {
Queue<String> queue = new LinkedList<>();
queue.add("A");
queue.add("B");
queue.add("C");
String s;
while((s = queue.poll()) != null) {
System.out.println(s);
}
}
}
这个实现方式使用LinkedList来实现Queue，它是一种基于双向链表的通用集合类。队列中元素的增删很方便，但查询效率不高。如果需要对队列中所有元素进行遍历，那么应该考虑使用其他实现方式。
2. PriorityQueue实现Queue
import java.util.PriorityQueue;
import java.util.Queue;
public class PriorityQueueExample {
public static void main(String[] args) {
Queue<Integer> queue = new PriorityQueue<>();
queue.add(3);
queue.add(1);
queue.add(2);
while(!queue.isEmpty()) {
System.out.println(queue.poll());
}
}
}
这个实现方式使用PriorityQueue来实现Queue，它是一个基于优先级堆的无界优先级队列。因为基于堆实现，所以查询效率很高。但是它不是线程安全的，不能用于多线程环境中。
3. ArrayBlockingQueue实现Queue
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;
public class ArrayBlockingQueueExample {
public static void main(String[] args) {
BlockingQueue<String> queue = new ArrayBlockingQueue<>(2);
queue.add("A");
queue.add("B");
queue.add("C"); //抛出异常，因为队列已满
String s;
while((s = queue.poll()) != null) {
System.out.println(s);
}
}
}
这个实现方式使用ArrayBlockingQueue来实现Queue，它是一个基于数组结构的线程安全的有界阻塞队列，当队列中元素满了或空了时，它会阻塞插入或取出操作，直到有空间或有元素插入为止。
Java Queue的基本操作
1. enqueue – 将元素插入队列尾部
在Java中，向队列中添加元素使用的是offer()方法。如果元素插入成功，则返回true；否则返回false。它的示例代码如下：
Queue<String> queue = new LinkedList<>();
queue.offer("A");
queue.offer("B");
queue.offer("C");
2. dequeue – 取出队列头部元素
在Java中，从队列中取出元素使用的是poll()方法。它会返回队列头部的元素，如果队列为空，则返回null。它的示例代码如下：
Queue<String> queue = new LinkedList<>();
queue.offer("A");
queue.offer("B");
queue.offer("C");
String s = queue.poll(); // s = "A"
3. 获取队头元素
在Java中，获取队头元素使用的是peek()方法。它会返回队头元素，但不会从队列中删除它。如果队列为空，则返回null。它的示例代码如下：
Queue<String> queue = new LinkedList<>();
queue.offer("A");
queue.offer("B");
queue.offer("C");
String s = queue.peek(); // s = "A"
Java Queue的应用
1. 实现缓存淘汰策略
缓存的淘汰策略往往是基于队列实现的，因为缓存中新进入的元素往往比较“新鲜”，而较早进入的元素往往需要被淘汰。如果使用LinkedList来实现缓存，那么队头元素就是最先进入的元素，因此我们可以定时轮询缓存队列，淘汰队头元素。它的示例代码如下：
public class Cache {
private int maxSize;
private Queue<Object> queue;
public Cache(int maxSize) {
this.maxSize = maxSize;
this.queue = new LinkedList<>();
}
public void add(Object o) {
queue.offer(o);
if(queue.size() > maxSize) {
queue.poll();
}
}
}
2. 多线程中的工作队列
在多线程的环境中，经常需要将工作任务放在工作队列中，以待线程池中的线程取出并执行。如果使用ArrayBlockingQueue来实现工作队列，那么队列满了时，插入操作会被阻塞，直到有空间为止。它的示例代码如下：
public class Worker implements Runnable {
private BlockingQueue<Runnable> queue;
private volatile boolean running = true;
public Worker(BlockingQueue<Runnable> queue) {
this.queue = queue;
}
public void stop() {
running = false;
}
public void run() {
while(running) {
try {
Runnable task = queue.take();
task.run();
} catch (InterruptedException e) { }
}
}
}
public class ThreadPool {
private BlockingQueue<Runnable> queue;
private List<Worker> workers;
public ThreadPool(int poolSize, int queueSize) {
this.queue = new ArrayBlockingQueue<>(queueSize);
this.workers = new ArrayList<>();
for(int i = 0; i < poolSize; i++) {
Worker worker = new Worker(queue);
workers.add(worker);
new Thread(worker).start();
}
}
public void execute(Runnable task) {
try {
queue.put(task);
} catch (InterruptedException e) { }
}
public void stopAll() {
for(Worker worker : workers) {
worker.stop();
}
}
}
3. 实现广度优先搜索
广度优先搜索是一种图形搜索算法，它是从根节点开始，沿着一层一层的方式进行遍历，直到找到目标节点。在实现广度优先搜索时，可以使用Queue来存储待遍历的节点。它的示例代码如下：
public class Graph {
private Map<String, List<String>> map = new HashMap<>();
public void addEdge(String node1, String node2) {
List<String> neighbors1 = map.getOrDefault(node1, new ArrayList<>());
neighbors1.add(node2);
map.put(node1, neighbors1);
List<String> neighbors2 = map.getOrDefault(node2, new ArrayList<>());
neighbors2.add(node1);
map.put(node2, neighbors2);
}
public List<String> BFS(String start) {
Queue<String> queue = new LinkedList<>();
Set<String> visited = new HashSet<>();
queue.offer(start);
visited.add(start);
List<String> res = new ArrayList<>();
while(!queue.isEmpty()) {
String currNode = queue.poll();
res.add(currNode);
for(String neighbor : map.getOrDefault(currNode, new ArrayList<>())) {
if(!visited.contains(neighbor)) {
visited.add(neighbor);
queue.offer(neighbor);
}
}
}
return res;
}
}
结语
Java Queue是一种非常常用且重要的数据结构，它可以用于实现队列和栈结构、并发控制、广度优先搜索和缓存淘汰策略等功能。在开发中，我们应该根据实际需求选择合适的Queue实现方式，避免出现性能问题和线程安全问题。
原创文章，作者：OBWQ，如若转载，请注明出处：https://www.506064.com/n/140763.html
微信扫一扫 
支付宝扫一扫 