目錄 一、前言 買房子最重要的是房屋格局！
如果買房子能接受地理位置、平米價(jià)格外，最重要的就是房屋格局。什么？丈母娘！你?????♂，出去！ 房屋的格局其實(shí)對(duì)應(yīng)的就是程序開發(fā)的根本，也就是數(shù)據(jù)結(jié)構(gòu)。有的土豪可以用錢換空間，房間格局更大，那沒錢的就只能選經(jīng)濟(jì)小空間節(jié)省錢。是不是很像不同的數(shù)據(jù)結(jié)構(gòu)，直接影響著是空間換時(shí)間，還是時(shí)間換空間。那么，再細(xì)看房間，如；客廳沙發(fā)坐人像散列表、上衛(wèi)生間像進(jìn)棧、廚房不大先進(jìn)后出像隊(duì)列、晚上各回各屋子像進(jìn)數(shù)組。所以你能在這個(gè)屋子生活的舒服，很大一部分取決于整個(gè)房間的布局。也同樣你能把程序?qū)懞?，很大的原因是因?yàn)閿?shù)據(jù)結(jié)構(gòu)定義的合理。
那么決定這程序開發(fā)基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)有哪些呢？
程序開發(fā)中數(shù)據(jù)結(jié)構(gòu)可以分為這八類；數(shù)組、鏈表、棧、隊(duì)列、散列表、樹、堆、圖。其中，數(shù)組、鏈表、散列表、樹是程序開發(fā)直接或者間接用到的最多的。相關(guān)的對(duì)應(yīng)實(shí)現(xiàn)類可以包括如下；
類型 實(shí)現(xiàn) 文章 數(shù)組 ArrayList ArrayList也這么多知識(shí)？一個(gè)指定位置插入就把謝飛機(jī)面暈了！ 鏈表 LinkedList LinkedList插入速度比ArrayList快？你確定嗎？ 樹 2-3樹、紅黑樹 看圖說話，講解2-3平衡樹「紅黑樹的前身」 散列表 HashMap HashMap核心知識(shí)，擾動(dòng)函數(shù)、負(fù)載因子、擴(kuò)容鏈表拆分，深度學(xué)習(xí) 棧 Stack 隊(duì)列 Queue、Deque
如上，除了棧和隊(duì)列外，小傅哥已經(jīng)編寫了非常細(xì)致的文章來介紹了其他數(shù)據(jù)結(jié)構(gòu)的核心知識(shí)和具體的實(shí)現(xiàn)應(yīng)用。 接下來就把剩下的棧和隊(duì)列在本章介紹完，其實(shí)這部分知識(shí)并不難了，有了以上對(duì)數(shù)組和鏈表的理解，其他的數(shù)據(jù)結(jié)構(gòu)基本都從這兩方面擴(kuò)展出來的。 本文涉及了較多的代碼和實(shí)踐驗(yàn)證圖稿，歡迎關(guān)注公眾號(hào)：bugstack蟲洞棧，回復(fù)下載得到一個(gè)鏈接打開后，找到ID：19??獲取！
二、面試題 謝飛機(jī)，飛機(jī)你旁邊這是？
「答」 ：啊，謝坦克，我弟弟。還沒畢業(yè)，想來看看大公司面試官的容顏。
「問」 ：飛機(jī)，上次把LinkedList都看了吧，那我問你哈。LinkedList可以當(dāng)隊(duì)列用嗎？
「答」 ：??？可以，可以吧！
「問」 ：那，數(shù)組能當(dāng)隊(duì)列用嗎？不能？對(duì)列有啥特點(diǎn)嗎？
「答」 ：隊(duì)列先進(jìn)先出，嗯，嗯。
「問」 ：還有嗎？了解延時(shí)隊(duì)列嗎？雙端隊(duì)列呢？
飛機(jī)拉著坦克的手出門了，還帶走了面試官送的一本《面經(jīng)手冊(cè)》，坦克對(duì)飛機(jī)說，基礎(chǔ)不牢，地動(dòng)山搖，我要好好學(xué)習(xí)。
三、數(shù)據(jù)結(jié)構(gòu) 把我們已經(jīng)掌握了的數(shù)組和鏈表立起來，就是棧和隊(duì)列了！
如圖，這一章節(jié)的數(shù)據(jù)結(jié)構(gòu)的知識(shí)點(diǎn)并不難，只要已經(jīng)學(xué)習(xí)過數(shù)組和鏈表，那么對(duì)于掌握其他數(shù)據(jù)結(jié)構(gòu)就已經(jīng)有了基礎(chǔ)，只不過對(duì)于數(shù)據(jù)的存放、讀取加了一些限定規(guī)則。尤其像鏈表這樣的數(shù)據(jù)結(jié)構(gòu)，只操作頭尾的效率是非常高的。
四、源碼學(xué)習(xí) 有時(shí)候不會(huì)反而不會(huì)犯錯(cuò)誤！怕就怕在只知道一知半解。
拋棄的不是棧這種數(shù)據(jù)結(jié)構(gòu)，而是Stack實(shí)現(xiàn)類，如果你還不了解就用到業(yè)務(wù)開發(fā)中，就很可能會(huì)影響系統(tǒng)性能。其實(shí)Stack這個(gè)棧已經(jīng)是不建議使用了，但是為什么不建議使用，我們可以通過使用和源碼分析了解下根本原因。
在學(xué)習(xí)之前先大概的了解下這樣的數(shù)據(jù)結(jié)構(gòu)，它很像羽毛球的擺放，是一種后進(jìn)先出隊(duì)列，如下；
@Test public void test_stack () new Stack<String>();"aaa" );"bbb" );"ccc" );"獲取最后一個(gè)元素：" + s.peek());"獲取最后一個(gè)元素：" + s.lastElement());"獲取最先放置元素：" + s.firstElement());"彈出一個(gè)元素[LIFO]：" + s.pop());"彈出一個(gè)元素[LIFO]：" + s.pop());"彈出一個(gè)元素[LIFO]：" + s.pop());例子是對(duì)Stack棧的使用，如果不運(yùn)行你能知道它的輸出結(jié)果嗎？
「測(cè)試結(jié)果：」
獲取最后一個(gè)元素：ccc0 看到測(cè)試結(jié)果，與你想的答案是否一致？
peek，是偷看的意思，就是看一下，不會(huì)彈出元素。滿足后進(jìn)先出的規(guī)則，它看的是最后放進(jìn)去的元素ccc。 lastElement、firstElement，字面意思的方法，獲取最后一個(gè)和獲取第一個(gè)元素。 pop，是隊(duì)列中彈出元素，彈出后也代表著要把屬于這個(gè)位置都元素清空，刪掉。 我們說Stack棧，這個(gè)實(shí)現(xiàn)類已經(jīng)不推薦使用了，需要從它的源碼上看。
/**@link Deque} interface and its implementations, which@code @author Jonathan Payne@since JDK1.0 public class Stack <E > extends Vector <E > s.push("aaa" );public synchronized void addElement (E obj) 1 );Stack 棧是在JDK1.0時(shí)代時(shí)，基于繼承Vector，實(shí)現(xiàn)的。本身Vector就是一個(gè)不推薦使用的類，主要在于它的一些操作方法鎖??(synchronized )的力度太粗，都是放到方法上。Stack 棧底層是使用Vector數(shù)組實(shí)現(xiàn)，在學(xué)習(xí)ArrayList時(shí)候我們知道，數(shù)組結(jié)構(gòu)在元素添加和擅長(zhǎng)需要通過System.arraycopy，進(jìn)行擴(kuò)容操作。而本身?xiàng)５奶攸c(diǎn)是首尾元素的操作，也不需要遍歷，使用數(shù)組結(jié)構(gòu)其實(shí)并不太理想。同時(shí)在這個(gè)方法的注釋上也明確標(biāo)出來，推薦使用Deque<Integer> stack = new ArrayDeque<Integer>();，雖然這也是數(shù)組結(jié)構(gòu)，但是它沒有粗粒度的鎖，同時(shí)可以申請(qǐng)指定空間并且在擴(kuò)容時(shí)操作時(shí)也要優(yōu)于Stack 。并且它還是一個(gè)雙端隊(duì)列，使用起來更靈活。 ArrayDeque 是基于數(shù)組實(shí)現(xiàn)的可動(dòng)態(tài)擴(kuò)容的雙端隊(duì)列，也就是說你可以在隊(duì)列的頭和尾同時(shí)插入和彈出元素。當(dāng)元素?cái)?shù)量超過數(shù)組初始化長(zhǎng)度時(shí)，則需要擴(kuò)容和遷移數(shù)據(jù)。
「數(shù)據(jù)結(jié)構(gòu)和操作」 ，如下；
從上圖我們可以了解到如下幾個(gè)知識(shí)點(diǎn)；
雙端隊(duì)列是基于數(shù)組實(shí)現(xiàn)，所以擴(kuò)容遷移數(shù)據(jù)操作。 push，像結(jié)尾插入、offerLast，向頭部插入，這樣兩端都滿足后進(jìn)先出。整體來看，雙端隊(duì)列，就是一個(gè)環(huán)形。所以擴(kuò)容后繼續(xù)插入元素也滿足后進(jìn)先出。 @Test public void test_ArrayDeque () new ArrayDeque<String>(1 );"a" );"b" );"c" );"d" );"e" );"f" );"g" );"h" ); // 這時(shí)候擴(kuò)容了 "i" );"j" );"數(shù)據(jù)出棧：" );while (!deque.isEmpty()) {" " );以上這部分代碼就是與上圖的展現(xiàn)是一致的，按照?qǐng)D中的分析我們看下輸出結(jié)果，如下；
數(shù)據(jù)出棧：0 i d c b a e f g h j，正好滿足了我們的說的數(shù)據(jù)出棧順序。可以參考上圖再進(jìn)行理解 ArrayDeque 這種雙端隊(duì)列是基于數(shù)組實(shí)現(xiàn)的，所以源碼上從初始化到數(shù)據(jù)入棧擴(kuò)容，都會(huì)有數(shù)組操作的痕跡。接下來我們就依次分析下。
new ArrayDeque<String>(1);，其實(shí)它的構(gòu)造函數(shù)初始化默認(rèn)也提供了幾個(gè)方法，比如你可以指定大小以及提供默認(rèn)元素。
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) {1 );2 );4 );8 );16 );if (initialCapacity < 0 ) // Too many elements, must back off 1 ;// Good luck allocating 2 ^ 30 element return initialCapacity;在初始化的過程中，它需要找到你當(dāng)前傳輸值最小的2的倍數(shù)的一個(gè)容量。這與HashMap的初始化過程相似。 deque.push("a");，ArrayDeque，提供了一個(gè) push 方法，這個(gè)方法與deque.offerFirst(“a”)，一致，因?yàn)樗鼈兊牡讓釉创a是一樣的，如下；
「addFirst：」
public void addFirst (E e) if (e == null )throw new NullPointerException();1 ) & (elements.length - 1 )] = e;if (head == tail)「addLast：」
public void addLast (E e) if (e == null )throw new NullPointerException();if ( (tail = (tail + 1 ) & (elements.length - 1 )) == head)這部分入棧元素，其實(shí)就是給數(shù)組賦值，知識(shí)點(diǎn)如下；
在addFirst()中，定位下標(biāo)，head = (head - 1) & (elements.length - 1)，因?yàn)槲覀兊臄?shù)組長(zhǎng)度是2^n的倍數(shù)，所以 2^n - 1 就是一個(gè)全是1的二進(jìn)制數(shù)，可以用于與運(yùn)算得出數(shù)組下標(biāo)。 同樣addLast()中，也使用了相同的方式定位下標(biāo)，只不過它是從0開始，往上增加。 最后，當(dāng)頭(head)與尾(tile)，數(shù)組則需要兩倍擴(kuò)容doubleCapacity。 下標(biāo)計(jì)算：head = (head - 1) & (elements.length - 1)：
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" );new Object[newCapacity];0 , r);0 , a, r, p);0 ;其實(shí)以上這部分源碼，就是進(jìn)行兩倍n << 1 擴(kuò)容，同時(shí)把兩端數(shù)據(jù)遷移進(jìn)新的數(shù)組，整個(gè)操作過程也與我們上圖對(duì)應(yīng)。為了更好的理解，我們單獨(dú)把這部分代碼做一些測(cè)試。
「測(cè)試代碼：」
@Test public void test_arraycopy () int head = 0 , tail = 0 ;new Object[8 ];1 ) & (elements.length - 1 )] = "a" ;1 ) & (elements.length - 1 )] = "b" ;1 ) & (elements.length - 1 )] = "c" ;1 ) & (elements.length - 1 )] = "d" ;"e" ;1 ) & (elements.length - 1 );"f" ;1 ) & (elements.length - 1 );"g" ;1 ) & (elements.length - 1 );"h" ;1 ) & (elements.length - 1 );"head：" + head);"tail：" + tail);int p = head;int n = elements.length;int r = n - p; // number of elements to the right of p // 輸出當(dāng)前的元素 // head == tail 擴(kuò)容 new Object[8 << 1 ];0 , r);0 , a, r, p);0 ;1 ) & (a.length - 1 )] = "i" ;以上的測(cè)試過程主要模擬了8個(gè)長(zhǎng)度的空間的數(shù)組，在進(jìn)行雙端隊(duì)列操作時(shí)數(shù)組擴(kuò)容，數(shù)據(jù)遷移操作，可以單獨(dú)運(yùn)行，測(cè)試結(jié)果如下；
head：4 4 "e" ,"f" ,"g" ,"h" ,"d" ,"c" ,"b" ,"a" ]"d" ,"c" ,"b" ,"a" ,null ,null ,null ,null ,null ,null ,null ,null ,null ,null ,null ,null ]"d" ,"c" ,"b" ,"a" ,"e" ,"f" ,"g" ,"h" ,null ,null ,null ,null ,null ,null ,null ,null ]"d" ,"c" ,"b" ,"a" ,"e" ,"f" ,"g" ,"h" ,"j" ,null ,null ,null ,null ,null ,null ,"i" ]0 從測(cè)試結(jié)果可以看到；
當(dāng)head與tail相等時(shí)，進(jìn)行擴(kuò)容操作。 第一次數(shù)據(jù)遷移，System.arraycopy(elements, p, a, 0, r);，「d、c、b、a」 ，落入新數(shù)組。 第二次數(shù)據(jù)遷移，System.arraycopy(elements, 0, a, r, p);，「e、f、g、h」 ，落入新數(shù)組。 最后再嘗試添加新的元素，i和j。每一次的輸出結(jié)果都可以看到整個(gè)雙端鏈路的變化。 Linkedlist天生就可以支持雙端隊(duì)列，而且從頭尾取數(shù)據(jù)也是它時(shí)間復(fù)雜度O(1)的。同時(shí)數(shù)據(jù)的插入和刪除也不需要像數(shù)組隊(duì)列那樣拷貝數(shù)據(jù)，雖然Linkedlist有這些優(yōu)點(diǎn)，但不能說ArrayDeque因?yàn)橛袛?shù)組復(fù)制性能比它低。
「Linkedlist，數(shù)據(jù)結(jié)構(gòu)」 ：
@Test public void test_Deque_LinkedList () new LinkedList<>();"a" );"b" );"c" );"d" );"e" );"f" );"g" );"h" ); "i" );"j" );"數(shù)據(jù)出棧：" );while (!deque.isEmpty()) {" " );「測(cè)試結(jié)果」 ：
數(shù)據(jù)出棧：0 測(cè)試結(jié)果上看與使用ArrayDeque是一樣的，功能上沒有差異。 「壓?！?/strong>：deque.push("a");、deque.offerFirst("a");
private void linkFirst (E e) final Node<E> f = first;final Node<E> newNode = new Node<>(null , e, f);if (f == null )else 「壓?！?/strong>：deque.offerLast("e");
void linkLast (E e) final Node<E> l = last;final Node<E> newNode = new Node<>(l, e, null );if (l == null )else linkFirst、linkLast，兩個(gè)方法分別是給鏈表的首尾節(jié)點(diǎn)插入元素，因?yàn)檫@是鏈表結(jié)構(gòu)，所以也不存在擴(kuò)容，只需要把雙向鏈路鏈接上即可。你是否有時(shí)候需要把一些數(shù)據(jù)存起來，倒計(jì)時(shí)到某個(gè)時(shí)刻在使用？
在Java的隊(duì)列數(shù)據(jù)結(jié)構(gòu)中，還有一種隊(duì)列是延時(shí)隊(duì)列，可以通過設(shè)定存放時(shí)間，依次輪訓(xùn)獲取。
「先寫一個(gè)Delayed的實(shí)現(xiàn)類」 ：
public class TestDelayed implements Delayed private String str;private long time;public TestDelayed (String str, long time, TimeUnit unit) this .str = str;this .time = System.currentTimeMillis() + (time > 0 ? unit.toMillis(time) : 0 );@Override public long getDelay (TimeUnit unit) return time - System.currentTimeMillis();@Override public int compareTo (Delayed o) long diff = this .time - work.time;if (diff <= 0 ) {return -1 ;else {return 1 ;public String getStr () return str;這個(gè)相當(dāng)于延時(shí)隊(duì)列的一個(gè)固定模版方法，通過這種方式來控制延時(shí)。 「案例測(cè)試」 ：
@Test public void test_DelayQueue () throws InterruptedException new DelayQueue<TestDelayed>();new TestDelayed("aaa" , 5 , TimeUnit.SECONDS));new TestDelayed("ccc" , 1 , TimeUnit.SECONDS));new TestDelayed("bbb" , 3 , TimeUnit.SECONDS));「測(cè)試結(jié)果」 ：
01 :44 :21.000 [main] INFO org.itstack.interview.test.ApiTest - ccc01 :44 :22.997 [main] INFO org.itstack.interview.test.ApiTest - bbb01 :44 :24.997 [main] INFO org.itstack.interview.test.ApiTest - aaa0 在案例測(cè)試中我們分別設(shè)定不同的休眠時(shí)間，1、3、5，TimeUnit.SECONDS。 測(cè)試結(jié)果分別在21、22、24，輸出了我們要的隊(duì)列結(jié)果。 隊(duì)列中的元素不會(huì)因?yàn)榇娣诺南群箜樞蚨鴮?dǎo)致輸出順序，它們是依賴于休眠時(shí)長(zhǎng)決定。 「入棧：」 ：delayQueue.offer(new TestDelayed("aaa", 5, TimeUnit.SECONDS));
public boolean offer (E e) if (e == null )throw new NullPointerException();int i = size;if (i >= queue.length)1 );1 ;if (i == 0 )0 ] = e;else return true ;private void siftUpUsingComparator (int k, E x) while (k > 0 ) {int parent = (k - 1 ) >>> 1 ;if (comparator.compare(x, (E) e) >= 0 )break ;關(guān)于數(shù)據(jù)存放還有 ReentrantLock 可重入鎖??，但暫時(shí)不是我們本章節(jié)數(shù)據(jù)結(jié)構(gòu)的重點(diǎn)，后面章節(jié)會(huì)介紹到。 DelayQueue 是基于數(shù)組實(shí)現(xiàn)的，所以可以動(dòng)態(tài)擴(kuò)容，另外它插入元素的順序并不影響最終的輸出順序。而元素的排序依賴于compareTo方法進(jìn)行排序，也就是休眠的時(shí)間長(zhǎng)短決定的。 同時(shí)只有實(shí)現(xiàn)了Delayed接口，才能存放元素。 「出?！?/strong>：delayQueue.take()
public E take () throws InterruptedException final ReentrantLock lock = this .lock;try {for (;;) {if (first == null )else {long delay = first.getDelay(NANOSECONDSif (delay <= 0 ) poll () ;null ; // don't retain ref while if (leader != null )else {try {finally {if (leader == thisThread)null ;finally {if (leader == null && q.peek() != null )這部分的代碼有點(diǎn)長(zhǎng)，主要是元素的獲取。DelayQueue 是 Leader-Followr 模式的變種，消費(fèi)者線程處于等待await時(shí)，總是等待最先休眠完成的元素。 這里會(huì)最小化的空等時(shí)間，提高線程利用率。數(shù)據(jù)結(jié)構(gòu)講完后，后面會(huì)有專門章節(jié)介紹 類型 實(shí)現(xiàn) 描述 Queue LinkedBlockingQueue 由鏈表結(jié)構(gòu)組成的有界阻塞隊(duì)列 Queue ArrayBlockingQueue 由數(shù)組結(jié)構(gòu)組成的有界阻塞隊(duì)列 Queue PriorityBlockingQueue 支持優(yōu)先級(jí)排序的無界阻塞隊(duì)列 Queue SynchronousQueue 不存儲(chǔ)元素的阻塞隊(duì)列 Queue LinkedTransferQueue 由鏈表結(jié)構(gòu)組成的無界阻塞隊(duì)列 Deque LinkedBlockingDeque 由鏈表結(jié)構(gòu)組成的雙向阻塞隊(duì)列 Deque ConcurrentLinkedDeque 由鏈表結(jié)構(gòu)組成的線程安全的雙向阻塞隊(duì)列
除了我們已經(jīng)講過的隊(duì)列以外，剩余的基本都是阻塞隊(duì)列，也就是上面這些。 在數(shù)據(jù)結(jié)構(gòu)方面基本沒有差異，只不過添加了相應(yīng)的阻塞功能和鎖的機(jī)制。 public class DataQueueStack private BlockingQueue<DataBean> dataQueue = null ;public DataQueueStack () //實(shí)例化隊(duì)列 new LinkedBlockingQueue<DataBean>(100 );/**@param dataBean@return public boolean doOfferData (DataBean dataBean) try {return dataQueue.offer(dataBean, 2 , TimeUnit.SECONDS);catch (InterruptedException e) {return false ;/**@return public DataBean doPollData () try {return dataQueue.poll(2 , TimeUnit.SECONDS);catch (InterruptedException e) {return null ;/**@return public int doGetQueueCount () return dataQueue.size();這是一個(gè)LinkedBlockingQueue隊(duì)列使用案例，一方面存儲(chǔ)數(shù)據(jù)，一方面從隊(duì)列中獲取進(jìn)行消費(fèi)。 因?yàn)檫@是一個(gè)阻塞隊(duì)列，所以在獲取元素的時(shí)候，如果隊(duì)列為空，會(huì)進(jìn)行阻塞。 LinkedBlockingQueue是一個(gè)阻塞隊(duì)列，內(nèi)部由兩個(gè)ReentrantLock來實(shí)現(xiàn)出入隊(duì)列的線程安全，由各自的Condition對(duì)象的await和signal來實(shí)現(xiàn)等待和喚醒功能。五、總結(jié) 關(guān)于棧和隊(duì)列的數(shù)據(jù)結(jié)構(gòu)方面到這里就介紹完了，另外這里還有一些關(guān)于阻塞隊(duì)列鎖??的應(yīng)用過程，到我們后面講鎖相關(guān)知識(shí)點(diǎn)，再重點(diǎn)介紹。 隊(duì)列結(jié)構(gòu)的設(shè)計(jì)非常適合某些需要LIFO或者FIFO的應(yīng)用場(chǎng)景，同時(shí)在隊(duì)列的數(shù)據(jù)結(jié)構(gòu)中也有雙端、延時(shí)和組合的功能類，使用起來也非常方便。 數(shù)據(jù)結(jié)構(gòu)方面的知識(shí)到本章節(jié)算是告一段落，如果有優(yōu)秀的內(nèi)容，后面還會(huì)繼續(xù)補(bǔ)充。再下一章節(jié)小傅哥()準(zhǔn)備給大家介紹，關(guān)于數(shù)據(jù)結(jié)構(gòu)中涉及的算法部分，這些主要來自于Collections類的實(shí)現(xiàn)部分。 
