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

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

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

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

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

int8位

longint16位

shortint4位

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

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

數(shù)組

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

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

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

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

堆棧

堆棧也是一維圖形。

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

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

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

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

隊(duì)列

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

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

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

鏈表

鏈表也是一維圖形。

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

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

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

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

一、數(shù)組

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

數(shù)組可以根據(jù)下標(biāo)隨機(jī)訪問(wèn)，計(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ù)組中存儲(chǔ)的是 int 類型數(shù)據(jù)data_type_size 就為 4 個(gè)字節(jié)。數(shù)組要求連續(xù)的內(nèi)存空間，所以想在數(shù)組中刪除、插入一個(gè)數(shù)據(jù)，為了保證連續(xù)性，就需要做大量的數(shù)據(jù)搬移工作。

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

二、鏈表(Linked list)

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

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

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

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

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

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

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

三、棧

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

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

棧的應(yīng)用：

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

操作系統(tǒng)給每個(gè)線程分配了一塊獨(dú)立的內(nèi)存空間，用來(lái)存儲(chǔ)函數(shù)調(diào)用時(shí)的臨時(shí)變量。每進(jìn)入一個(gè)函數(shù)，就會(huì)將臨時(shí)變量作為一個(gè)棧幀入棧，當(dāng)被調(diào)用函數(shù)執(zhí)行完成，返回之后，將這個(gè)函數(shù)對(duì)應(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í)際上，編譯器就是通過(guò)兩個(gè)棧來(lái)實(shí)現(xiàn)的。其中一個(gè)保存操作數(shù)的棧，另一個(gè)是保存運(yùn)算符的棧。我們從左向右遍歷表達(dá)式，當(dāng)遇到數(shù)字，我們就直接壓入操作數(shù)棧;當(dāng)遇到運(yùn)算符，就與運(yùn)算符棧的棧頂元素進(jìn)行比較。如果比運(yùn)算符棧頂元素的優(yōu)先級(jí)高，就將當(dāng)前運(yùn)算符壓入棧;如果比運(yùn)算符棧頂元素的優(yōu)先級(jí)低或者相同，從運(yùn)算符棧中取棧頂運(yùn)算符，從操作數(shù)棧的棧頂取 2 個(gè)操作數(shù)，然后進(jìn)行計(jì)算，再把計(jì)算完的結(jié)果壓入操作數(shù)棧，繼續(xù)比較。

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

四、隊(duì)列

隊(duì)列的特點(diǎn)：先進(jìn)先出。主要包含兩個(gè)操作，入隊(duì)enqueue()，放一個(gè)數(shù)據(jù)到隊(duì)列尾部;出隊(duì) dequeue()，從隊(duì)列頭部取一個(gè)元素。用數(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í)候，會(huì)有數(shù)據(jù)搬移操作，要想解決數(shù)據(jù)搬移的問(wèn)題，我們就需要像環(huán)一樣的循環(huán)隊(duì)列。循環(huán)隊(duì)列當(dāng)隊(duì)滿時(shí)，(tail+1)%n=head。其中最后tail 指向的位置實(shí)際上是沒(méi)有存儲(chǔ)數(shù)據(jù)的。所以，循環(huán)隊(duì)列會(huì)浪費(fèi)一個(gè)數(shù)組的存儲(chǔ)空間。

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

五、遞歸

1、遞歸需要滿足的三個(gè)條件：

一個(gè)問(wèn)題的解可以分解為幾個(gè)子問(wèn)題的解

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

存在遞歸終止條件。

2、如何編寫(xiě)遞歸代碼?

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

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

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

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

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

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

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