欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java?集合框架?Queue?和?Stack?體系

 更新時間:2022年06月16日 09:05:34   作者:??自動化BUG制造器????  
這篇文章主要介紹了Java?集合框架Queue和Stack體系,Stack?繼承自Vector,并拓展了五個允許將容器視為棧結(jié)構(gòu)的操作,Queue接口定義了隊列的能力,它繼承自Collection,更多相關(guān)內(nèi)容需要得小伙伴可以參考一下

Stack

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

包括常見的poppush操作、以及查看棧頂元素的方法、檢查棧是否為空的方法以及從棧頂向下進(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 exceptionReturns special value
Insertadd(e)offer(e)
Removeremove()poll()
Examineelement()peek()

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

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

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

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

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)hashequals方法,理由和Queue是一樣的。

BlockingQueue

BlockingQueueQueue接口的另一個重要子接口,它用來代表一個可阻塞的隊列。支持在檢索元素是,等待隊列變?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;

通過headtail作為索引來支持雙端隊列的特性。

擴(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已不推薦使用,建議使用LinkedListArrayQueue替代。
  • 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)文章

最新評論