隊(duì)列、堆棧段直、鏈表和數(shù)組這些概念傻傻分不清楚吃溅，經(jīng)過(guò)查閱資料稍微總結(jié)了一下。
數(shù)據(jù)結(jié)構(gòu)：描述數(shù)據(jù)元素邏輯關(guān)系的集合鸯檬。隊(duì)列就是一種先進(jìn)先出的邏輯結(jié)構(gòu)决侈，棧是一種先進(jìn)后出的邏輯結(jié)構(gòu)，家譜是一種樹(shù)形的邏輯結(jié)構(gòu)喧务！數(shù)組赖歌、鏈表、堆棧和隊(duì)列是最基本的數(shù)據(jù)結(jié)構(gòu)蹂楣。
數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)：描述數(shù)據(jù)在計(jì)算機(jī)中存儲(chǔ)方式俏站。常見(jiàn)的有兩種：順序存儲(chǔ)讯蒲，非順序存儲(chǔ)痊土。數(shù)組就是順序存儲(chǔ)，數(shù)據(jù)存儲(chǔ)的地址是連續(xù)的墨林；鏈表是非順序存儲(chǔ)赁酝，數(shù)據(jù)存儲(chǔ)的地址是不連續(xù)的。
-
隊(duì)列：隊(duì)列的特點(diǎn)是先入先出 (FIFO) 旭等，可以使用數(shù)組和鏈表來(lái)實(shí)現(xiàn)酌呆。
圖1.1 隊(duì)列
隊(duì)列只允許在隊(duì)尾添加數(shù)據(jù)，在隊(duì)頭刪除數(shù)據(jù)搔耕。但是可以查看隊(duì)頭和隊(duì)尾的數(shù)據(jù)隙袁。還有一種是雙端隊(duì)列，在兩端都可以插入和刪除：
圖1.2 雙端隊(duì)列 -
堆棧：這里討論的是數(shù)據(jù)結(jié)構(gòu)中的堆（heap)和棧（stack）弃榨，而不是內(nèi)存中的堆棧菩收。棧：是一種連續(xù)存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)，特點(diǎn)是存儲(chǔ)的數(shù)據(jù)先進(jìn)后出（FILO）鲸睛∧榷可以使用數(shù)組和鏈表來(lái)實(shí)現(xiàn)。
堆：是一棵完全二叉樹(shù)結(jié)構(gòu)官辈，特點(diǎn)是父節(jié)點(diǎn)的值大于（小于）兩個(gè)子節(jié)點(diǎn)的值（分別稱(chēng)為最大堆和最小堆）箱舞。它常用于管理算法執(zhí)行過(guò)程中的信息迁客，應(yīng)用場(chǎng)景包括堆排序轧坎，優(yōu)先隊(duì)列等博杖。
圖2.1 棧
-
鏈表： 鏈表是在非連續(xù)的內(nèi)存單元中保存數(shù)據(jù)渠啤，并且通過(guò)指針將各個(gè)內(nèi)存單元鏈接在一起锦爵，最右一個(gè)節(jié)點(diǎn)的指針指向 NULL 哟忍。鏈表不需要提前分配固定大小存儲(chǔ)空間限寞，當(dāng)需要存儲(chǔ)數(shù)據(jù)的時(shí)候分配一塊內(nèi)存并將這塊內(nèi)存插入鏈表中臼疫。
圖3.1 鏈表結(jié)構(gòu)
在鏈表中查找第 n 個(gè)數(shù)據(jù)以及查找指定的數(shù)據(jù)的時(shí)間復(fù)雜度是 O(N) ，但是插入和刪除數(shù)據(jù)的時(shí)間復(fù)雜度是 O(1) 胡桨，因?yàn)橹恍枰{(diào)整指針就可以：
圖3.2 添加元素
圖3.3 刪除元素
向上面這樣的鏈表結(jié)構(gòu)在插入和刪除的時(shí)候編程會(huì)比較困難官帘，因?yàn)樾枰涀‘?dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，這樣才能完成插入和刪除昧谊。為了簡(jiǎn)便通常使用帶有頭節(jié)點(diǎn)的鏈表：
圖3.4 帶有頭節(jié)點(diǎn)的單鏈表
上面的鏈表是單鏈表刽虹，此外還有雙鏈表，就是節(jié)點(diǎn)中包含指向下一個(gè)節(jié)點(diǎn)的指針和指向上一個(gè)節(jié)點(diǎn)的指針：
圖3.5 雙向鏈表
不帶有頭節(jié)點(diǎn)的雙向鏈表在插入和刪除數(shù)據(jù)的時(shí)候也不會(huì)出現(xiàn)單鏈表那樣的問(wèn)題呢诬。此外還有一種鏈表是循環(huán)鏈表涌哲，它是將雙向鏈表的頭尾相接：
圖3.6 雙向循環(huán)鏈表
向循環(huán)雙向鏈表和循環(huán)鏈表中插入或者從中刪除數(shù)據(jù)只是多移動(dòng)幾個(gè)指針。 -
數(shù)組： 組是使用一塊連續(xù)的內(nèi)存空間保存數(shù)據(jù)尚镰，保存的數(shù)據(jù)的個(gè)數(shù)在分配內(nèi)存的時(shí)候就是確定的阀圾。
在數(shù)組中訪(fǎng)問(wèn)數(shù)組中第 n 個(gè)數(shù)據(jù)的時(shí)間花費(fèi)是 O(1) ，查找一個(gè)指定的數(shù)據(jù)則是 O(N)狗唉。當(dāng)向數(shù)組中插入或者刪除數(shù)據(jù)的時(shí)候初烘，最好的情況是在數(shù)組的末尾進(jìn)行操作，時(shí)間復(fù)雜度是O(1) 分俯，但是最壞情況是插入或者刪除第一個(gè)數(shù)據(jù)肾筐，時(shí)間復(fù)雜度是 O(N) 。在任意位置插入或者刪除數(shù)據(jù)的時(shí)候缸剪，后面的數(shù)據(jù)全部需要移動(dòng)吗铐，移動(dòng)的數(shù)據(jù)還是和數(shù)據(jù)個(gè)數(shù)有關(guān)所以總體的時(shí)間復(fù)雜度仍然是 O(N) 。
圖4.1 數(shù)組插入元素
