Java隊列 PriorityQueue

 ​

文章目錄

• ​​PriorityQueue​​
• ​​小結​​

PriorityQueue

我們知道，​

​Queue​

​是一個先進先出（FIFO）的隊列。

在銀行櫃台辦業務時，我們假設隻有一個櫃台在辦理業務，但是辦理業務的人很多，怎麼辦？

可以每個人先取一個号，例如：​

​A1​

​、​

​A2​

​A3​

​……然後，按照号碼順序依次辦理，實際上這就是一個​

​Queue​

​。

如果這時來了一個VIP客戶，他的号碼是​

​V1​

​，雖然目前排隊的是​

​A10​

​A11​

​A12​

​……但是櫃台下一個呼叫的客戶号碼卻是​

​V1​

這個時候，我們發現，要實作​

​“VIP插隊”​

​的業務，用​

​Queue​

​就不行了，因為​

​Queue​

​會嚴格按FIFO的原則取出隊首元素。我們需要的是優先隊列：​

​PriorityQueue​

​

​PriorityQueue​

​和​

​Queue​

​的差別在于，它的出隊順序與元素的優先級有關，對​

​PriorityQueue​

​調用​

​remove()​

​或​

​poll()​

​方法，傳回的總是優先級最高的元素。

要使用​

​PriorityQueue​

​，我們就必須給每個元素定義“優先級”。我們以實際代碼為例，先看看​

​PriorityQueue​

​的行為：

public class Main {
public static void main(String[] args) {
Queue<String> q = new PriorityQueue<>();
// 添加3個元素到隊列:
q.offer("apple");
q.offer("pear");
q.offer("banana");
System.out.println(q.poll()); // apple
System.out.println(q.poll()); // banana
System.out.println(q.poll()); // pear
System.out.println(q.poll()); // null,因為隊列為空
    }
}
      

我們放入的順序是​

​"apple"​

​"pear"​

​"banana"​

​，但是取出的順序卻是​

​"apple"​

​"banana"​

​"pear"​

​，這是因為從字元串的排序看，​

​"apple"​

​排在最前面，​

​"pear"​

​排在最後面。

是以，放入​

​PriorityQueue​

​的元素，必須實作​

​Comparable​

​接口，​

​PriorityQueue​

​會根據元素的排序順序決定出隊的優先級。

如果我們要放入的元素并沒有實作​

​Comparable​

​接口怎麼辦？​

​PriorityQueue​

​允許我們提供一個​

​Comparator​

​對象來判斷兩個元素的順序。我們以銀行排隊業務為例，實作一個​

​PriorityQueue​

​：

public class Main {
public static void main(String[] args) {
Queue<User> q = new PriorityQueue<>(new UserComparator());
// 添加3個元素到隊列:
q.offer(new User("Bob", "A1"));
q.offer(new User("Alice", "A2"));
q.offer(new User("Boss", "V1"));
System.out.println(q.poll()); // Boss/V1
System.out.println(q.poll()); // Bob/A1
System.out.println(q.poll()); // Alice/A2
System.out.println(q.poll()); // null,因為隊列為空
    }
}

class UserComparator implements Comparator<User> {
public int compare(User u1, User u2) {
if (u1.number.charAt(0) == u2.number.charAt(0)) {
// 如果兩人的号都是A開頭或者都是V開頭,比較号的大小:
return u1.number.compareTo(u2.number);
        }
if (u1.number.charAt(0) == 'V') {
// u1的号碼是V開頭,優先級高:
return -1;
        } else {
return 1;
        }
    }
}

class User {
public final String name;
public final String number;

public User(String name, String number) {
this.name = name;
this.number = number;
    }

public String toString() {
return name + "/" + number;
    }
}

      

實作​

​PriorityQueue​

​的關鍵在于提供的​

​UserComparator​

​對象，它負責比較兩個元素的大小（較小的在前）。​

​UserComparator​

​總是把​

​V​

​開頭的号碼優先傳回，隻有在開頭相同的時候，才比較号碼大小。

上面的​

​UserComparator​

​的比較邏輯其實還是有問題的，它會把​

​A10​

​排在​

​A2​

​的前面，請嘗試修複該錯誤。

小結

​PriorityQueue​

​實作了一個優先隊列：從隊首擷取元素時，總是擷取優先級最高的元素。