前面介紹了列表，其中包括List接口和LinkedList鏈表和ArrayList數組列表。這節介紹一個也很常見的數據結構：隊列。

我們知道，隊列是一個可以從尾部添加新元素、從頭部刪除元素的數據結構。對于有兩個頭的隊列，即雙端隊列，可以讓人們有效的在頭部和尾部同時添加或刪除元素。不過，隊列不支持在中間添加元素。這節將介紹兩個隊列接口：Queue接口和雙端隊列接口Deque，還有實現類：ArrayDeque和優先級隊列PriorityQueue。

1 隊列：Queue接口

Queue接口設計了一些可以在隊列頭部刪除元素、在尾部添加元素的方法。這個接口比較簡單，一共只有6個方法，分別如下：

（1）添加元素

boolean add(E e); boolean offer(E e);這兩個方法都在尾部添加一個值為e的元素。如果隊列沒有滿，將給定的元素添加到這個隊列的尾部并返回true。不同的是如果隊列滿了，add方法會拋出一個IllegalStateException異常，而offer方法返回false。

（2）刪除并返回元素

E remove(); E poll();這兩個方法刪除隊列頭部的元素。如果隊列非空，這兩個方法刪除頭部元素后并返回這個元素。不同的是如果隊列是空的，remove方法拋出一個NoSuchElementException異常，而poll方法返回false。

（3） 獲得頭部元素

E element(); E peek();這兩個方法都會返回頭部的元素，而都不刪除頭部元素。不同的是如果隊列是空的，element方法拋出一個NoSuchElementException異常，而peek方法返回null。

2 雙端隊列：Deque接口及ArrayDeque類

一般的隊列只能在頭部刪除元素、在尾部添加元素，即只有一個端。而雙端隊列有兩個端，支持在兩端同時添加或刪除元素。Deque接口是Java SE 6引入的，并由ArrayDeque類和LinkedList類實現，這兩個類都提供了雙端隊列，并在必要的時候可以增加隊列的長度。其實，還有一種隊列，叫做有限隊列，當然也包括有限雙端隊列，這兩個隊列不在本文的討論之內。

2.1 Deque接口

Deque接口在Queue接口的基礎之上增加了一些針對雙端添加和刪除元素的方法，這些方法根據出錯時的行為也可以分為幾組。這些方法就是在Queue接口中的方法名后面加上“First”和“Last”表明在哪端操作。這些方法整理如下：

（1）添加元素

void addFirst(E e); void addLast(E e); boolean offerFirst(E e); boolean offerLast(E e);這四個方法在頭部或尾部添加給定的元素。如果隊列滿了，前兩個方法將拋出一個IllegalStateException異常，后兩個方法返回false。

（2）刪除并返回元素

E removeFirst(); E removeLast(); E pollFirst(); E pollLast();這四個方法刪除頭部或尾部的元素并返回。如果隊列為空，前兩個方法將拋出一個NoSuchElementException異常，后兩個方法返回null。

（3）返回但不刪除元素

E getFirst(); E getLast(); E peekFirst(); E peekLast();這四個方法返回頭部或尾部的元素，但不刪除。如果隊列為空，前兩個方法將拋出一個NoSuchElementException異常，后兩個方法返回null。

2.2 ArrayDeque類

ArrayDeque類實現了Deque接口，是一個雙端隊列。不像LinkedList是一個雙向鏈表，ArrayDeque是一個雙向數組。這么說有點不準確，應該是，ArrayDeque的底層實現是一個循環數組：

transient Object[] elements; transient int head; transient int tail;什么是循環數組？對于普通的數組，下標為0的元素代表數組的第一個元素，下標最大的元素代表數組的最后一個元素，這是固定的，對于在尾部添加和刪除元素的隊列操作來說還可以，但是對于同時也要在頭部添加和刪除元素就不適合了，因為這時必須移動頭部元素后面的所有元素。而循環數組就解決了這個問題。

循環數組的基本思路是頭下標和尾下標不是固定的。即這樣：

