一文搞懂?dāng)?shù)組、堆棧與鏈表、隊(duì)列的區(qū)別

線性表就是數(shù)據(jù)排成像一條線一樣的結(jié)構(gòu)。每個線性表上的數(shù)據(jù)最多只有前和后兩個方向。其實(shí)除了數(shù)組，鏈表、隊(duì)列、棧等也是線性表結(jié)構(gòu)。而與它相對立的概念是非線性表，比如二叉樹、堆、圖等。

所謂的數(shù)據(jù)結(jié)構(gòu)就是表示數(shù)據(jù)之間的關(guān)系。這些數(shù)據(jù)結(jié)構(gòu)中的每一個元素都是緊密相連的，不能有空隙。

數(shù)據(jù)結(jié)構(gòu)是抽象的概念，沒有語言之別，就像是設(shè)計(jì)模式一樣，是一種抽象的思想，用任何語言的代碼都能構(gòu)建出來。而我們的python中的字符串，列表，字典，元祖，集合都是基本數(shù)據(jù)類型，他們是依附于語言存在的，不同的語言有不同的基本數(shù)據(jù)類型。

在二進(jìn)制下的數(shù)據(jù)類型所占的位數(shù)：

int8位

longint16位

shortint4位

char---assic8位;gbk16位;utf-8，24位;unicode32位;

float--占4個字節(jié)，即32位，具體分布如下：1bit(符號位，即正負(fù)號)，8bit(指數(shù)位)，23bit(尾數(shù)位)。

數(shù)組

數(shù)組是一維圖形。

數(shù)組是定長，所謂的定長就是在創(chuàng)建之初就需要告訴解釋器它的長度，而我們的列表是不定長的，所謂的不定長就是我們創(chuàng)建了一個列表，我們?nèi)庋劭吹降目赡苓@個列表只有3個元素或者我們就干脆創(chuàng)建一個空列表，但是在內(nèi)部實(shí)現(xiàn)的時候解釋器給這個列表一個初始長度，假設(shè)這個長度是20，然后我們對這個我們所創(chuàng)建了列表進(jìn)行增刪改查的時候，這個列表的長度就會發(fā)生變化，然后發(fā)生變化的過程中，系統(tǒng)內(nèi)部就把這個列表一開始的所有數(shù)據(jù)給拷貝下來，然后根據(jù)你增刪改查的結(jié)果對列表進(jìn)行擴(kuò)大或者縮小。

數(shù)組中的數(shù)據(jù)類型必須要保持一致，一個數(shù)組中只能存一種數(shù)據(jù)類型，所謂的數(shù)據(jù)類型就是：整數(shù)int，小數(shù)float，字符串char這些類型。列表里面存的數(shù)據(jù)類型是不一樣的，但是在解釋器內(nèi)部，這些個不同的數(shù)據(jù)類型都是被python實(shí)例化出來的一個個對象，然后在列表中存的都是這些對象的一個個的地址指針。

