真实的国产乱ⅩXXX66竹夫人,五月香六月婷婷激情综合,亚洲日本VA一区二区三区,亚洲精品一区二区三区麻豆

成都創(chuàng)新互聯(lián)網(wǎng)站制作重慶分公司

死磕java集合之ArrayDeque源碼分析-創(chuàng)新互聯(lián)

問(wèn)題

（1）什么是雙端隊(duì)列？

創(chuàng)新互聯(lián)建站專注于企業(yè)成都全網(wǎng)營(yíng)銷、網(wǎng)站重做改版、河津網(wǎng)站定制設(shè)計(jì)、自適應(yīng)品牌網(wǎng)站建設(shè)、成都h5網(wǎng)站建設(shè)、商城網(wǎng)站建設(shè)、集團(tuán)公司官網(wǎng)建設(shè)、成都外貿(mào)網(wǎng)站建設(shè)公司、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁(yè)設(shè)計(jì)等建站業(yè)務(wù)，價(jià)格優(yōu)惠性價(jià)比高，為河津等各大城市提供網(wǎng)站開(kāi)發(fā)制作服務(wù)。

（2）ArrayDeque是怎么實(shí)現(xiàn)雙端隊(duì)列的？

（3）ArrayDeque是線程安全的嗎？

（4）ArrayDeque是有界的嗎？

簡(jiǎn)介

雙端隊(duì)列是一種特殊的隊(duì)列，它的兩端都可以進(jìn)出元素，故而得名雙端隊(duì)列。

ArrayDeque是一種以數(shù)組方式實(shí)現(xiàn)的雙端隊(duì)列，它是非線程安全的。

繼承體系

死磕 java集合之ArrayDeque源碼分析

通過(guò)繼承體系可以看，ArrayDeque實(shí)現(xiàn)了Deque接口，Deque接口繼承自Queue接口，它是對(duì)Queue的一種增強(qiáng)。


public interface Deque extends Queue {
    // 添加元素到隊(duì)列頭
    void addFirst(E e);
    // 添加元素到隊(duì)列尾
    void addLast(E e);
    // 添加元素到隊(duì)列頭
    boolean offerFirst(E e);
    // 添加元素到隊(duì)列尾
    boolean offerLast(E e);
    // 從隊(duì)列頭移除元素
    E removeFirst();
    // 從隊(duì)列尾移除元素
    E removeLast();
    // 從隊(duì)列頭移除元素
    E pollFirst();
    // 從隊(duì)列尾移除元素
    E pollLast();
    // 查看隊(duì)列頭元素
    E getFirst();
    // 查看隊(duì)列尾元素
    E getLast();
    // 查看隊(duì)列頭元素
    E peekFirst();
    // 查看隊(duì)列尾元素
    E peekLast();
    // 從隊(duì)列頭向后遍歷移除指定元素
    boolean removeFirstOccurrence(Object o);
    // 從隊(duì)列尾向前遍歷移除指定元素
    boolean removeLastOccurrence(Object o);

    // *** 隊(duì)列中的方法 ***

    // 添加元素，等于addLast(e)
    boolean add(E e);
     // 添加元素，等于offerLast(e)
    boolean offer(E e);
    // 移除元素，等于removeFirst()
    E remove();
    // 移除元素，等于pollFirst()
    E poll();
    // 查看元素，等于getFirst()
    E element();
    // 查看元素，等于peekFirst()
    E peek();

    // *** 棧方法 ***

    // 入棧，等于addFirst(e)
    void push(E e);
    // 出棧，等于removeFirst()
    E pop();

    // *** Collection中的方法 ***

    // 刪除指定元素，等于removeFirstOccurrence(o)
    boolean remove(Object o);
    // 檢查是否包含某個(gè)元素
    boolean contains(Object o);
    // 元素個(gè)數(shù)
    public int size();
    // 迭代器
    Iterator iterator();
    // 反向迭代器
    Iterator descendingIterator();
}

Deque中新增了以下幾類方法：

（1）*First，表示從隊(duì)列頭操作元素；

（2）*Last，表示從隊(duì)列尾操作元素；

（3）push(e)，pop()，以棧的方式操作元素的方法；

源碼分析

主要屬性