其中中間的部分是隊列中的元素。從這里我們可以看出，隊列中的元素還是在數組中的連續部分存儲的。兩邊空的地方可以擴展隊列。如果要在頭部添加或刪除一個元素，只需要使頭下標head左移或右移一位即可，對于尾部的操作也是如此。這樣就避免了真個數組的移動，提高了性能。

可以如果頭部一直添加，或尾部一直添加，導致左面或右面不夠了怎么辦？這時就體現出循環數組的循環特點來了。具體的做法是，如果添加頭部時左面沒空間了，那么就在右面添加，就像這樣：

數組的總長度固定，保證能夠容納所有元素的情況下，兩個下標（head和tail）就像這樣來回循環著。

那么在這兩種情況下，隊列中的元素個數怎么計算呢？

對于上面那種情況很容易，元素個數就是tail-head+1。下面這種情況就不是那么清晰了。可以先算中間空余的部分，然后用總長度減去空余的。中間空余的部分的長度是head-tail-1，那么元素個數就是length-(head-tail-1)。

事實上，ArrayDeque類的實現者有個更好的方法，使用位運算：

public int size() {return (tail - head) & (elements.length - 1); }這樣就計算了元素的個數，很神奇。

可是，head和tail總有相等的時候。一種情況是隊列中沒有元素，這時head==tail，就像這樣：

另一種情況是，head循環后一直增加，一直增加到tail：

這兩種情況tail都等于head，看ArrayDeque類的isEmpty方法：

public boolean isEmpty() {return head == tail; }這又是怎么判斷到底是空呢還是滿呢？

事實上，ArrayDeque類的實現者不會讓第二種情況發生。因為ArrayDeque是一個可變長度隊列，即如果空間不夠，程序會自動擴大數組的容量為原來的2倍，然后將原來的元素復制到新的數組中。

還有一點，初始化時這個數組的長度是8，如果滿了就擴大為原來的2倍，因此數組的長度一直是2的冪。

這個雙端隊列的基本操作方法都很簡單，這里就不過多敘述。

雖然雙端隊列只可以在兩端做添加和刪除操作，但ArrayDeque類還增加了兩個方法可以在中間刪除給定的元素：

public boolean removeFirstOccurrence(Object o) public boolean removeLastOccurrence(Object o)第一個方法刪除第一次出現給定對象的元素（第一次出現即從head開始到tail結束）；第二個方法刪除最后一次出現給定對象的元素。

由于雙端隊列的特殊性（head可能比tail大），如果要從head到tail遍歷隊列，需要這樣：

int mask=elements.length-1; int i=head; while(i!=tail) {dosomething with elements[i];i=(i+1)&mask; }不過這樣的話tail的那個元素沒有遍歷到。

ArrayDeque類中還定義了兩個迭代器，一個是正向的Iterator迭代器，通過方法iterator返回；另一個是反向迭代器DescendingIterator，通過方法descendingIterator返回。關于迭代器的部分在上一節LinkedList部分講到了，這里不過多重復。ArrayDeque類內部實現Iterator接口的內部類分別是：

private class DeqIterator implements Iterator<E> private class DescendingIterator implements Iterator<E>這兩個類實現了next和hasNext方法。

3 優先級隊列：PriorityQueue

優先級隊列中的元素可以按照任意的順序插入，卻總是按照排序的順序進行檢索。也就是說，無論何時調用remove方法，總會獲得當前優先級隊列中最小的元素。然而，優先級隊列并沒有對所有的元素進行排序。如果用迭代的方式處理這些元素，并不需要對它們進行排序。優先級隊列使用了一個優雅且高效的數據結構，稱為堆（heap）。堆是一個可以自我調節的二叉樹，對樹執行添加（add）和刪除（remove）操作，可以讓最小的元素移動到根，而不必花時間對元素進行排序。

PriorityQueue類的底層是使用數組保存數據的：

