file

前言

本文收錄于專輯：http://dwz.win/HjK，點(diǎn)擊解鎖更多數(shù)據(jù)結(jié)構(gòu)與算法的知識(shí)。

你好，我是彤哥，一個(gè)每天爬二十六層樓還不忘讀源碼的硬核男人。

數(shù)組、鏈表、隊(duì)列、棧，是數(shù)據(jù)結(jié)構(gòu)中最基礎(chǔ)的四大結(jié)構(gòu)，數(shù)組和鏈表更是基礎(chǔ)中的基礎(chǔ)，后續(xù)所有復(fù)雜的數(shù)據(jù)結(jié)構(gòu)都是在它們的基礎(chǔ)上演變而來的。

本節(jié)，我們就來重溫這四大結(jié)構(gòu)。

數(shù)組

關(guān)于數(shù)組，大家都比較熟悉了。

它是一種線性數(shù)據(jù)結(jié)構(gòu)，使用一組連續(xù)的內(nèi)存空間存儲(chǔ)一組具有相同類型的數(shù)據(jù)。

file

這個(gè)概念中有三個(gè)關(guān)鍵詞：線性、連續(xù)、相同類型。

線性，表示沒有分叉，任意元素的前后元素最多只有一個(gè)，同樣是線性結(jié)構(gòu)的還有鏈表、隊(duì)列等。

連續(xù)，它在內(nèi)存空間中的存儲(chǔ)是連續(xù)的，不間斷的，前后兩個(gè)元素緊挨著，不存在間隙。

相同類型，數(shù)組中存儲(chǔ)的元素的類型一定是相同的，當(dāng)然，在Java中，你可以使用Object代表所有類型，本質(zhì)上，它們依然是相同類型。

正是有了上面三個(gè)特性，才使得數(shù)組具有了隨機(jī)訪問的特性，那么，什么是隨機(jī)訪問呢？

簡(jiǎn)單點(diǎn)說，你可以通過下標(biāo)快速定位到數(shù)組中的元素，且時(shí)間復(fù)雜度是O(1)，它是怎么做到的呢？

我們知道，計(jì)算機(jī)中只有0和1，一切的一切都可以看作是0和1的各種組合，內(nèi)存也是一樣。

當(dāng)我們創(chuàng)建一個(gè)數(shù)組，比如int[] array = new int[]{2, 5, 8, 7};時(shí)，它其實(shí)返回的是這個(gè)數(shù)組在內(nèi)存中的位置（地址），我們知道，一個(gè)int類型占用4個(gè)字節(jié)，也就是32位的0或1，當(dāng)我們?cè)L問數(shù)組下標(biāo)為0的元素時(shí)，直接返回?cái)?shù)組地址處取32位轉(zhuǎn)成int即可，同樣地，當(dāng)我們?cè)L問數(shù)組下標(biāo)為1的元素時(shí)，返回?cái)?shù)組地址加上(32*1)的地址處取32位轉(zhuǎn)成int，依此類推。

file

這也是大部分語言中數(shù)組下標(biāo)從0開始的原因，試想如果下標(biāo)從1開始，那么，計(jì)算內(nèi)存地址的時(shí)候就變成了address + 32 * (i - 1)，這顯然會(huì)造成一定的性能損耗。

鏈表

鏈表，它也是一種線程數(shù)據(jù)結(jié)構(gòu)，與數(shù)組不同的是，它在內(nèi)存空間中不一定是順序存儲(chǔ)的，為了保證鏈表中元素的連續(xù)性，一般使用一個(gè)指針來找到下一個(gè)元素。

file

上圖是典型的單鏈表結(jié)構(gòu)，在單鏈表中，只有一個(gè)指向下一個(gè)元素的指針。

如果要用Java類來表示單鏈表中的元素節(jié)點(diǎn)的話，大概看起來像這樣子：

class Node {
    int value;
    Node next;
}

所以，鏈表不具有隨機(jī)訪問的特性，在鏈表中根據(jù)索引來查找元素只能從頭開始（單鏈表），它的時(shí)間復(fù)雜度是O(n)。

上面我們說的是單鏈表，如果在單鏈表的基礎(chǔ)上再增加一個(gè)前驅(qū)指針（指向前一個(gè)元素的指針），就變成了雙向鏈表。

file

Java中的LinkedList就是典型的雙向鏈表結(jié)構(gòu)，雙向鏈表既可以當(dāng)作隊(duì)列使用，又可以當(dāng)作棧來使用，非常方便。

如果在雙向鏈表的基礎(chǔ)上再增加HashMap的功能，就變成了LinkedHashMap了，咳咳，扯遠(yuǎn)了。

希望學(xué)習(xí)LinkedList和LinkedHashMap源碼解析的同學(xué)，可以關(guān)注我的公號(hào)主“彤哥讀源碼”。

這里提到了隊(duì)列，那么，什么是隊(duì)列呢？

隊(duì)列

所謂隊(duì)列，其實(shí)跟現(xiàn)實(shí)中的排隊(duì)是一樣的，其中的元素從一端進(jìn)入，從另一端出去，英文叫做：First In，F(xiàn)irst Out，簡(jiǎn)寫FIFO。