數(shù)組可以通過索引取值，時間復(fù)雜度是O1.(O1這個時間復(fù)雜度跟數(shù)組的規(guī)模是沒有差別的，不論是多長的數(shù)組，它的時間復(fù)雜度都是O1.而On的話，這個n可以是任何常數(shù)，比如可以是20、300、5000等等，都遠(yuǎn)遠(yuǎn)沒有O1快)它的取值原理是因?yàn)閿?shù)組存的是同一種數(shù)據(jù)類型，而數(shù)據(jù)類型都是固定長度的，所以可以通過長度取值。比如這里有一個數(shù)組A，它存的都是整數(shù)類型，第一個元素的地址假設(shè)是0110，那么我們要獲取這個A數(shù)組中的第4個元素，只需要通過第一個元素的地址加上(4-1)*8=24，即0110+24=0134，就是第4個元素的地址，然后就能直接很快地拿到這個元素，內(nèi)存地址都是連續(xù)的。這就是它取值快的地方。但是它有弊端，我們的數(shù)組中每一個元素都是緊挨著的，打一個比方，算盤，它的每一根柱子上都是一串算珠，我們把這個算盤立起來的時候，算珠都會垂直落到底部，我們假設(shè)拆掉一個柱子上的一個算珠，那么這個算珠上面的算珠會依次降落到下一個算珠的位置上，然后這個柱子的算珠整體高度就會下降一個算珠的高度，或者我們增加一個算珠，我們所增加的這個算珠上面的所有算珠都會上升到上一個算珠的位置上，因?yàn)樗阒橹g不能有空隙，要一個個緊緊挨著。我們的數(shù)組就類似這樣的情況，當(dāng)我們要在數(shù)組中插入一個值的時候，我們所插入的這個位置，后面的所有元素都要依次往后挪一個元素的位置，就像我們給算盤增加算珠一樣，在增加的位置上的每一上面的算珠都要往上挪一個算珠的位置;同理，如果要刪除一個數(shù)組中的元素的話，那么這個被刪除的元素的位置就空出來了，然后因?yàn)槲覀兊臄?shù)組里面的元素都是緊挨著的，所以這個被刪除的元素后面的元素都會依次往前挪一個元素的位置，就像我們的算盤上取掉一個算珠，這個算珠的上面每一個算珠都要往下降一個算珠的位置，就是這個道理。所以如果刪除或者是插入一個數(shù)組中的中間元素的話，它后面的所有元素都需要挪動位置，這里就沒有取值那么便捷了，時間復(fù)雜度就會增加，但是，如果是增加或者是刪除最后一個元素就不會涉及到其他元素的操作，這里就不存在時間復(fù)雜度的增加問題了。

堆棧

堆棧也是一維圖形。

我們想象一下一個裝羽毛球的球桶，它的直徑就是羽毛球的羽毛那一端所圍成的圓形的直徑，這樣一個個羽毛球放進(jìn)去剛好卡在桶壁內(nèi)，沒有多余空隙，以免晃動中產(chǎn)生摩擦帶來不必要的損耗。假設(shè)這個球桶只有一個口，另一段是封死的，這個時候假設(shè)這個球桶是空的，我們把羽毛球一個個依次放進(jìn)去的時候，只能從這個口放進(jìn)去，然后也只能從這個口拿出來，也就是先進(jìn)后出，后進(jìn)先出。

在這個堆棧中我們只研究棧頂，這個棧頂?shù)奈恢镁褪俏覀兊亩褩Ｕw高度。也就是說在這個羽毛球桶中，最上面的這個羽毛球在刻度4處，這個球桶中就有4個球，此時我們拿出去一個球，這個球桶中最上面的這個球就在3這個刻度上了，此時球桶中就有3個球，這個球桶中最上面的球就被我們標(biāo)記為棧頂。實(shí)現(xiàn)一個堆棧的方式就是一個變量+一個數(shù)組。這個變量指向這個數(shù)組中的最后一個元素，比如這個數(shù)組中有8個元素，這個變量指向8，這個堆棧就有8個元素，棧頂就是8。

堆棧組成可以用列表實(shí)現(xiàn)，也可以用數(shù)組實(shí)現(xiàn)，如果用列表的話就可以存放不同的數(shù)據(jù)類型。

需要附上堆棧的代碼實(shí)現(xiàn)，以上僅僅是概念性的原理。代碼需要有一個類，類里面有兩個方法，入棧和出棧，入棧時需要考慮到棧的大小，棧滿時不可入，同時，出棧也要考慮到棧空時不能出。

隊(duì)列

隊(duì)列也是一維圖形。

隊(duì)列不同于堆棧有一個口，進(jìn)出都是它(我們叫做出入耦合)，隊(duì)列不一樣，它有2個口，一個單獨(dú)的出口，一個單獨(dú)的入口(我們叫做出入分離)。同向時如果出入口重合，則隊(duì)列為空，反向時如果出入口重合，則隊(duì)列為滿。我們在隊(duì)列問題中，僅僅考慮兩個點(diǎn)，入口和出口，而且這兩個要分開考慮，不能想得過于復(fù)雜。所以按照堆棧的實(shí)現(xiàn)方式，隊(duì)列的實(shí)現(xiàn)就是兩個變量+數(shù)組。

