Java 集合框架 Queue 和 Stack 體系

2022-06-16 10:01:57

Stack

棧結構型別，表示物件的後進先出堆疊。Stack繼承自Vector，並拓展了五個允許將容器視為棧結構的操作。

包括常見的pop和push操作、以及檢視棧頂元素的方法、檢查棧是否為空的方法以及從棧頂向下進行搜尋某個元素，並獲取該元素在棧內深度的方法。

Deque 介面及其實現提供了一組更完整的 LIFO 堆疊操作能力，應該優先考慮使用 Deque 及其實現。例如：

Deque<Integer> stack = new ArrayDeque<Integer>();

Queue

Queue介面定義了佇列的能力，它繼承自Collection ，除了基本的集合操作外，佇列提供了額外的插入、獲取、檢查等操作。

public interface Queue<E> extends Collection<E> {
    // 在不違反容量限制的情況下立即將指定元素插入此佇列，成功時返回 true，如果當前沒有可用空間則丟擲 IllegalStateException。
    boolean add(E e);
    // 在不違反容量限制的情況下立即將指定元素插入此佇列。 在使用容量受限的佇列中，一般最好使用這種方法新增，僅通過丟擲異常可能無法插入元素。
    boolean offer(E e);
    // 檢索並刪除此佇列的頭部。 此方法與 poll 的不同之處僅在於如果此佇列為空，它將引發異常。
    E remove();
    // 檢索並移除此佇列的頭部，如果此佇列為空，則返回 null。
    E poll();
    // 檢索但不刪除此佇列的頭部。 此方法與 peek 的不同之處僅在於如果此佇列為空，它將引發異常。
    E element();
    // 檢索但不刪除此佇列的頭部，如果此佇列為空，則返回 null。
    E peek();
}

可以看出，每一種操作都存在兩種定義，一種是在操作失敗的情況下強制丟擲異常的，另一種則是返回null不強制丟擲異常的。

	Throws exception	Returns special value
Insert	add(e)	offer(e)
Remove	remove()	poll()
Examine	element()	peek()

佇列通常是先進先出的，所以對元素的排序方式也是以先進先出的順序的，但是有特殊情況，例如，優先順序佇列是根據比較元素的優先順序進行排序的；另一種例子是後進先出佇列，即棧結構。

無論使用哪種排序，佇列的頭部元素都是通過呼叫remove或poll刪除的。在 FIFO 佇列中，所有的新元素都是插入到佇列的尾部的，其他型別的佇列可能使用不同的插入規則，每個Queue的實現都必須明確指定其排序方式。

佇列的另一個特性是不允許插入null ，儘管在某些實現中，例如LinkedList，允許儲存null。但在這種實現中，也不應該將null插入到佇列中，因為 null 被 poll 方法作為特殊返回值，以表明佇列不包含任何元素。

佇列的實現通常不定義hashCode和equals，因為對於具有相同的元素，但具有不同的排序方式的佇列，基於元素的相等並不是很好的定義方式。

Deque

Deque繼承自 Queue，是一種支援兩端元素插入和移除的順序結構集合，簡稱 “雙端佇列” 。大多數雙端佇列對容量沒有固定限制。

Deque介面主要拓展了對於雙端佇列兩端元素操作的方法，也是兩種形式，一種丟擲異常，一種返回特殊值 null 的形式。

Deque可以當作 FIFO 佇列使用，所以它的一些拓展的方法等效於Queue的一些方法：

Deque作為 LIFO 佇列使用時（棧結構），它也會有一些等價於Stack的方法：

其他特性

與List介面不同，此介面不支援對元素的索引存取。

另外雖然沒有嚴格要求Deque的實現禁止插入null元素，但在使用中的確應該儘量避免插入null，因為null元素被各種操作方法作為特殊的返回值，這裡和 Queue 一樣。

另一個與Queue相同的是，它也沒有定義需要實現hash和equals方法，理由和Queue是一樣的。

BlockingQueue

BlockingQueue是Queue介面的另一個重要子介面，它用來代表一個可阻塞的佇列。支援在檢索元素是，等待佇列變為非空再返回資料。

BlockingQueue有四種型別，用來解決當前不能立刻處理，需要再未來某個時間點下滿足指定條件才執行的操作。

丟擲異常
返回特殊值
無限期阻塞當前執行緒，直到操作成功
在有限時間內阻塞當前執行緒，超時即放棄執行

以下這張表是同一個行為在不同型別的方法表：

特點

