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

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

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

Stack

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

包括常見的poppush操作、以及查看棧頂元素的方法、檢查棧是否為空的方法以及從棧頂向下進行搜索某個元素,并獲取該元素在棧內深度的方法。

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不強制拋出異常的。

 Throws exceptionReturns special value
Insertadd(e)offer(e)
Removeremove()poll()
Examineelement()peek()

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

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

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

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

Deque

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

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

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

Deque作為 LIFO 隊列使用時(棧結構),它也會有一些等價于Stack的方法:

其他特性

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

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

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

BlockingQueue

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

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

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

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

特點

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

PriorityQueue 優(yōu)先級隊列

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

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

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

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

特點

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

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

transient Object[] queue;

不是線程安全的。

擴容機制

優(yō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ù)組雙端隊列,是一種可調整大小的數(shù)組實現(xiàn),沒有容量限制。它會根據需要自動擴容。

繼承關系

public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>, Cloneable, Serializable
  • AbstractCollection:提供了一些集合接口能力的基本封裝。
  • 雙端隊列
  • 可通過Object.clone()方法快速復制
  • 支持序列化

底層實現(xiàn)

底層數(shù)據結構是一個數(shù)組:

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

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

擴容機制

 ? ?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右側的元素,然后再把左邊的復制過來。即雖然是往隊列頭部插值,但實際還是在尾部插完值后,分段移動進行排序,最后組成了新數(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ù)級別的。

總結

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

  • ArrayQueue,更適用于當作雙端隊列或棧結構。
  • Stack已不推薦使用,建議使用LinkedListArrayQueue替代。
  • PriorityQueue用來處理優(yōu)先級,多了一個可自定義優(yōu)先級條件的能力。
  • BlockingQueue常用于實現(xiàn) 生產者/消費者隊列,但線程安全需要外部自己去實現(xiàn)。
  • 上面的幾種隊列,除了LinkedList,底層的數(shù)據結構都是數(shù)組。
  • Queue的有些實現(xiàn)沒有強制要求不允許存null ,但最好不要存null 。

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

相關文章

最新評論