隊(duì)列同上，用數(shù)組和列表都能實(shí)現(xiàn)。

鏈表

鏈表也是一維圖形。

鏈表中的每一個元素都會標(biāo)記一個尾部指向，這個指向是指向下一個元素，然后每一個元素之間用尾部彼此相連，所謂鏈表就像鐵鏈一樣，彼此之間緊密相扣，形成一條鏈條。鏈表是沒有大小的，不同于數(shù)組，堆棧和隊(duì)列。

雙向鏈表就是不僅會標(biāo)記尾部指向，還會有頭部指向，一條鏈表中的任意一個元素拿出來，它有頭部指向，指向上一個元素，還有尾部指向，指向下一個元素，這就是雙向鏈表。

鏈表分單向和雙向，兩種。彼此之間不能混合，單向和單向組合，雙向和雙向組合。循環(huán)鏈表，就是尾項(xiàng)指向頭項(xiàng)，首位相連形成一個圓，就是循環(huán)鏈表，也就沒有頭尾之分。

鏈表的增刪改查，跟數(shù)組比起來就要快很多了，比如我們要刪除一個鏈表中的元素，就需要把這個元素的上一個元素的尾部指向指向到這個元素的下一個元素的尾部指向即可，就像是把這個鏈條上的一個鏈環(huán)拿掉就把這個鏈條分成了兩截，然后把這個斷開的部分重新鏈接上即可，比如是abcd的鏈條，把c拿掉，就讓b和d鏈接上即可，不會涉及到更多元素的操作，比起數(shù)組就方便很多。但是有一點(diǎn)弊端，就是數(shù)組取值，是通過索引取值，會很快，而鏈表如果要取值，就需要從鏈頭開始找依次去找到那個值然后返回，這樣就會慢很多，如果剛好要找的那個值是鏈尾，那么就需要遍歷整個鏈表。時間復(fù)雜度是O(n)。

一、數(shù)組

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

數(shù)組可以根據(jù)下標(biāo)隨機(jī)訪問，計(jì)算機(jī)根據(jù)尋址公式可以快速查找下標(biāo)為i的元素：

a[i]_address = base_address + i() * data_type_size

即下標(biāo)為i的元素地址=數(shù)組首地址+下標(biāo) i 乘以 數(shù)據(jù)類型大小。例如數(shù)組中存儲的是 int 類型數(shù)據(jù)data_type_size 就為 4 個字節(jié)。數(shù)組要求連續(xù)的內(nèi)存空間，所以想在數(shù)組中刪除、插入一個數(shù)據(jù)，為了保證連續(xù)性，就需要做大量的數(shù)據(jù)搬移工作。

小結(jié)：數(shù)組用一塊連續(xù)的內(nèi)存空間，來存儲相同類型的一組數(shù)據(jù)，最大的特點(diǎn)就是支持隨機(jī)訪問O(1)，但插入、刪除操作比較低效，平均情況時間復(fù)雜度為 O(n)。

二、鏈表(Linked list)

鏈表不需要像數(shù)組一樣需要一塊連續(xù)的內(nèi)存空間，它通過“指針”將一組零散的內(nèi)存塊串聯(lián)起來使用。

常見的鏈表結(jié)構(gòu)有：單鏈表、雙向鏈表和循環(huán)鏈表。通常第一個結(jié)點(diǎn)叫作頭結(jié)點(diǎn)，把最后一個結(jié)點(diǎn)叫作尾結(jié)點(diǎn)，頭結(jié)點(diǎn)用來記錄鏈表的基地址。

1、單鏈表：每個鏈表的結(jié)點(diǎn)除了存儲數(shù)據(jù)之外，還有一個后繼指針 next記錄下一個結(jié)點(diǎn)的地址。尾結(jié)點(diǎn)指向一個空地址 NULL。

