Java隊列 Queue

文章目錄

• ​​Queue​​
• ​​小結​​

Queue

隊列（​

​Queue​

​）是一種經常使用的集合。​

​Queue​

​實際上是實作了一個先進先出（FIFO：First In First Out）的有序表。它和​

​List​

​的差別在于，​

​List​

​可以在任意位置添加和删除元素，而​

​Queue​

​隻有兩個操作：

• 把元素添加到隊列末尾；
• 從隊列頭部取出元素。

超市的收銀台就是一個隊列：

在Java的标準庫中，隊列接口Queue定義了以下幾個方法：

• ​

  ​int size()​

  ​：擷取隊列長度；

• ​boolean add(E)​

  ​/​

  ​boolean offer(E)​

  ​：添加元素到隊尾；

• ​E remove()​

  ​E poll()​

  ​：擷取隊首元素并從隊列中删除；

• ​E element()​

  ​E peek()​

  ​：擷取隊首元素但并不從隊列中删除。

對于具體的實作類，有的Queue有最大隊列長度限制，有的Queue沒有。注意到添加、删除和擷取隊列元素總是有兩個方法，這是因為在添加或擷取元素失敗時，這兩個方法的行為是不同的。我們用一個表格總結如下：

添加元素到隊尾	傳回false或null
	add(E e)	boolean offer(E e)
取隊首元素并删除	E remove()	E poll()
取隊首元素但不删除	E element()	E peek()

舉個栗子，假設我們有一個隊列，對它做一個添加操作，如果調用 ​

​add()​

​方法，當添加失敗時（可能超過了隊列的容量），它會抛出異常：

Queue<String> q = ...
try {
q.add("Apple");
System.out.println("添加成功");
} catch(IllegalStateException e) {
System.out.println("添加失敗");
}
      

如果我們調用 ​

​offer()​

​ 方法來添加元素，當添加失敗時，它不會抛異常，而是傳回​

​false​

​：

Queue<String> q = ...
if (q.offer("Apple")) {
System.out.println("添加成功");
} else {
System.out.println("添加失敗");
}
      

當我們需要從​

​Queue​

​中取出隊首元素時，如果目前​

​Queue​

​是一個空隊列，調用​

​remove()​

​方法，它會抛出異常：

Queue<String> q = ...
try {
String s = q.remove();
System.out.println("擷取成功");
} catch(IllegalStateException e) {
System.out.println("擷取失敗");
}
      

如果我們調用​

​poll()​

​方法來取出隊首元素，當擷取失敗時，它不會抛異常，而是傳回​

​null​

Queue<String> q = ...
String s = q.poll();
if (s != null) {
System.out.println("擷取成功");
} else {
System.out.println("擷取失敗");
}
      

是以，兩套方法可以根據需要來選擇使用。

注意：不要把​

​null​

​添加到隊列中，否則​

​poll()​

​方法傳回​

​null​

​時，很難确定是取到了​

​null​

​元素還是隊列為空。

接下來我們以​

​poll()​

​和​

​peek()​

​為例來說說“擷取并删除”與“擷取但不删除”的差別。對于​

​Queue​

​來說，每次調用​

​poll()​

​，都會擷取隊首元素，并且擷取到的元素已經從隊列中被删除了：

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

      

如果用​

​peek()​

​，因為擷取隊首元素時，并不會從隊列中删除這個元素，是以可以反複擷取：

public class Main {
public static void main(String[] args) {
Queue<String> q = new LinkedList<>();
// 添加3個元素到隊列:
q.offer("apple");
q.offer("pear");
q.offer("banana");
// 隊首永遠都是apple，因為peek()不會删除它:
System.out.println(q.peek()); // apple
System.out.println(q.peek()); // apple
System.out.println(q.peek()); // apple
    }
}
      

從上面的代碼中，我們還可以發現，​

​LinkedList​

​即實作了​

​List​

​接口，又實作了​

​Queue​

​接口，但是，在使用的時候，如果我們把它當作​

​List​

​，就擷取​

​List​

​的引用，如果我們把它當作​

​Queue​

​Queue​

​的引用：

// 這是一個List:
List<String> list = new LinkedList<>();
// 這是一個Queue:
Queue<String> queue = new LinkedList<>();
      

始終按照面向抽象程式設計的原則編寫代碼，可以大大提高代碼的品質。

小結

隊列​

​Queue​

​實作了一個先進先出（FIFO）的資料結構：

• 通過​

  ​add()​

  ​offer()​

  ​方法将元素添加到隊尾；

• ​remove()​

  ​poll()​

  ​從隊首擷取元素并删除；

• ​element()​

  ​peek()​

  ​從隊首擷取元素但不删除。