Stack

棧結(jié)構(gòu)類型，表示對象的后進先出堆棧。Stack繼承自Vector，并拓展了五個允許將容器視為棧結(jié)構(gòu)的操作。

包括常見的pop和push操作、以及查看棧頂元素的方法、檢查棧是否為空的方法以及從棧頂向下進行搜索某個元素，并獲取該元素在棧內(nèi)深度的方法。

Deque 接口及其實現(xiàn)提供了一組更完整的 LIFO 堆棧操作能力，應該優(yōu)先考慮使用 Deque 及其實現(xiàn)。例如：

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

Queue

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

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

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

隊列通常是先進先出的，所以對元素的排序方式也是以先進先出的順序的，但是有特殊情況，例如，優(yōu)先級隊列是根據(jù)比較元素的優(yōu)先級進行排序的；另一種例子是后進先出隊列，即棧結(jié)構(gòu)。

無論使用哪種排序，隊列的頭部元素都是通過調(diào)用remove或poll刪除的。在 FIFO 隊列中，所有的新元素都是插入到隊列的尾部的，其他類型的隊列可能使用不同的插入規(guī)則，每個Queue的實現(xiàn)都必須明確指定其排序方式。

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

隊列的實現(xiàn)通常不定義hashCode和equals，因為對于具有相同的元素，但具有不同的排序方式的隊列，基于元素的相等并不是很好的定義方式。

Deque

Deque繼承自 Queue，是一種支持兩端元素插入和移除的順序結(jié)構(gòu)集合，簡稱 “雙端隊列” 。大多數(shù)雙端隊列對容量沒有固定限制。

Deque接口主要拓展了對于雙端隊列兩端元素操作的方法，也是兩種形式，一種拋出異常，一種返回特殊值 null 的形式。

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

Deque作為 LIFO 隊列使用時（棧結(jié)構(gòu)），它也會有一些等價于Stack的方法：

其他特性

與List接口不同，此接口不支持對元素的索引訪問。

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

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

BlockingQueue

BlockingQueue是Queue接口的另一個重要子接口，它用來代表一個可阻塞的隊列。支持在檢索元素是，等待隊列變?yōu)榉强赵俜祷財?shù)據(jù)。

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

• 拋出異常
• 返回特殊值
• 無限期阻塞當前線程，直到操作成功
• 在有限時間內(nèi)阻塞當前線程，超時即放棄執(zhí)行

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

特點

• 不支持空元素：BlockingQueue不接受空元素。在嘗試添加、放置或提供null時，實現(xiàn)會拋出NullPointerException。 null用作標記值以指示輪詢操作失敗。
• 容量受限：可能是容量受限的，在給定時間內(nèi)，可能只有一個剩余容量，超出該容量就不能在不阻塞的情況下放置其他元素。
• 主要用于實現(xiàn)生產(chǎn)者-消費者隊列，但還支持Collection接口。
• 線程安全需要它的實現(xiàn)類自身去實現(xiàn)。
• 批量操作不能保證原子性。
• 內(nèi)存一致性：和其他并發(fā)集合一樣，在一個線程中實現(xiàn)將一個對象存入BlockingQueue的操作，會發(fā)生在下一個其他線程對BlockingQueue中的該元素讀取或移除之前。

PriorityQueue 優(yōu)先級隊列

PriorityQueue是一個基于優(yōu)先級堆的無界限優(yōu)先級隊列。它是 Queue的直接實現(xiàn)類，優(yōu)先級隊列的元素排序有兩種情況：

• 根據(jù)元素的自然存儲順序
• 隊列構(gòu)造時提供的Comparator進行比較后排序

排序方式取決于具體的構(gòu)造函數(shù)的參數(shù)Comparator。

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

特點

優(yōu)先級隊列不允許null元素，依賴于自然排序的優(yōu)先級隊列也不允許插入不可比較的對象，否則會導致ClassCastException。

底層實現(xiàn)是通過數(shù)組來保存數(shù)據(jù)的：

transient Object[] queue;

不是線程安全的。

擴容機制

優(yōu)先級隊列的容量是沒有限制的，但是內(nèi)部存儲元素的結(jié)構(gòu)實際上是一個數(shù)組，它的擴容機制是有規(guī)律的。

初始化默認容量 11 ，后續(xù)擴容總是擴容到與隊列元素數(shù)量相同大小，這一點和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 %。
• 如果新容量超出最大數(shù)組容量。則通過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;
 ?  }

• 如果需要的容量超過數(shù)組最大容量，則限制隊列容量為 Int 的最大值。
• 如果需要的容量沒超過數(shù)組最大容量，則限制隊列容量為數(shù)組最大容量MAX_ARRAY_SIZE。

ArrayDeque

數(shù)組雙端隊列，是一種可調(diào)整大小的數(shù)組實現(xiàn)，沒有容量限制。它會根據(jù)需要自動擴容。

繼承關(guān)系

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

• AbstractCollection：提供了一些集合接口能力的基本封裝。
• 雙端隊列
• 可通過Object.clone()方法快速復制
• 支持序列化

底層實現(xiàn)

底層數(shù)據(jù)結(jié)構(gòu)是一個數(shù)組：

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總是指向下一個可插入的空位，這個意思就是 數(shù)組中至少留有一個空位置，所以元素可以先插入。

head = (head - 1) & (elements.length - 1)這行代碼比較難以理解。語義是：取余操作，同時解決head為負值的情況。 elements.length 必定是 2 的指數(shù)倍。elements.length - 1的二進制低位必為 1 ， 與head - 1進行與操作后，起到了取模的作用（取余數(shù)）。如果head - 1為負數(shù)（只可能是 -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;
 ?  }

這個函數(shù)的作用相當于擴容 100% 后，將原數(shù)組，分段復制進去：

首先復制head右側(cè)的元素，然后再把左邊的復制過來。即雖然是往隊列頭部插值，但實際還是在尾部插完值后，分段移動進行排序，最后組成了新數(shù)組。

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();   //擴容
}

特點：

• 不是線程安全的，在沒有外部處理同步的情況下，不支持多線程并發(fā)訪問。
• 禁止保存null元素。
• 作為棧使用時，可能比Stack快；作為隊列使用時， 比LinkedList快。
• 時間復雜度時常數(shù)級別的。

總結(jié)

常見的隊列除了 ArrayQueue、PriorityQuueue 和BlockingQueue，還有一個可以當作隊列的LinkedList，關(guān)于它在上一節(jié)的 List 體系中有詳細的講解。

• ArrayQueue，更適用于當作雙端隊列或棧結(jié)構(gòu)。
• Stack已不推薦使用，建議使用LinkedList或ArrayQueue替代。
• PriorityQueue用來處理優(yōu)先級，多了一個可自定義優(yōu)先級條件的能力。
• BlockingQueue常用于實現(xiàn) 生產(chǎn)者/消費者隊列，但線程安全需要外部自己去實現(xiàn)。

• 上面的幾種隊列，除了LinkedList，底層的數(shù)據(jù)結(jié)構(gòu)都是數(shù)組。
• Queue的有些實現(xiàn)沒有強制要求不允許存null ，但最好不要存null 。

到此這篇關(guān)于Java 集合框架 Queue 和 Stack 體系的文章就介紹到這了,更多相關(guān)Java 集合框架 內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論