2、循環(huán)鏈表：循環(huán)鏈表是特殊的單鏈表。循環(huán)鏈表的尾結(jié)點(diǎn)指針是指向鏈表的頭結(jié)點(diǎn)。

3、雙向鏈表：每個結(jié)點(diǎn)不止有一個后繼指針 next 指向后面的結(jié)點(diǎn)，還有一個前驅(qū)指針 prev 指向前面的結(jié)點(diǎn)。

針對鏈表的插入和刪除操作，我們只需要考慮相鄰結(jié)點(diǎn)的指針改變，所以對應(yīng)的時間復(fù)雜度是 O(1)。因?yàn)殒湵碇械臄?shù)據(jù)并非連續(xù)存儲的，想隨機(jī)訪問第 k 個元素，無法像數(shù)組那樣通過尋址公式就能直接計(jì)算出對應(yīng)的內(nèi)存地址，而是需要根據(jù)指針一個結(jié)點(diǎn)一個結(jié)點(diǎn)地依次遍歷，直到找到相應(yīng)的結(jié)點(diǎn)。

小結(jié)：鏈表是內(nèi)存不連續(xù)的，通過“指針”將零散的內(nèi)存塊串聯(lián)起來使用的。鏈表的插入和刪除操作比較快都快O(1)，隨機(jī)訪問的性能沒有數(shù)組好O(n)，編寫代碼時注意邊界條件，對插入第一個結(jié)點(diǎn)和刪除最后一個結(jié)點(diǎn)的情況進(jìn)行特殊處理。

三、棧

棧的特點(diǎn)：后進(jìn)先出。棧主要包含兩個操作，入棧 push()和出棧 pop()，也就是在棧頂插入一個數(shù)據(jù)和從棧頂刪除一個數(shù)據(jù)。

數(shù)組實(shí)現(xiàn)的棧，我們叫作順序棧，支持動態(tài)擴(kuò)容。用鏈表實(shí)現(xiàn)的棧，我們叫作鏈?zhǔn)綏！?

棧的應(yīng)用：

1、函數(shù)調(diào)用棧

操作系統(tǒng)給每個線程分配了一塊獨(dú)立的內(nèi)存空間，用來存儲函數(shù)調(diào)用時的臨時變量。每進(jìn)入一個函數(shù)，就會將臨時變量作為一個棧幀入棧，當(dāng)被調(diào)用函數(shù)執(zhí)行完成，返回之后，將這個函數(shù)對應(yīng)的棧幀出棧

eg:

int main() {

int a = 1;

int ret = 0;

int res = 0;

ret = add(3, 5);

res = a + ret;

printf("%d", res);

reuturn 0;

}

int add(int x, int y) {

int sum = 0;

sum = x + y;

return sum;

}

函數(shù)棧里出棧、入棧的操作：

2、表達(dá)式求值

eg：3+5*8-6。

實(shí)際上，編譯器就是通過兩個棧來實(shí)現(xiàn)的。其中一個保存操作數(shù)的棧，另一個是保存運(yùn)算符的棧。我們從左向右遍歷表達(dá)式，當(dāng)遇到數(shù)字，我們就直接壓入操作數(shù)棧;當(dāng)遇到運(yùn)算符，就與運(yùn)算符棧的棧頂元素進(jìn)行比較。如果比運(yùn)算符棧頂元素的優(yōu)先級高，就將當(dāng)前運(yùn)算符壓入棧;如果比運(yùn)算符棧頂元素的優(yōu)先級低或者相同，從運(yùn)算符棧中取棧頂運(yùn)算符，從操作數(shù)棧的棧頂取 2 個操作數(shù)，然后進(jìn)行計(jì)算，再把計(jì)算完的結(jié)果壓入操作數(shù)棧，繼續(xù)比較。

