溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
問題
（1）什么是雙端隊列？
（2）ArrayDeque是怎么實現雙端隊列的？
（3）ArrayDeque是線程安全的嗎？
（4）ArrayDeque是有界的嗎？
簡介
雙端隊列是一種特殊的隊列，它的兩端都可以進出元素，故而得名雙端隊列。
ArrayDeque是一種以數組方式實現的雙端隊列，它是非線程安全的。
繼承體系
通過繼承體系可以看，ArrayDeque實現了Deque接口，Deque接口繼承自Queue接口，它是對Queue的一種增強。
public interface Deque<E> extends Queue<E> {
// 添加元素到隊列頭
void addFirst(E e);
// 添加元素到隊列尾
void addLast(E e);
// 添加元素到隊列頭
boolean offerFirst(E e);
// 添加元素到隊列尾
boolean offerLast(E e);
// 從隊列頭移除元素
E removeFirst();
// 從隊列尾移除元素
E removeLast();
// 從隊列頭移除元素
E pollFirst();
// 從隊列尾移除元素
E pollLast();
// 查看隊列頭元素
E getFirst();
// 查看隊列尾元素
E getLast();
// 查看隊列頭元素
E peekFirst();
// 查看隊列尾元素
E peekLast();
// 從隊列頭向后遍歷移除指定元素
boolean removeFirstOccurrence(Object o);
// 從隊列尾向前遍歷移除指定元素
boolean removeLastOccurrence(Object o);
// *** 隊列中的方法 ***
// 添加元素，等于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);
// 檢查是否包含某個元素
boolean contains(Object o);
// 元素個數
public int size();
// 迭代器
Iterator<E> iterator();
// 反向迭代器
Iterator<E> descendingIterator();
}
Deque中新增了以下幾類方法：
（1）*First，表示從隊列頭操作元素；
（2）*Last，表示從隊列尾操作元素；
（3）push(e)，pop()，以棧的方式操作元素的方法；
源碼分析
主要屬性
// 存儲元素的數組 transient Object[] elements; // non-private to simplify nested class access // 隊列頭位置 transient int head; // 隊列尾位置 transient int tail; // 最小初始容量 private static final int MIN_INITIAL_CAPACITY = 8;
從屬性我們可以看到，ArrayDeque使用數組存儲元素，并使用頭尾指針標識隊列的頭和尾，其最小容量是8。
主要構造方法
// 默認構造方法，初始容量為16
public ArrayDeque() {
elements = new Object[16];
}
// 指定元素個數初始化
public ArrayDeque(int numElements) {
allocateElements(numElements);
}
// 將集合c中的元素初始化到數組中
public ArrayDeque(Collection<? extends E> c) {
allocateElements(c.size());
addAll(c);
}
// 初始化數組
private void allocateElements(int numElements) {
elements = new Object[calculateSize(numElements)];
}
// 計算容量，這段代碼的邏輯是算出大于numElements的最接近的2的n次方且不小于8
// 比如，3算出來是8，9算出來是16，33算出來是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;
}
通過構造方法，我們知道默認初始容量是16，最小容量是8。
入隊
入隊有很多方法，我們這里主要分析兩個，addFirst(e)和addLast(e)。
// 從隊列頭入隊
public void addFirst(E e) {
// 不允許null元素
if (e == null)
throw new NullPointerException();
// 將head指針減1并與數組長度減1取模
// 這是為了防止數組到頭了邊界溢出
// 如果到頭了就從尾再向前
// 相當于循環利用數組
elements[head = (head - 1) & (elements.length - 1)] = e;
// 如果頭尾挨在一起了，就擴容
// 擴容規則也很簡單，直接兩倍
if (head == tail)
doubleCapacity();
}
// 從隊列尾入隊
public void addLast(E e) {
// 不允許null元素
if (e == null)
throw new NullPointerException();
// 在尾指針的位置放入元素
// 可以看到tail指針指向的是隊列最后一個元素的下一個位置
elements[tail] = e;
// tail指針加1，如果到數組尾了就從頭開始
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
（1）入隊有兩種方式，從隊列頭或者從隊列尾；
（2）如果容量不夠了，直接擴大為兩倍；
（3）通過取模的方式讓頭尾指針在數組范圍內循環；
（4）x & (len - 1) = x % len，使用&的方式更快；
擴容
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];
// 將舊數組head之后的元素拷貝到新數組中
System.arraycopy(elements, p, a, 0, r);
// 將舊數組下標0到head之間的元素拷貝到新數組中
System.arraycopy(elements, 0, a, r, p);
// 賦值為新數組
elements = a;
// head指向0，tail指向舊數組長度表示的位置
head = 0;
tail = n;
}
擴容這里遷移元素可能有點繞，請看下面這張圖來理解。
出隊
出隊同樣有很多方法，我們主要看兩個，pollFirst()和pollLast()。
// 從隊列頭出隊
public E pollFirst() {
int h = head;
@SuppressWarnings("unchecked")
// 取隊列頭元素
E result = (E) elements[h];
// 如果隊列為空，就返回null
if (result == null)
return null;
// 將隊列頭置為空
elements[h] = null; // Must null out slot
// 隊列頭指針右移一位
head = (h + 1) & (elements.length - 1);
// 返回取得的元素
return result;
}
// 從隊列尾出隊
public E pollLast() {
// 尾指針左移一位
int t = (tail - 1) & (elements.length - 1);
@SuppressWarnings("unchecked")
// 取當前尾指針處元素
E result = (E) elements[t];
// 如果隊列為空返回null
if (result == null)
return null;
// 將當前尾指針處置為空
elements[t] = null;
// tail指向新的尾指針處
tail = t;
// 返回取得的元素
return result;
}
（1）出隊有兩種方式，從隊列頭或者從隊列尾；
（2）通過取模的方式讓頭尾指針在數組范圍內循環；
（3）出隊之后沒有縮容哈哈^^
棧
前面我們介紹Deque的時候說過，Deque可以直接作為棧來使用，那么ArrayDeque是怎么實現的呢？
public void push(E e) {
addFirst(e);
}
public E pop() {
return removeFirst();
}
是不是很簡單，入棧出棧只要都操作隊列頭就可以了。
總結
（1）ArrayDeque是采用數組方式實現的雙端隊列；
（2）ArrayDeque的出隊入隊是通過頭尾指針循環利用數組實現的；
（3）ArrayDeque容量不足時是會擴容的，每次擴容容量增加一倍；
（4）ArrayDeque可以直接作為棧使用；
彩蛋
雙端隊列與雙重隊列？
雙端隊列（Deque）是指隊列的兩端都可以進出元素的隊列，里面存儲的是實實在在的元素。
雙重隊列（Dual Queue）是指一種隊列有兩種用途，里面的節點分為數據節點和非數據節點，它是LinkedTransferQueue使用的數據結構。
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持億速云。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
