Java?集合框架?Queue?和?Stack?體系
Stack
棧結(jié)構(gòu)類型,表示對象的后進(jìn)先出堆棧。Stack
繼承自Vector
,并拓展了五個允許將容器視為棧結(jié)構(gòu)的操作。
包括常見的pop
和push
操作、以及查看棧頂元素的方法、檢查棧是否為空的方法以及從棧頂向下進(jìn)行搜索某個元素,并獲取該元素在棧內(nèi)深度的方法。
Deque 接口及其實現(xiàn)提供了一組更完整的 LIFO 堆棧操作能力,應(yīng)該優(yōu)先考慮使用 Deque 及其實現(xiàn)。例如:
Deque<Integer> stack = new ArrayDeque<Integer>();
Queue
Queue
接口定義了隊列的能力,它繼承自Collection
,除了基本的集合操作外,隊列提供了額外的插入、獲取、檢查等操作。
public interface Queue<E> extends Collection<E> { ? ?// 在不違反容量限制的情況下立即將指定元素插入此隊列,成功時返回 true,如果當(dāng)前沒有可用空間則拋出 IllegalStateException。 ? ?boolean add(E e); ? ?// 在不違反容量限制的情況下立即將指定元素插入此隊列。 在使用容量受限的隊列中,一般最好使用這種方法添加,僅通過拋出異??赡軣o法插入元素。 ? ?boolean offer(E e); ? ?// 檢索并刪除此隊列的頭部。 此方法與 poll 的不同之處僅在于如果此隊列為空,它將引發(fā)異常。 ? ?E remove(); ? ?// 檢索并移除此隊列的頭部,如果此隊列為空,則返回 null。 ? ?E poll(); ? ?// 檢索但不刪除此隊列的頭部。 此方法與 peek 的不同之處僅在于如果此隊列為空,它將引發(fā)異常。 ? ?E element(); ? ?// 檢索但不刪除此隊列的頭部,如果此隊列為空,則返回 null。 ? ?E peek(); }
可以看出,每一種操作都存在兩種定義,一種是在操作失敗的情況下強(qiáng)制拋出異常的,另一種則是返回null
不強(qiáng)制拋出異常的。
Throws exception | Returns special value | |
---|---|---|
Insert | add(e) | offer(e) |
Remove | remove() | poll() |
Examine | element() | peek() |
隊列通常是先進(jìn)先出的,所以對元素的排序方式也是以先進(jìn)先出的順序的,但是有特殊情況,例如,優(yōu)先級隊列是根據(jù)比較元素的優(yōu)先級進(jìn)行排序的;另一種例子是后進(jìn)先出隊列,即棧結(jié)構(gòu)。
無論使用哪種排序,隊列的頭部元素都是通過調(diào)用remove
或poll
刪除的。在 FIFO 隊列中,所有的新元素都是插入到隊列的尾部的,其他類型的隊列可能使用不同的插入規(guī)則,每個Queue
的實現(xiàn)都必須明確指定其排序方式。
隊列的另一個特性是不允許插入null
,盡管在某些實現(xiàn)中,例如LinkedList
,允許存儲null
。但在這種實現(xiàn)中,也不應(yīng)該將null
插入到隊列中,因為 null 被 poll
方法作為特殊返回值,以表明隊列不包含任何元素。
隊列的實現(xiàn)通常不定義hashCode
和equals
,因為對于具有相同的元素,但具有不同的排序方式的隊列,基于元素的相等并不是很好的定義方式。
Deque
Deque
繼承自 Queue
,是一種支持兩端元素插入和移除的順序結(jié)構(gòu)集合,簡稱 “雙端隊列” 。大多數(shù)雙端隊列對容量沒有固定限制。
Deque
接口主要拓展了對于雙端隊列兩端元素操作的方法,也是兩種形式,一種拋出異常,一種返回特殊值 null 的形式。
Deque
可以當(dāng)作 FIFO 隊列使用,所以它的一些拓展的方法等效于Queue
的一些方法:
Deque
作為 LIFO 隊列使用時(棧結(jié)構(gòu)),它也會有一些等價于Stack
的方法:
其他特性
與List
接口不同,此接口不支持對元素的索引訪問。
另外雖然沒有嚴(yán)格要求Deque
的實現(xiàn)禁止插入null
元素,但在使用中的確應(yīng)該盡量避免插入null
,因為null
元素被各種操作方法作為特殊的返回值,這里和 Queue
一樣。
另一個與Queue
相同的是,它也沒有定義需要實現(xiàn)hash
和equals
方法,理由和Queue
是一樣的。
BlockingQueue
BlockingQueue
是Queue
接口的另一個重要子接口,它用來代表一個可阻塞的隊列。支持在檢索元素是,等待隊列變?yōu)榉强赵俜祷財?shù)據(jù)。
BlockingQueue
有四種類型,用來解決當(dāng)前不能立刻處理,需要再未來某個時間點下滿足指定條件才執(zhí)行的操作。
- 拋出異常
- 返回特殊值
- 無限期阻塞當(dāng)前線程,直到操作成功
- 在有限時間內(nèi)阻塞當(dāng)前線程,超時即放棄執(zhí)行
以下這張表是同一個行為在不同類型的方法表:
特點
- 不支持空元素:
BlockingQueue
不接受空元素。在嘗試添加、放置或提供null
時,實現(xiàn)會拋出NullPointerException
。null
用作標(biāo)記值以指示輪詢操作失敗。 - 容量受限:可能是容量受限的,在給定時間內(nèi),可能只有一個剩余容量,超出該容量就不能在不阻塞的情況下放置其他元素。
- 主要用于實現(xiàn)生產(chǎn)者-消費(fèi)者隊列,但還支持
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
進(jìn)行比較后排序
排序方式取決于具體的構(gòu)造函數(shù)的參數(shù)Comparator
。
? ?public PriorityQueue(Comparator<? super E> comparator) { ? ? ? ?this(DEFAULT_INITIAL_CAPACITY, comparator); ? }
特點
優(yōu)先級隊列不允許null
元素,依賴于自然排序的優(yōu)先級隊列也不允許插入不可比較的對象,否則會導(dǎo)致ClassCastException
。
底層實現(xiàn)是通過數(shù)組來保存數(shù)據(jù)的:
transient Object[] queue;
不是線程安全的。
擴(kuò)容機(jī)制
優(yōu)先級隊列的容量是沒有限制的,但是內(nèi)部存儲元素的結(jié)構(gòu)實際上是一個數(shù)組,它的擴(kuò)容機(jī)制是有規(guī)律的。
初始化默認(rèn)容量 11 ,后續(xù)擴(kuò)容總是擴(kuò)容到與隊列元素數(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); // 真正的擴(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); ? }
- 如果舊的隊列容量 < 64 ,每次擴(kuò)容 100% 并加 2 。超過 64,每次擴(kuò)容舊容量的 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ù)需要自動擴(kuò)容。
繼承關(guān)系
public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>, Cloneable, Serializable
AbstractCollection
:提供了一些集合接口能力的基本封裝。- 雙端隊列
- 可通過
Object.clone()
方法快速復(fù)制 - 支持序列化
底層實現(xiàn)
底層數(shù)據(jù)結(jié)構(gòu)是一個數(shù)組:
transient Object[] elements; transient int head; transient int tail;
通過head
和tail
作為索引來支持雙端隊列的特性。
擴(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) // 檢查空間是否夠用, == 說明空間不夠了 ? ? ? ? ? ?doubleCapacity(); // 擴(kuò)容 ? }
這里先插入,后擴(kuò)容。tail
總是指向下一個可插入的空位,這個意思就是 數(shù)組中至少留有一個空位置,所以元素可以先插入。
head = (head - 1) & (elements.length - 1)
這行代碼比較難以理解。語義是:取余操作,同時解決head
為負(fù)值的情況。 elements.length
必定是 2 的指數(shù)倍。elements.length - 1
的二進(jìn)制低位必為 1 , 與head - 1
進(jìn)行與操作后,起到了取模的作用(取余數(shù))。如果head - 1
為負(fù)數(shù)(只可能是 -1),則相當(dāng)于對其取相對于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; ? }
這個函數(shù)的作用相當(dāng)于擴(kuò)容 100% 后,將原數(shù)組,分段復(fù)制進(jìn)去:
首先復(fù)制head
右側(cè)的元素,然后再把左邊的復(fù)制過來。即雖然是往隊列頭部插值,但實際還是在尾部插完值后,分段移動進(jìn)行排序,最后組成了新數(shù)組。
addLast
則是直接把新元素存入tail
位置上,然后在重新計算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ò)容 }
特點:
- 不是線程安全的,在沒有外部處理同步的情況下,不支持多線程并發(fā)訪問。
- 禁止保存
null
元素。 - 作為棧使用時,可能比
Stack
快;作為隊列使用時, 比LinkedList
快。 - 時間復(fù)雜度時常數(shù)級別的。
總結(jié)
常見的隊列除了 ArrayQueue
、PriorityQuueue
和BlockingQueue
,還有一個可以當(dāng)作隊列的LinkedList
,關(guān)于它在上一節(jié)的 List 體系中有詳細(xì)的講解。
ArrayQueue
,更適用于當(dāng)作雙端隊列或棧結(jié)構(gòu)。Stack
已不推薦使用,建議使用LinkedList
或ArrayQueue
替代。PriorityQueue
用來處理優(yōu)先級,多了一個可自定義優(yōu)先級條件的能力。BlockingQueue
常用于實現(xiàn) 生產(chǎn)者/消費(fèi)者隊列,但線程安全需要外部自己去實現(xiàn)。
- 上面的幾種隊列,除了
LinkedList
,底層的數(shù)據(jù)結(jié)構(gòu)都是數(shù)組。 Queue
的有些實現(xiàn)沒有強(qiáng)制要求不允許存null
,但最好不要存null
。
到此這篇關(guān)于Java 集合框架 Queue 和 Stack 體系的文章就介紹到這了,更多相關(guān)Java 集合框架 內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
SpringMVC 跨重定向請求傳遞數(shù)據(jù)的方法實現(xiàn)
這篇文章主要介紹了SpringMVC 跨重定向請求傳遞數(shù)據(jù)的方法實現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-06-06Java中HashSet和HashMap的區(qū)別_動力節(jié)點Java學(xué)院整理
這篇文章主要介紹了Java中HashSet和HashMap的區(qū)別_動力節(jié)點Java學(xué)院整理,需要的朋友可以參考下2017-04-04Spring Security實現(xiàn)禁止用戶重復(fù)登陸的配置原理
這篇文章主要介紹了Spring Security實現(xiàn)禁止用戶重復(fù)登陸的配置原理,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2019-12-12關(guān)于java.util.Random的實現(xiàn)原理詳解
Java實用工具類庫中的類java.util.Random提供了產(chǎn)生各種類型隨機(jī)數(shù)的方法,下面這篇文章主要給大家介紹了關(guān)于java.util.Random實現(xiàn)原理的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),需要的朋友可以參考下。2017-08-08Easyui的combobox實現(xiàn)動態(tài)數(shù)據(jù)級聯(lián)效果
這篇文章主要介紹了Easyui的combobox實現(xiàn)動態(tài)數(shù)據(jù)級聯(lián)效果的相關(guān)資料,感興趣的小伙伴們可以參考一下2016-06-06Java?從json提取數(shù)組并轉(zhuǎn)換為list的操作方法
這篇文章主要介紹了Java?從json提取出數(shù)組并轉(zhuǎn)換為list,使用getJSONArray()獲取到j(luò)sonarray后,再將jsonArray轉(zhuǎn)換為字符串,最后將字符串解析為List列表,本文通過實例代碼給大家詳細(xì)講解,需要的朋友可以參考下2022-10-10詳解Java中IO字節(jié)流基本操作(復(fù)制文件)并測試性能
這篇文章主要介紹了Java中IO字節(jié)流基本操作(復(fù)制文件)并測試性能,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-04-04