重溫四大基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)：數(shù)組、鏈表、隊列和棧
關(guān)注公眾號“彤哥讀源碼”，解鎖更多源碼、基礎(chǔ)、架構(gòu)知識！
前言
本文收錄于專輯：http://dwz.win/HjK，點擊解鎖更多數(shù)據(jù)結(jié)構(gòu)與算法的知識。
你好，我是彤哥，一個每天爬二十六層樓還不忘讀源碼的硬核男人。
數(shù)組、鏈表、隊列、棧，是數(shù)據(jù)結(jié)構(gòu)中最基礎(chǔ)的四大結(jié)構(gòu)，數(shù)組和鏈表更是基礎(chǔ)中的基礎(chǔ)，后續(xù)所有復雜的數(shù)據(jù)結(jié)構(gòu)都是在它們的基礎(chǔ)上演變而來的。
本節(jié)，我們就來重溫這四大結(jié)構(gòu)。
數(shù)組
關(guān)于數(shù)組，大家都比較熟悉了。
它是一種線性數(shù)據(jù)結(jié)構(gòu)，使用一組連續(xù)的內(nèi)存空間存儲一組具有相同類型的數(shù)據(jù)。
這個概念中有三個關(guān)鍵詞：線性、連續(xù)、相同類型。
線性，表示沒有分叉，任意元素的前后元素最多只有一個，同樣是線性結(jié)構(gòu)的還有鏈表、隊列等。
連續(xù)，它在內(nèi)存空間中的存儲是連續(xù)的，不間斷的，前后兩個元素緊挨著，不存在間隙。
相同類型，數(shù)組中存儲的元素的類型一定是相同的，當然，在Java中，你可以使用Object代表所有類型，本質(zhì)上，它們依然是相同類型。
正是有了上面三個特性，才使得數(shù)組具有了隨機訪問的特性，那么，什么是隨機訪問呢？
簡單點說，你可以通過下標快速定位到數(shù)組中的元素，且時間復雜度是O(1)，它是怎么做到的呢？
我們知道，計算機中只有0和1，一切的一切都可以看作是0和1的各種組合，內(nèi)存也是一樣。
當我們創(chuàng)建一個數(shù)組，比如int[] array = new int[]{2, 5, 8, 7};時，它其實返回的是這個數(shù)組在內(nèi)存中的位置（地址），我們知道，一個int類型占用4個字節(jié)，也就是32位的0或1，當我們訪問數(shù)組下標為0的元素時，直接返回數(shù)組地址處取32位轉(zhuǎn)成int即可，同樣地，當我們訪問數(shù)組下標為1的元素時，返回數(shù)組地址加上(32*1)的地址處取32位轉(zhuǎn)成int，依此類推。
這也是大部分語言中數(shù)組下標從0開始的原因，試想如果下標從1開始，那么，計算內(nèi)存地址的時候就變成了address + 32 * (i - 1)，這顯然會造成一定的性能損耗。
鏈表
鏈表，它也是一種線程數(shù)據(jù)結(jié)構(gòu)，與數(shù)組不同的是，它在內(nèi)存空間中不一定是順序存儲的，為了保證鏈表中元素的連續(xù)性，一般使用一個指針來找到下一個元素。
上圖是典型的單鏈表結(jié)構(gòu)，在單鏈表中，只有一個指向下一個元素的指針。
如果要用Java類來表示單鏈表中的元素節(jié)點的話，大概看起來像這樣子：
class Node {
int value;
Node next;
}
所以，鏈表不具有隨機訪問的特性，在鏈表中根據(jù)索引來查找元素只能從頭開始（單鏈表），它的時間復雜度是O(n)。
上面我們說的是單鏈表，如果在單鏈表的基礎(chǔ)上再增加一個前驅(qū)指針（指向前一個元素的指針），就變成了雙向鏈表。
Java中的LinkedList就是典型的雙向鏈表結(jié)構(gòu)，雙向鏈表既可以當作隊列使用，又可以當作棧來使用，非常方便。
如果在雙向鏈表的基礎(chǔ)上再增加HashMap的功能，就變成了LinkedHashMap了，咳咳，扯遠了。
希望學習LinkedList和LinkedHashMap源碼解析的同學，可以關(guān)注我的公號主“彤哥讀源碼”。
這里提到了隊列，那么，什么是隊列呢？
隊列
所謂隊列，其實跟現(xiàn)實中的排隊是一樣的，其中的元素從一端進入，從另一端出去，英文叫做：First In，F(xiàn)irst Out，簡寫FIFO。
從這張圖，也可以看出來，實現(xiàn)隊列最簡單的方式就是使用鏈表，把上圖中的箭頭倒過來即可。
入隊時，將元素加入到鏈表尾端，出隊時，將第一個元素刪除并將頭節(jié)點指向下一個節(jié)點即可。
讓我們來看看使用鏈表實現(xiàn)隊列的簡單代碼實現(xiàn)：
public class LinkedQueue {
Node head;
Node tail;
void offer(Integer value) {
if (value == null) {
throw new NullPointerException();
}
Node node = new Node(value);
if (head == null) {
head = tail = node;
} else {
tail.next = node;
tail = node;
}
}
Integer poll() {
Node first = head;
if (first != null) {
head = first.next;
first.next = null;
return first.value;
} else {
return null;
}
}
static class Node {
int value;
Node next;
public Node(int value) {
this.value = value;
}
}
}
是不是很簡單呢？
那么，數(shù)組能不能實現(xiàn)隊列呢？
答案是肯定的，使用數(shù)組實現(xiàn)隊列有很多種方式，其中一種是使用兩個指針：入指針、出指針，它們分別指向下一個入隊列和下一個出隊列的位置。
入隊時，在入指針處放入元素，同時入指針后移。
出隊時，取出出指針處的元素返回，同時出指針后移。
當指針到達數(shù)組末尾時，返回數(shù)組開始的位置。
這樣就形成了一個可以循環(huán)使用的數(shù)組，俗稱環(huán)形數(shù)組。
此時，我們考慮一個問題，隊列空和隊列滿時，兩個指針都是指向同一個位置，似乎不太好處理。
其實，很簡單，引入一個size變量標識隊列中有多少個元素即可。
所以，這玩意兒要怎么實現(xiàn)呢？Show me the code!
public class ArrayQueue {
int[] array;
int offerIndex;
int pollIndex;
int size;
public ArrayQueue(int capacity) {
this.array = new int[capacity];
this.offerIndex = this.pollIndex = 0;
this.size = 0;
}
boolean offer(Integer value) {
if (value == null) {
throw new NullPointerException();
}
if (size == array.length) {
return false;
}
array[offerIndex] = value;
offerIndex = (offerIndex + 1) % array.length;
size++;
return true;
}
Integer poll() {
if (size == 0) {
return null;
}
int value = array[pollIndex];
pollIndex = (pollIndex + 1) % array.length;
size--;
return value;
}
}
OK，以上就是使用數(shù)組實現(xiàn)的隊列，可以看到，與鏈表實現(xiàn)的隊列相比，它需要指定容量，這叫做有界隊列，如果需要使用數(shù)組實現(xiàn)無界隊列，則需要加入擴容的機制，有興趣的同學可以自己實現(xiàn)看看。
下面，我們再來看另一種基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)——棧。
棧
棧，它是與隊列表現(xiàn)完全相反的數(shù)據(jù)結(jié)構(gòu)，它的元素是先進的后出來，就像我們往一個杯子里面放東西一樣，先放進去的放在最下面，只有把上面的東西拿出來后才能拿出下面壓著的東西，這種行為用英文叫做：First In，Last Out，簡稱FILO。
棧，具有很多用處，計算機中很多處理都是通過棧這種數(shù)據(jù)結(jié)構(gòu)來進行的，比如算術(shù)運算，準備兩個棧，一個棧存儲數(shù)字，一個棧存儲符號，從頭開始依次把字符壓入到這兩個棧中，當遇到符號優(yōu)先級比棧頂元素低時，則取出棧頂符號，并從數(shù)字棧中取出兩個數(shù)字進行運算，運算的結(jié)果再壓回數(shù)字棧中，繼續(xù)以此運行，當所有字符都放入棧之后，依次從數(shù)字棧中取出兩個元素，并從符號棧中取出一個元素，進行計算，結(jié)果壓回數(shù)字棧，繼續(xù)以此運行，直到符號棧為空，或者數(shù)字棧只剩下一個元素為止，彈出這個數(shù)字即為最后的結(jié)果。
以3 + 2 * 4 -1為例：
好了，關(guān)于棧，我們就簡單介紹到這里，后面，我們還會大量遇到這個數(shù)據(jù)結(jié)構(gòu)。
后記
本節(jié)，我們一起重溫了數(shù)組、鏈表、隊列、棧這四種最基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)。
說起數(shù)組，我們看到，內(nèi)存本身就是一張大數(shù)組，它里面的元素就是0和1，那么，我們能不能直接操作這些0和1呢？
答案是肯定的。
下一節(jié)，我們將介紹位運算，以及位圖這種數(shù)據(jù)結(jié)構(gòu)，彼時，我們將詳細介紹如何使用位圖來實現(xiàn)12306的搶票邏輯，關(guān)注我，及時獲取最新推文。
關(guān)注公號主“彤哥讀源碼”，解鎖更多源碼、基礎(chǔ)、架構(gòu)知識。