不支援空元素：BlockingQueue不接受空元素。在嘗試新增、放置或提供null時，實現會丟擲NullPointerException。 null用作標記值以指示輪詢操作失敗。
容量受限：可能是容量受限的，在給定時間內，可能只有一個剩餘容量，超出該容量就不能在不阻塞的情況下放置其他元素。
主要用於實現生產者-消費者佇列，但還支援Collection介面。
執行緒安全需要它的實現類自身去實現。
批次操作不能保證原子性。
記憶體一致性：和其他並行集合一樣，在一個執行緒中實現將一個物件存入BlockingQueue的操作，會發生在下一個其他執行緒對BlockingQueue中的該元素讀取或移除之前。

PriorityQueue 優先順序佇列

PriorityQueue是一個基於優先順序堆的無界限優先順序佇列。它是 Queue的直接實現類，優先順序佇列的元素排序有兩種情況：

根據元素的自然儲存順序
佇列構造時提供的Comparator進行比較後排序

排序方式取決於具體的建構函式的引數Comparator。

    public PriorityQueue(Comparator<? super E> comparator) {
        this(DEFAULT_INITIAL_CAPACITY, comparator);
    }

特點

優先順序佇列不允許null元素，依賴於自然排序的優先順序佇列也不允許插入不可比較的物件，否則會導致ClassCastException。

底層實現是通過陣列來儲存資料的：

transient Object[] queue;

不是執行緒安全的。

擴容機制

優先順序佇列的容量是沒有限制的，但是內部儲存元素的結構實際上是一個陣列，它的擴容機制是有規律的。

初始化預設容量 11 ，後續擴容總是擴容到與佇列元素數量相同大小，這一點和ArrayList基本一致。

    public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException(); // 不允許 null 元素
        modCount++;
        int i = size;
        if (i >= queue.length)
            grow(i + 1); // 真正的擴容方法
        size = i + 1;
        if (i == 0)
            queue[0] = e;
        else
            siftUp(i, e);
        return true;
    }

    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);
    }

如果舊的佇列容量 < 64 ，每次擴容 100% 並加 2 。超過 64，每次擴容舊容量的 50 %。
如果新容量超出最大陣列容量。則通過hugeCapacity()計算容量：

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

如果需要的容量超過陣列最大容量，則限制佇列容量為 Int 的最大值。
如果需要的容量沒超過陣列最大容量，則限制佇列容量為陣列最大容量MAX_ARRAY_SIZE。

ArrayDeque

陣列雙端佇列，是一種可調整大小的陣列實現，沒有容量限制。它會根據需要自動擴容。

繼承關係

public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>, Cloneable, Serializable

AbstractCollection：提供了一些集合介面能力的基本封裝。
雙端佇列
可通過Object.clone()方法快速複製
支援序列化

底層實現

底層資料結構是一個陣列：

transient Object[] elements;
transient int head;
transient int tail;

通過head和tail作為索引來支援雙端佇列的特性。

擴容機制

    public void addFirst(E e) {
        if (e == null)
            throw new NullPointerException(); // 不允許 null 
        elements[head = (head - 1) & (elements.length - 1)] = e; // 防止下標越界處理
        if (head == tail) // 檢查空間是否夠用， == 說明空間不夠了
            doubleCapacity(); // 擴容
    }

這裡先插入，後擴容。tail總是指向下一個可插入的空位，這個意思就是陣列中至少留有一個空位置，所以元素可以先插入。

head = (head - 1) & (elements.length - 1)這行程式碼比較難以理解。語意是：取餘操作，同時解決head為負值的情況。 elements.length 必定是 2 的指數倍。elements.length - 1的二進位制低位必為 1 ，與head - 1進行與操作後，起到了取模的作用（取餘數）。如果head - 1為負數（只可能是 -1），則相當於對其取相對於elements.length的二補數。

真正的擴容機制在doubleCapacity()：

    private void doubleCapacity() {
        assert head == tail;
        int p = head;
        int n = elements.length;
        int r = n - p; // number of elements to the right of p
        int newCapacity = n << 1;
        if (newCapacity < 0)
            throw new IllegalStateException("Sorry, deque too big");
        Object[] a = new Object[newCapacity];
        System.arraycopy(elements, p, a, 0, r);
        System.arraycopy(elements, 0, a, r, p);
        elements = a;
        head = 0;
        tail = n;
    }

這個函數的作用相當於擴容 100% 後，將原陣列，分段複製進去：

首先複製head右側的元素，然後再把左邊的複製過來。即雖然是往佇列頭部插值，但實際還是在尾部插完值後，分段移動進行排序，最後組成了新陣列。

addLast則是直接把新元素存入tail位置上，然後在重新計算tail ，檢查是否需要擴容。

public void addLast(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[tail] = e;   //賦值
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)   //下標越界處理
        doubleCapacity();   //擴容
}

特點：