// 存儲(chǔ)元素的數(shù)組
transient Object[] elements; // non-private to simplify nested class access
// 隊(duì)列頭位置
transient int head;
// 隊(duì)列尾位置
transient int tail;
// 最小初始容量
private static final int MIN_INITIAL_CAPACITY = 8;

從屬性我們可以看到，ArrayDeque使用數(shù)組存儲(chǔ)元素，并使用頭尾指針標(biāo)識(shí)隊(duì)列的頭和尾，其最小容量是8。

主要構(gòu)造方法

// 默認(rèn)構(gòu)造方法，初始容量為16
public ArrayDeque() {
    elements = new Object[16];
}
// 指定元素個(gè)數(shù)初始化
public ArrayDeque(int numElements) {
    allocateElements(numElements);
}
// 將集合c中的元素初始化到數(shù)組中
public ArrayDeque(Collection c) {
    allocateElements(c.size());
    addAll(c);
}
// 初始化數(shù)組
private void allocateElements(int numElements) {
    elements = new Object[calculateSize(numElements)];
}
// 計(jì)算容量，這段代碼的邏輯是算出大于numElements的最接近的2的n次方且不小于8
// 比如，3算出來(lái)是8，9算出來(lái)是16，33算出來(lái)是64
private static int calculateSize(int numElements) {
    int initialCapacity = MIN_INITIAL_CAPACITY;
    // Find the best power of two to hold elements.
    // Tests "<=" because arrays aren't kept full.
    if (numElements >= initialCapacity) {
        initialCapacity = numElements;
        initialCapacity |= (initialCapacity >>>  1);
        initialCapacity |= (initialCapacity >>>  2);
        initialCapacity |= (initialCapacity >>>  4);
        initialCapacity |= (initialCapacity >>>  8);
        initialCapacity |= (initialCapacity >>> 16);
        initialCapacity++;

        if (initialCapacity < 0)   // Too many elements, must back off
            initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
    }
    return initialCapacity;
}

通過(guò)構(gòu)造方法，我們知道默認(rèn)初始容量是16，最小容量是8。

入隊(duì)

入隊(duì)有很多方法，我們這里主要分析兩個(gè)，addFirst(e)和addLast(e)。

// 從隊(duì)列頭入隊(duì)
public void addFirst(E e) {
    // 不允許null元素
    if (e == null)
        throw new NullPointerException();
    // 將head指針減1并與數(shù)組長(zhǎng)度減1取模
    // 這是為了防止數(shù)組到頭了邊界溢出
    // 如果到頭了就從尾再向前
    // 相當(dāng)于循環(huán)利用數(shù)組
    elements[head = (head - 1) & (elements.length - 1)] = e;
    // 如果頭尾挨在一起了，就擴(kuò)容
    // 擴(kuò)容規(guī)則也很簡(jiǎn)單，直接兩倍
    if (head == tail)
        doubleCapacity();
}
// 從隊(duì)列尾入隊(duì)
public void addLast(E e) {
    // 不允許null元素
    if (e == null)
        throw new NullPointerException();
    // 在尾指針的位置放入元素
    // 可以看到tail指針指向的是隊(duì)列最后一個(gè)元素的下一個(gè)位置
    elements[tail] = e;
    // tail指針加1，如果到數(shù)組尾了就從頭開(kāi)始
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)
        doubleCapacity();
}

（1）入隊(duì)有兩種方式，從隊(duì)列頭或者從隊(duì)列尾；

（2）如果容量不夠了，直接擴(kuò)大為兩倍；

（3）通過(guò)取模的方式讓頭尾指針在數(shù)組范圍內(nèi)循環(huán)；

（4）x & (len - 1) = x % len，使用&的方式更快；

擴(kuò)容

private void doubleCapacity() {
    assert head == tail;
    // 頭指針的位置
    int p = head;
    // 舊數(shù)組長(zhǎng)度
    int n = elements.length;
    // 頭指針離數(shù)組尾的距離
    int r = n - p; // number of elements to the right of p
    // 新長(zhǎng)度為舊長(zhǎng)度的兩倍
    int newCapacity = n << 1;
    // 判斷是否溢出
    if (newCapacity < 0)
        throw new IllegalStateException("Sorry, deque too big");
    // 新建新數(shù)組
    Object[] a = new Object[newCapacity];
    // 將舊數(shù)組head之后的元素拷貝到新數(shù)組中
    System.arraycopy(elements, p, a, 0, r);
    // 將舊數(shù)組下標(biāo)0到head之間的元素拷貝到新數(shù)組中
    System.arraycopy(elements, 0, a, r, p);
    // 賦值為新數(shù)組
    elements = a;
    // head指向0，tail指向舊數(shù)組長(zhǎng)度表示的位置
    head = 0;
    tail = n;
}

