深入理解Java Queue

引言

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