一、數(shù)組Array
典型應(yīng)用之斐波那契數(shù)列：前2個(gè)項(xiàng)都為1，從第三項(xiàng)開始，每一項(xiàng)都等于前2項(xiàng)之和，求斐波那契數(shù)列的前20項(xiàng)。
第一反應(yīng)是，用2個(gè)變量記錄前兩項(xiàng)，每次循環(huán)時(shí)更新這兩個(gè)變量并打印出來：
以上做法的問題是這2個(gè)變量僅作為臨時(shí)計(jì)算實(shí)用，結(jié)果的20個(gè)數(shù)并沒能保存下來
用數(shù)組的方式：目的是要把這20個(gè)數(shù)利用數(shù)組arr保存下來，并去掉numPrev1 和 numPrev2這兩個(gè)臨時(shí)的變量，利用數(shù)組下標(biāo)取值的方式計(jì)算出每一項(xiàng)：
數(shù)組的便利之處就在于【能只用一個(gè)變量存多個(gè)數(shù)據(jù)，不用創(chuàng)建很多變量來存每一項(xiàng)】，【利用數(shù)組下標(biāo)能很方便地取各個(gè)位置上的值】，對(duì)保存和處理那些【在順序上有規(guī)律的數(shù)據(jù)】來說非常實(shí)用。
二、棧Stack
棧是一個(gè)遵循后進(jìn)先出原則（LIFO）的有序集合，我們可以在數(shù)組的?任意位置?上操作元素，但棧限制了操作位置：只能在棧頂?進(jìn)行存取操作。棧被用來在編程語言中保存變量、方法的調(diào)用順序；保存訪問過的路徑，比如瀏覽器保存歷史記錄以回退到上一路徑等。
1.創(chuàng)建一個(gè)基于數(shù)組的棧
2.創(chuàng)建一個(gè)基于對(duì)象的棧
3.使用WeakMap保護(hù)私有屬性
使用以上兩種方法時(shí)，Stack的實(shí)例仍能訪問并修改_items屬性，用下劃線命名只是一種約定，依賴于開發(fā)者的常識(shí)，我們希望能保護(hù)內(nèi)部的元素，將_items作為私有屬性，限制實(shí)例對(duì)它的訪問：
WeakMap?的設(shè)計(jì)目的在于，有時(shí)我們想在某個(gè)對(duì)象上面存放一些數(shù)據(jù)，但是這會(huì)形成對(duì)于這個(gè)對(duì)象的引用，只要引用存在，垃圾回收?機(jī)制就不會(huì)釋放對(duì)象占用的內(nèi)存。 WeakMap 就是為了解決這個(gè)問題而誕生的，它的鍵名所引用的對(duì)象都是弱引用 ，只要所引用的對(duì)象的?其他引用?都被清除，垃圾回收機(jī)制就會(huì)釋放該對(duì)象所占用的內(nèi)存。也就是說，一旦不再需要，WeakMap 里面的鍵名對(duì)象和所對(duì)應(yīng)的鍵值對(duì)會(huì)自動(dòng)消失，不用手動(dòng)刪除引用
4.利用棧實(shí)現(xiàn)進(jìn)制轉(zhuǎn)換
將10進(jìn)制轉(zhuǎn)換為2~36的任意進(jìn)制，例如轉(zhuǎn)換為二進(jìn)制，將十進(jìn)制的數(shù)除以2，每次將余數(shù)壓入棧中，用商繼續(xù)除以2，直到商為0.
5.校驗(yàn)圓括號(hào)是否平衡
三、隊(duì)列（Queue）與雙端隊(duì)列（Deque:double-ended queue）
1.隊(duì)列
隊(duì)列是遵循先進(jìn)先出（FIFO，也成為先來先服務(wù)）原則的一組有序的項(xiàng)。它與棧非常類似，但棧?只在棧頂?進(jìn)行存取，而隊(duì)列是只能在 隊(duì)尾存，隊(duì)首取?：最新添加的元素必須排在末尾，最早被添加的元素最先得到服務(wù)。
常見的例子就是打印隊(duì)列，先來先打印，后來先排隊(duì)
經(jīng)典問題之擊鼓傳花
圍圈傳遞花，音樂停花在誰手里則誰淘汰，游戲里小朋友位置不變，傳遞花，用隊(duì)列模擬就是相當(dāng)于隊(duì)列首部放一束花不懂，為危險(xiǎn)位置，隊(duì)列首部的小朋友不斷跑到隊(duì)列尾，音樂停誰在隊(duì)首誰淘汰。
2.雙端隊(duì)列
雙端隊(duì)列，允許我們同時(shí)從?兩端進(jìn)行存取。
常見的例子是用雙端隊(duì)列存儲(chǔ)最近的幾次操作，最早的操作排在最前面，當(dāng)需要撤銷時(shí)從隊(duì)尾彈出最近的一次操作，就像棧一樣，后進(jìn)的先出；當(dāng)存儲(chǔ)的操作數(shù)達(dá)到設(shè)定時(shí)，有最新操作進(jìn)來就需要移除最早的操作，這個(gè)時(shí)候要從最前面移除，這時(shí)候就像隊(duì)列一樣，先進(jìn)的先出，所以雙端隊(duì)列就像棧和隊(duì)列相結(jié)合的一種數(shù)據(jù)結(jié)構(gòu)。
判斷字符串是否是回文（正讀和反讀相同）
用棧的思路是先反轉(zhuǎn)再對(duì)比原字符串
用雙端隊(duì)列的思路是同時(shí)從兩端取一個(gè)字符，對(duì)比是否相同
四、鏈表LinkedList
1. 鏈表LinkedList
鏈表能夠確定一組（不是保存一組，鏈表本身只存第一個(gè)元素head的引用）有序的元素集合。不同于數(shù)組的是，鏈表中的元素在內(nèi)存中并不是連續(xù)放置的，每個(gè)節(jié)點(diǎn)都存儲(chǔ)元素本身和指向下一個(gè)節(jié)點(diǎn)的指針，元素順序就是靠這些指向下一節(jié)點(diǎn)的指針來確定的。
在數(shù)組中插入或刪除元素的成本很高，因?yàn)樾枰苿?dòng)元素；
鏈表的好處就是添加或刪除時(shí)不需要移動(dòng)元素，只需要改變指針指向；
當(dāng)然，鏈表的缺點(diǎn)是額外保存了指針，而且因?yàn)樵卦趦?nèi)存中不是連續(xù)放置的，在訪問鏈表中間的元素時(shí)，只能從前往后迭代，無法像數(shù)組一樣能直接通過位置找到元素；
當(dāng)你需要添加和移除很多元素時(shí)，應(yīng)該首選鏈表而非數(shù)組。
2.雙向鏈表
雙向鏈表由于同時(shí)保存了前后兩個(gè)節(jié)點(diǎn)的引用，可以進(jìn)行前序和后序遍歷，普通鏈表只能從前往后。由于可以進(jìn)行雙向遍歷，當(dāng)確定了要操作的元素位置時(shí)，可以根據(jù)位置的前后來決定遍歷的方向，以減少迭代次數(shù)。
但是每個(gè)節(jié)點(diǎn)都要多分配一個(gè)指針存儲(chǔ)前一個(gè)結(jié)點(diǎn)引用，增刪時(shí)也需要維護(hù)前驅(qū)節(jié)點(diǎn)的指向。
3.循環(huán)鏈表
與鏈表的不同點(diǎn)在于，鏈表的最后一個(gè)元素的next不再指向undefined而是指向head節(jié)點(diǎn)；雙向鏈表的head節(jié)點(diǎn)的prev指向最后一個(gè)節(jié)點(diǎn)。
循環(huán)鏈表的優(yōu)點(diǎn)在于，從任意一個(gè)位置出發(fā)，都能遍歷整個(gè)鏈表；普通鏈表則只能從指定位置遍歷到尾部，或首部（如果是雙向鏈表的話）。
循環(huán)鏈表中沒有NULL指針，在遍歷時(shí)也可以減少判斷null的這個(gè)操作
五、集合Set
集合由一組無序且不相同的項(xiàng)組成。例如：N = {'A', 10, '哈', 4};
我們可以使用對(duì)象來模擬集合。將項(xiàng)作為對(duì)象的key以保證唯一性，增加項(xiàng)時(shí)則增加屬性，刪除項(xiàng)則刪除該屬性。
在進(jìn)行集合運(yùn)算時(shí)，可以用擴(kuò)展運(yùn)算符將集合轉(zhuǎn)化為數(shù)組來操作：
1.并集：new Set([...setA,...setB])
2.交集：new Set([...setA].filter(i=>setB.has(i)))
3.差集：new Set([...setA].filter(i=>!setB.has(i)))
六、字典Map和散列表HashMap(page 145)
集合是以[值，值]的形式存儲(chǔ)元素，字典以[鍵，值]的形式來存儲(chǔ)元素。字典也稱作映射、符號(hào)、關(guān)聯(lián)數(shù)組。
在字典中，我們將key轉(zhuǎn)化為字符串后，將value存在該字符串屬性中。
在散列表(哈希表)中，我們【將key轉(zhuǎn)化為字符串再使用每個(gè)字符的ASCII值轉(zhuǎn)成一個(gè)數(shù)字】，將value存在該數(shù)字位置。這個(gè)轉(zhuǎn)換函數(shù)是散列(hash)函數(shù)，散列函數(shù)的作用，就是給定一個(gè)鍵值，返回值在表中的位置。
1.處理散列表中的沖突
當(dāng)不同的key有相同的散列值時(shí)，會(huì)有沖突，因?yàn)椴煌闹祵?duì)應(yīng)同一個(gè)位置。
方法1：分離鏈接：為散列表的每一個(gè)位置創(chuàng)建一個(gè)鏈表，這樣一個(gè)位置上相當(dāng)于能存多個(gè)值了，不過存的時(shí)候需要既存值也存鍵，因?yàn)槿〉臅r(shí)候需要使用鍵來匹配鏈表中的值。
方法2：線性探查：當(dāng)添加元素時(shí)發(fā)現(xiàn)位置被占了，就從此位置向后迭代，以找一個(gè)空閑的位置并插入。在查找值時(shí)，如果要查找的位置上有值，并且所存的key與要查找的key相同，則返回，否則向后查找哈希值為當(dāng)前位置的元素并匹配key。當(dāng)要?jiǎng)h除某個(gè)值時(shí)，除了刪除那個(gè)位置上的值以外，還要將其他沖突的元素移動(dòng)至之前的位置 ，不產(chǎn)生空位置。
七、樹
一棵樹包含一系列存在父子關(guān)系的節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)都有一個(gè)父節(jié)點(diǎn)和0/多個(gè)子節(jié)點(diǎn)。子樹，由一個(gè)節(jié)點(diǎn)和它的后代構(gòu)成；
節(jié)點(diǎn)的一個(gè)屬性是深度，取決于祖先的數(shù)量；樹的高度取決于所有節(jié)點(diǎn)深度的最大值
在樹中，我們將節(jié)點(diǎn)稱為【鍵】
1.二叉樹與二叉搜索樹（BST）
二叉樹中的節(jié)點(diǎn)最多只能有2個(gè)子節(jié)點(diǎn)，二叉搜索樹只允許在左側(cè)節(jié)點(diǎn)存儲(chǔ)比父節(jié)點(diǎn)小的值，右側(cè)存儲(chǔ)大的值。
2.樹的遍歷
2.1 中序遍歷 （先訪問左節(jié)點(diǎn)——再訪問自身——再訪問右節(jié)點(diǎn)）
以從最小到最大的順序訪問所有節(jié)點(diǎn)；
2.2 前序遍歷(先訪問自身——再訪問左節(jié)點(diǎn)——再訪問右節(jié)點(diǎn))
2.3 后序遍歷(先訪問左節(jié)點(diǎn)——再訪問右節(jié)點(diǎn)——再訪問自身)
3.在樹中搜索值
4.移除樹中的節(jié)點(diǎn)
4.1 移除一個(gè)葉子節(jié)點(diǎn)
4.2 移除只有一個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)
4.3 移除有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)
