引言
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实现方式,避免出现性能问题和线程安全问题。