深入理解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實現方式，避免出現性能問題和線程安全問題。