您好,登錄后才能下訂單哦!
問題
(1)什么是雙端隊(duì)列?
(2)ArrayDeque是怎么實(shí)現(xiàn)雙端隊(duì)列的?
(3)ArrayDeque是線程安全的嗎?
(4)ArrayDeque是有界的嗎?
簡介
雙端隊(duì)列是一種特殊的隊(duì)列,它的兩端都可以進(jìn)出元素,故而得名雙端隊(duì)列。
ArrayDeque是一種以數(shù)組方式實(shí)現(xiàn)的雙端隊(duì)列,它是非線程安全的。
繼承體系
通過繼承體系可以看,ArrayDeque實(shí)現(xiàn)了Deque接口,Deque接口繼承自Queue接口,它是對Queue的一種增強(qiáng)。
public interface Deque<E> extends Queue<E> { // 添加元素到隊(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<E> iterator(); // 反向迭代器 Iterator<E> 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<? extends E> c) { allocateElements(c.size()); addAll(c); } // 初始化數(shù)組 private void allocateElements(int numElements) { elements = new Object[calculateSize(numElements)]; } // 計(jì)算容量,這段代碼的邏輯是算出大于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; }
通過構(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ù)組長度減1取模 // 這是為了防止數(shù)組到頭了邊界溢出 // 如果到頭了就從尾再向前 // 相當(dāng)于循環(huán)利用數(shù)組 elements[head = (head - 1) & (elements.length - 1)] = e; // 如果頭尾挨在一起了,就擴(kuò)容 // 擴(kuò)容規(guī)則也很簡單,直接兩倍 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ù)組尾了就從頭開始 if ( (tail = (tail + 1) & (elements.length - 1)) == head) doubleCapacity(); }
(1)入隊(duì)有兩種方式,從隊(duì)列頭或者從隊(duì)列尾;
(2)如果容量不夠了,直接擴(kuò)大為兩倍;
(3)通過取模的方式讓頭尾指針在數(shù)組范圍內(nèi)循環(huán);
(4)x & (len - 1) = x % len,使用&的方式更快;
擴(kuò)容
private void doubleCapacity() { assert head == tail; // 頭指針的位置 int p = head; // 舊數(shù)組長度 int n = elements.length; // 頭指針離數(shù)組尾的距離 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"); // 新建新數(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ù)組長度表示的位置 head = 0; tail = n; }
擴(kuò)容這里遷移元素可能有點(diǎn)繞,請看下面這張圖來理解。
出隊(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)通過取模的方式讓頭尾指針在數(shù)組范圍內(nèi)循環(huán);
(3)出隊(duì)之后沒有縮容哈哈^^
棧
前面我們介紹Deque的時(shí)候說過,Deque可以直接作為棧來使用,那么ArrayDeque是怎么實(shí)現(xiàn)的呢?
public void push(E e) { addFirst(e); } public E pop() { return removeFirst(); }
是不是很簡單,入棧出棧只要都操作隊(duì)列頭就可以了。
總結(jié)
(1)ArrayDeque是采用數(shù)組方式實(shí)現(xiàn)的雙端隊(duì)列;
(2)ArrayDeque的出隊(duì)入隊(duì)是通過頭尾指針循環(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)。
以上就是本文的全部內(nèi)容,希望對大家的學(xué)習(xí)有所幫助,也希望大家多多支持億速云。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。