Stack

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

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

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

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

Queue

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

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

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

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

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

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

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

Deque

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

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

Deque可以當(dāng)作 FIFO 隊(duì)列使用，所以它的一些拓展的方法等效于Queue的一些方法：

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

其他特性

與List接口不同，此接口不支持對(duì)元素的索引訪問(wèn)。

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

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

BlockingQueue

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

BlockingQueue有四種類型，用來(lái)解決當(dāng)前不能立刻處理，需要再未來(lái)某個(gè)時(shí)間點(diǎn)下滿足指定條件才執(zhí)行的操作。

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

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

特點(diǎn)

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

PriorityQueue 優(yōu)先級(jí)隊(duì)列

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

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

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

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

特點(diǎn)

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

底層實(shí)現(xiàn)是通過(guò)數(shù)組來(lái)保存數(shù)據(jù)的：

transient Object[] queue;

不是線程安全的。

擴(kuò)容機(jī)制

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

初始化默認(rèn)容量 11 ，后續(xù)擴(kuò)容總是擴(kuò)容到與隊(duì)列元素?cái)?shù)量相同大小，這一點(diǎn)和ArrayList基本一致。

 ? ?public boolean offer(E e) {
 ? ? ? ?if (e == null)
 ? ? ? ? ? ?throw new NullPointerException(); // 不允許 null 元素
 ? ? ? ?modCount++;
 ? ? ? ?int i = size;
 ? ? ? ?if (i >= queue.length)
 ? ? ? ? ? ?grow(i + 1); // 真正的擴(kuò)容方法
 ? ? ? ?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% 默認(rèn)擴(kuò)容量
 ? ? ? ?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);
 ?  }

• 如果舊的隊(duì)列容量 < 64 ，每次擴(kuò)容 100% 并加 2 。超過(guò) 64，每次擴(kuò)容舊容量的 50 %。
• 如果新容量超出最大數(shù)組容量。則通過(guò)hugeCapacity()計(jì)算容量：

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

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

ArrayDeque

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

繼承關(guān)系

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

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

底層實(shí)現(xiàn)

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

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

通過(guò)head和tail作為索引來(lái)支持雙端隊(duì)列的特性。

擴(kuò)容機(jī)制

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

這里先插入，后擴(kuò)容。tail總是指向下一個(gè)可插入的空位，這個(gè)意思就是 數(shù)組中至少留有一個(gè)空位置，所以元素可以先插入。

head = (head - 1) & (elements.length - 1)這行代碼比較難以理解。語(yǔ)義是：取余操作，同時(shí)解決head為負(fù)值的情況。 elements.length 必定是 2 的指數(shù)倍。elements.length - 1的二進(jìn)制低位必為 1 ， 與head - 1進(jìn)行與操作后，起到了取模的作用（取余數(shù)）。如果head - 1為負(fù)數(shù)（只可能是 -1），則相當(dāng)于對(duì)其取相對(duì)于elements.length的補(bǔ)碼。

真正的擴(kuò)容機(jī)制在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;
 ?  }

這個(gè)函數(shù)的作用相當(dāng)于擴(kuò)容 100% 后，將原數(shù)組，分段復(fù)制進(jìn)去：

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

addLast則是直接把新元素存入tail位置上，然后在重新計(jì)算tail ，檢查是否需要擴(kuò)容。

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

特點(diǎn)：

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

總結(jié)

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

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

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

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

最新評(píng)論