file

從這張圖，也可以看出來，實(shí)現(xiàn)隊(duì)列最簡(jiǎn)單的方式就是使用鏈表，把上圖中的箭頭倒過來即可。

file

入隊(duì)時(shí)，將元素加入到鏈表尾端，出隊(duì)時(shí)，將第一個(gè)元素刪除并將頭節(jié)點(diǎn)指向下一個(gè)節(jié)點(diǎn)即可。

讓我們來看看使用鏈表實(shí)現(xiàn)隊(duì)列的簡(jiǎn)單代碼實(shí)現(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;
        }
    }
}

是不是很簡(jiǎn)單呢？

那么，數(shù)組能不能實(shí)現(xiàn)隊(duì)列呢？

答案是肯定的，使用數(shù)組實(shí)現(xiàn)隊(duì)列有很多種方式，其中一種是使用兩個(gè)指針：入指針、出指針，它們分別指向下一個(gè)入隊(duì)列和下一個(gè)出隊(duì)列的位置。

入隊(duì)時(shí)，在入指針處放入元素，同時(shí)入指針后移。

出隊(duì)時(shí)，取出出指針處的元素返回，同時(shí)出指針后移。

當(dāng)指針到達(dá)數(shù)組末尾時(shí)，返回?cái)?shù)組開始的位置。

這樣就形成了一個(gè)可以循環(huán)使用的數(shù)組，俗稱環(huán)形數(shù)組。

file

此時(shí)，我們考慮一個(gè)問題，隊(duì)列空和隊(duì)列滿時(shí)，兩個(gè)指針都是指向同一個(gè)位置，似乎不太好處理。

其實(shí)，很簡(jiǎn)單，引入一個(gè)size變量標(biāo)識(shí)隊(duì)列中有多少個(gè)元素即可。

所以，這玩意兒要怎么實(shí)現(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ù)組實(shí)現(xiàn)的隊(duì)列，可以看到，與鏈表實(shí)現(xiàn)的隊(duì)列相比，它需要指定容量，這叫做有界隊(duì)列，如果需要使用數(shù)組實(shí)現(xiàn)無界隊(duì)列，則需要加入擴(kuò)容的機(jī)制，有興趣的同學(xué)可以自己實(shí)現(xiàn)看看。

下面，我們?cè)賮砜戳硪环N基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)——棧。

棧

棧，它是與隊(duì)列表現(xiàn)完全相反的數(shù)據(jù)結(jié)構(gòu)，它的元素是先進(jìn)的后出來，就像我們往一個(gè)杯子里面放東西一樣，先放進(jìn)去的放在最下面，只有把上面的東西拿出來后才能拿出下面壓著的東西，這種行為用英文叫做：First In，Last Out，簡(jiǎn)稱FILO。

file

棧，具有很多用處，計(jì)算機(jī)中很多處理都是通過棧這種數(shù)據(jù)結(jié)構(gòu)來進(jìn)行的，比如算術(shù)運(yùn)算，準(zhǔn)備兩個(gè)棧，一個(gè)棧存儲(chǔ)數(shù)字，一個(gè)棧存儲(chǔ)符號(hào)，從頭開始依次把字符壓入到這兩個(gè)棧中，當(dāng)遇到符號(hào)優(yōu)先級(jí)比棧頂元素低時(shí)，則取出棧頂符號(hào)，并從數(shù)字棧中取出兩個(gè)數(shù)字進(jìn)行運(yùn)算，運(yùn)算的結(jié)果再壓回?cái)?shù)字棧中，繼續(xù)以此運(yùn)行，當(dāng)所有字符都放入棧之后，依次從數(shù)字棧中取出兩個(gè)元素，并從符號(hào)棧中取出一個(gè)元素，進(jìn)行計(jì)算，結(jié)果壓回?cái)?shù)字棧，繼續(xù)以此運(yùn)行，直到符號(hào)棧為空，或者數(shù)字棧只剩下一個(gè)元素為止，彈出這個(gè)數(shù)字即為最后的結(jié)果。

以3 + 2 * 4 -1為例：

file

好了，關(guān)于棧，我們就簡(jiǎn)單介紹到這里，后面，我們還會(huì)大量遇到這個(gè)數(shù)據(jù)結(jié)構(gòu)。

后記

本節(jié)，我們一起重溫了數(shù)組、鏈表、隊(duì)列、棧這四種最基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)。

說起數(shù)組，我們看到，內(nèi)存本身就是一張大數(shù)組，它里面的元素就是0和1，那么，我們能不能直接操作這些0和1呢？

答案是肯定的。

下一節(jié)，我們將介紹位運(yùn)算，以及位圖這種數(shù)據(jù)結(jié)構(gòu)，彼時(shí)，我們將詳細(xì)介紹如何使用位圖來實(shí)現(xiàn)12306的搶票邏輯，關(guān)注我，及時(shí)獲取最新推文。

關(guān)注公號(hào)主“彤哥讀源碼”，解鎖更多源碼、基礎(chǔ)、架構(gòu)知識(shí)。