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