transient Object[] queue; private int size = 0;其中size保存元素的個數。使用數組保存一個二叉樹，對于一個節點下標為n，則左兒子的下標為2*n+1，右兒子下標為2*(n+1)。而隊列中的最小元素保存在queue[0]中。

PriorityQueue即可以保存實現了Comparable接口的類對象，也可以保存在構造器中提供比較器的對象。比如，下面的代碼使用自定義比較器構造一個優先級隊列：

PriorityQueue<Student> pq=new PriorityQueueM<>(new Comparator<Student>(){public int compare(Student s1,Student s2){return s1.getScore()-s2.getScore();} } );這個比較器比較兩個學生的成績。這是一個匿名內部類。

在最小堆中，最重要的操作就是添加元素或刪除元素后如何調整這個堆。基本上，如果添加一個元素，可以先將這個元素放在最下面，然后將這個元素向上移動，知道大于等于它的父節點或稱為根節點；還可以將這個元素放在根節點位置，然后將這個元素向下移動，直到小于等于子節點或稱為一個葉節點。

下面是PriorityQueue類中實現的上移和下移代碼，對我們的編程很有幫助：

private void siftUp(int k, E x) {if (comparator != null)siftUpUsingComparator(k, x);elsesiftUpComparable(k, x); }@SuppressWarnings("unchecked") private void siftUpComparable(int k, E x) {Comparable<? super E> key = (Comparable<? super E>) x;while (k > 0) {int parent = (k - 1) >>> 1;Object e = queue[parent];if (key.compareTo((E) e) >= 0)break;queue[k] = e;k = parent;}queue[k] = key; }@SuppressWarnings("unchecked") private void siftUpUsingComparator(int k, E x) {while (k > 0) {int parent = (k - 1) >>> 1;Object e = queue[parent];if (comparator.compare(x, (E) e) >= 0)break;queue[k] = e;k = parent;}queue[k] = x; }private void siftDown(int k, E x) {if (comparator != null)siftDownUsingComparator(k, x);elsesiftDownComparable(k, x); }@SuppressWarnings("unchecked") private void siftDownComparable(int k, E x) {Comparable<? super E> key = (Comparable<? super E>)x;int half = size >>> 1; // loop while a non-leafwhile (k < half) {int child = (k << 1) + 1; // assume left child is leastObject c = queue[child];int right = child + 1;if (right < size &&((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)c = queue[child = right];if (key.compareTo((E) c) <= 0)break;queue[k] = c;k = child;}queue[k] = key; }@SuppressWarnings("unchecked") private void siftDownUsingComparator(int k, E x) {int half = size >>> 1;while (k < half) {int child = (k << 1) + 1;Object c = queue[child];int right = child + 1;if (right < size &&comparator.compare((E) c, (E) queue[right]) > 0)c = queue[child = right];if (comparator.compare(x, (E) c) <= 0)break;queue[k] = c;k = child;}queue[k] = x; }使用優先級隊列的典型示例是任務調度。每一個任務都有一個優先級，任務以隨機順序添加到隊列中。每當啟動一個新的任務時，都將優先級最高的任務從隊列中刪除（習慣上將1設為最高優先級）。

下面的代碼展示了PriorityQueue類的使用：

import java.util.*; public class PriorityQueueTest {public static void main(String[] args) {PriorityQueue<GregorianCalendar> pq=new PriorityQueue<>();pq.add(new GregorianCalendar(1906,Calendar.DECEMBER,9));pq.add(new GregorianCalendar(1815,Calendar.DECEMBER,10));pq.add(new GregorianCalendar(1903,Calendar.DECEMBER,3));pq.add(new GregorianCalendar(1910,Calendar.JUNE,22));System.out.println("Iterating over elements...");for(GregorianCalendar date:pq){System.out.println(date.get(Calendar.YEAR));}System.out.println("Removing elements...");while(!pq.isEmpty()){System.out.println(pq.remove().get(Calendar.YEAR));}} }結果如下：

總結

以上是生活随笔為你收集整理的Java集合(三)：Queue队列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。