文章目錄
- 隊列Queue
- 優先隊列PriorityQueue
- 雙端隊列Deque
隊列Queue
在Java的标準庫中，隊列接口Queue定義了以下幾個方法：
- int size()：擷取隊列長度；
- boolean add(E)/boolean offer(E)：添加元素到隊尾；
- E remove()/E poll()：擷取隊首元素并從隊列中删除；
- E element()/E peek()：擷取隊首元素但并不從隊列中删除。
注意到添加、删除和擷取隊列元素總是有兩個方法，這是因為在添加或擷取元素失敗時，這兩個方法的行為是不同的。我們用一個表格總結如下：
隊列的實作類：LinkedList
優先隊列PriorityQueue
PriorityQueue和Queue的差別在于，它的出隊順序與元素的優先級有關，對PriorityQueue調用remove()或poll()方法，傳回的總是優先級最高的元素。
要使用PriorityQueue，我們就必須給每個元素定義“優先級”。
要實作放入優先隊列元素的優先級，方法為：
- 放入PriorityQueue的元素，必須實作Comparable接口，PriorityQueue會根據元素的排序順序決定出隊的優先級。
- PriorityQueue允許我們提供一個Comparator對象來判斷兩個元素的順序
可以這樣了解優先隊列：
- 始終建構小頂堆，即堆頂的元素按排序算法始終最小（傳回-1）.
- 排序算法是這樣的：傳回0，表示相等，傳回整數表示大于，傳回複數表示小于
- 由于優先隊列即是對堆的實作，其底層也是基于動态數組加上擴容機制，隻不過加了個堆排序
源碼
public class PriorityQueue<E> extends AbstractQueue<E>
implements java.io.Serializable {
private static final long serialVersionUID = -7720805057305804111L;
//動态數組預設大小
private static final int DEFAULT_INITIAL_CAPACITY = 11;
/**
* Priority queue represented as a balanced binary heap: the two
* children of queue[n] are queue[2*n+1] and queue[2*(n+1)]. The
* priority queue is ordered by comparator, or by the elements'
* natural ordering, if comparator is null: For each node n in the
* heap and each descendant d of n, n <= d. The element with the
* lowest value is in queue[0], assuming the queue is nonempty.
*/
transient Object[] queue; // non-private to simplify nested class access
/**
* The number of elements in the priority queue.
*/
int size;
/**
* The comparator, or null if priority queue uses elements'
* natural ordering.
*/
private final Comparator<? super E> comparator;
transient int modCount; // non-private to simplify nested class access
public PriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}
public PriorityQueue(int initialCapacity) {
this(initialCapacity, null);
}
public PriorityQueue(Comparator<? super E> comparator) {
this(DEFAULT_INITIAL_CAPACITY, comparator);
}
動态擴容
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// Double size if small; else grow by 50%
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
// overflow-conscious code
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
queue = Arrays.copyOf(queue, newCapacity);
}
雙端隊列Deque
Java集合提供了接口Deque來實作一個雙端隊列，它的功能是：
- 既可以添加到隊尾，也可以添加到隊首；
- 既可以從隊首擷取，又可以從隊尾擷取。
我們來比較一下Queue和Deque出隊和入隊的方法：
對于添加元素到隊尾的操作，Queue提供了add()/offer()方法，而Deque提供了addLast()/offerLast()方法。添加元素到對首、取隊尾元素的操作在Queue中不存在，在Deque中由addFirst()/removeLast()等方法提供。
注意到Deque接口實際上擴充自Queue：
public interface Deque<E> extends Queue<E> {
...
}
是以，Queue提供的add()/offer()方法在Deque中也可以使用，但是，使用Deque，最好不要調用offer()，而是調用offerLast()：
Deque是一個接口，它的實作類有ArrayDeque和LinkedList。