小結(jié)：棧是一種“操作受限”的線性表，只允許在一端插入和刪除數(shù)據(jù)即入棧和出棧，只需要一個棧頂指針。后進(jìn)者先出，先進(jìn)者后出。典型應(yīng)用場景函數(shù)調(diào)用，表達(dá)式求值也需要理解。入棧、出棧的時間復(fù)雜度都為 O(1)。

四、隊(duì)列

隊(duì)列的特點(diǎn)：先進(jìn)先出。主要包含兩個操作，入隊(duì)enqueue()，放一個數(shù)據(jù)到隊(duì)列尾部;出隊(duì) dequeue()，從隊(duì)列頭部取一個元素。用數(shù)組實(shí)現(xiàn)的隊(duì)列叫作順序隊(duì)列，用鏈表實(shí)現(xiàn)的隊(duì)列叫作鏈?zhǔn)疥?duì)列。

隊(duì)空和隊(duì)滿的判定條件：隊(duì)滿的判斷條件是 tail == n，隊(duì)空的判斷條件是 head == tail。

在數(shù)組實(shí)現(xiàn)隊(duì)列的時候，會有數(shù)據(jù)搬移操作，要想解決數(shù)據(jù)搬移的問題，我們就需要像環(huán)一樣的循環(huán)隊(duì)列。循環(huán)隊(duì)列當(dāng)隊(duì)滿時，(tail+1)%n=head。其中最后tail 指向的位置實(shí)際上是沒有存儲數(shù)據(jù)的。所以，循環(huán)隊(duì)列會浪費(fèi)一個數(shù)組的存儲空間。

小結(jié)：隊(duì)列也是一種“操作受限”的線性表，先進(jìn)者先出，對應(yīng)入隊(duì)和出隊(duì)，隊(duì)列需要兩個指針：一個是 head 指針，指向隊(duì)頭;一個是 tail 指針，指向隊(duì)尾。注意隊(duì)空和隊(duì)滿的判定條件，典型應(yīng)用場景如循環(huán)隊(duì)列、阻塞隊(duì)列、并發(fā)隊(duì)列、線程池。

五、遞歸

1、遞歸需要滿足的三個條件：

一個問題的解可以分解為幾個子問題的解

這個問題與分解之后的子問題，除了數(shù)據(jù)規(guī)模不同，求解思路完全一樣。

存在遞歸終止條件。

2、如何編寫遞歸代碼?

最關(guān)鍵的是寫出遞推公式，找到終止條件。

3、為什么遞歸代碼容易造成堆棧溢出呢?

函數(shù)調(diào)用會使用棧來保存臨時變量。每調(diào)用一個函數(shù)，都會將臨時變量封裝為棧幀壓入內(nèi)存棧，等函數(shù)執(zhí)行完成返回時，才出棧。系統(tǒng)?；蛘咛摂M機(jī)?？臻g一般都不大。如果遞歸求解的數(shù)據(jù)規(guī)模很大，調(diào)用層次很深，一直壓入棧，就會有堆棧溢出的風(fēng)險。

4、那如何避免出現(xiàn)堆棧溢出呢?

我們可以通過在代碼中限制遞歸調(diào)用的最大深度的方式來解決這個問題。

為了避免重復(fù)計(jì)算，我們可以通過一個數(shù)據(jù)結(jié)構(gòu)(比如散列表)來保存已經(jīng)求解過的 f(k)。當(dāng)遞歸調(diào)用到 f(k)時，先看下是否已經(jīng)求解過了。如果是，則直接從散列表中取值返回，不需要重復(fù)計(jì)算。

小結(jié)：遞歸不算數(shù)據(jù)結(jié)構(gòu)但是一種應(yīng)用非常廣泛的編程技巧，注意使用遞歸需滿足的條件以及如何找出遞歸公式和終止條件，避免死循環(huán)，編碼時注意避免堆棧溢出和重復(fù)計(jì)算。 典型應(yīng)用如 DFS 深度優(yōu)先搜索、前中后序二叉樹遍歷，斐波那契數(shù)列。