擴(kuò)容這里遷移元素可能有點(diǎn)繞，請(qǐng)看下面這張圖來(lái)理解。

死磕 java集合之ArrayDeque源碼分析

出隊(duì)

出隊(duì)同樣有很多方法，我們主要看兩個(gè)，pollFirst()和pollLast()。

// 從隊(duì)列頭出隊(duì)
public E pollFirst() {
    int h = head;
    @SuppressWarnings("unchecked")
    // 取隊(duì)列頭元素
    E result = (E) elements[h];
    // 如果隊(duì)列為空，就返回null
    if (result == null)
        return null;
    // 將隊(duì)列頭置為空
    elements[h] = null;     // Must null out slot
    // 隊(duì)列頭指針右移一位
    head = (h + 1) & (elements.length - 1);
    // 返回取得的元素
    return result;
}
// 從隊(duì)列尾出隊(duì)
public E pollLast() {
    // 尾指針左移一位
    int t = (tail - 1) & (elements.length - 1);
    @SuppressWarnings("unchecked")
    // 取當(dāng)前尾指針處元素
    E result = (E) elements[t];
    // 如果隊(duì)列為空返回null
    if (result == null)
        return null;
    // 將當(dāng)前尾指針處置為空
    elements[t] = null;
    // tail指向新的尾指針處
    tail = t;
    // 返回取得的元素
    return result;
}

（1）出隊(duì)有兩種方式，從隊(duì)列頭或者從隊(duì)列尾；

（2）通過(guò)取模的方式讓頭尾指針在數(shù)組范圍內(nèi)循環(huán)；

（3）出隊(duì)之后沒(méi)有縮容哈哈^^

棧

前面我們介紹Deque的時(shí)候說(shuō)過(guò)，Deque可以直接作為棧來(lái)使用，那么ArrayDeque是怎么實(shí)現(xiàn)的呢？

public void push(E e) {
    addFirst(e);
}

public E pop() {
    return removeFirst();
}

是不是很簡(jiǎn)單，入棧出棧只要都操作隊(duì)列頭就可以了。

總結(jié)

（1）ArrayDeque是采用數(shù)組方式實(shí)現(xiàn)的雙端隊(duì)列；

（2）ArrayDeque的出隊(duì)入隊(duì)是通過(guò)頭尾指針循環(huán)利用數(shù)組實(shí)現(xiàn)的；

（3）ArrayDeque容量不足時(shí)是會(huì)擴(kuò)容的，每次擴(kuò)容容量增加一倍；

（4）ArrayDeque可以直接作為棧使用；

彩蛋

雙端隊(duì)列與雙重隊(duì)列？

雙端隊(duì)列（Deque）是指隊(duì)列的兩端都可以進(jìn)出元素的隊(duì)列，里面存儲(chǔ)的是實(shí)實(shí)在在的元素。

雙重隊(duì)列（Dual Queue）是指一種隊(duì)列有兩種用途，里面的節(jié)點(diǎn)分為數(shù)據(jù)節(jié)點(diǎn)和非數(shù)據(jù)節(jié)點(diǎn)，它是LinkedTransferQueue使用的數(shù)據(jù)結(jié)構(gòu)。

還記得LinkedTransferQueue嗎？點(diǎn)擊鏈接直達(dá)【死磕 java集合之LinkedTransferQueue源碼分析】。

歡迎關(guān)注我的公眾號(hào)“彤哥讀源碼”，查看更多源碼系列文章, 與彤哥一起暢游源碼的海洋。

死磕 java集合之ArrayDeque源碼分析

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。


標(biāo)題名稱：死磕java集合之ArrayDeque源碼分析-創(chuàng)新互聯(lián)
URL網(wǎng)址：http://weahome.cn/article/ccsejs.html

其他資訊

在線咨詢

微信咨詢

電話咨詢

028-86922220（工作日）

18980820575（7×24）

提交需求

返回頂部