今天晚上還有課，就先搞明白一個(gè)知識(shí)點(diǎn)吧，學(xué)到技術(shù)才是王道呀！
鏈表：
當(dāng)需要存儲(chǔ)多個(gè)相同數(shù)據(jù)類型的時(shí)候，可以使用數(shù)組存儲(chǔ)，數(shù)組可以通過下標(biāo)直接訪問，但數(shù)組有個(gè)缺點(diǎn)就是無法動(dòng)態(tài)的插入或刪除其中的元素（特別是操作第一個(gè)位置上的元素），而鏈表彌補(bǔ)了這個(gè)缺陷，對(duì)于元素的插入和刪除操作是很方便的，不過訪問元素的“性能”就差很多了。
所謂單鏈表，即只有一個(gè)指針，指向下一個(gè)元素（結(jié)點(diǎn)）的地址，只要知道單鏈表的首地址，就可以遍歷整個(gè)鏈表了。由于鏈表結(jié)點(diǎn)是在堆區(qū)動(dòng)態(tài)申請(qǐng)的，其地址并不是連續(xù)的，因此無法進(jìn)行隨機(jī)訪問，只有通過前一結(jié)點(diǎn)的next指針才能定位到下一個(gè)結(jié)點(diǎn)的指針。
單鏈表只能向后遍歷，不能逆序遍歷，所以有了使用更廣泛的雙鏈表。即結(jié)點(diǎn)多了一個(gè)存儲(chǔ)前一個(gè)結(jié)點(diǎn)地址的prev指針。雙鏈表可以雙向遍歷，但也只能按順序訪問。
隊(duì)列：
隊(duì)列就像我們平時(shí)排隊(duì)一樣，按照數(shù)據(jù)到達(dá)的順序進(jìn)行排隊(duì)，每次新插入的一個(gè)結(jié)點(diǎn)排在隊(duì)尾（注意是隊(duì)尾哦），刪除一個(gè)結(jié)點(diǎn)只能從頭才能出隊(duì)。簡言之，對(duì)元素的到達(dá)順序，按照“先進(jìn)先出”的原則。由于隊(duì)列頻繁的插入和刪除，一般為了高效，使用固定長度的數(shù)組實(shí)現(xiàn)，并且可循環(huán)使用數(shù)組空間，在操作之前要判斷處理的隊(duì)列是否已滿或?yàn)榭?。如果要?jiǎng)討B(tài)長度，可以用鏈表實(shí)現(xiàn)，只要同時(shí)記住鏈表的首地址（隊(duì)頭front）和尾地址（隊(duì)尾rear）。
棧：棧的特點(diǎn)正好與隊(duì)列相反，按照數(shù)據(jù)進(jìn)棧的逆序出棧，即“先進(jìn)后出”，每次入棧將元素放在棧頂，出棧時(shí)也只能從棧頂出棧，與隊(duì)列類似，一般用定長數(shù)組存儲(chǔ)棧元素，而不是動(dòng)態(tài)的申請(qǐng)結(jié)點(diǎn)空間。進(jìn)棧一般被叫做壓棧，出棧被叫做彈棧。
由于壓棧彈棧都在棧頂，所以只需要一個(gè)size字段存儲(chǔ)當(dāng)前棧的大小，初始化size為0，每次壓棧時(shí)，size+1，注意棧是否已滿,彈棧則size-1。
什么是樹（平衡二叉樹、二叉排序樹、B樹、B+樹、R樹、紅黑樹）？敲重點(diǎn)！
為什么會(huì)有樹這個(gè)概念呢？因?yàn)橐延械臄?shù)據(jù)結(jié)構(gòu)（數(shù)組、鏈表）不能很好的平衡靜態(tài)操作和動(dòng)態(tài)操作的時(shí)間開銷。
時(shí)間復(fù)雜度 數(shù)組 鏈表
靜態(tài)操作（查找） O(1) O(n)
動(dòng)態(tài)操作（插入、刪除）O(n) O(1)
對(duì)于樹這種數(shù)據(jù)結(jié)構(gòu)而言，最顯著的特點(diǎn)就是有且只能有一個(gè)根節(jié)點(diǎn)（空樹除外），每個(gè)節(jié)點(diǎn)可以有多個(gè)子結(jié)點(diǎn)，除了根結(jié)點(diǎn)，其他結(jié)點(diǎn)只能有一個(gè)父結(jié)點(diǎn)。樹的種類繁多，一般談?wù)摰淖疃嗟氖嵌鏄?，每個(gè)結(jié)點(diǎn)有不超過兩個(gè)的子結(jié)點(diǎn)。（最多兩個(gè)叉子唄）
平衡二叉樹 & 二叉排序樹
二叉排序樹（Binary Search Tree，BST，也叫二叉搜索樹），構(gòu)造一棵二叉排序樹也很簡單，大于根節(jié)點(diǎn)的放在根節(jié)點(diǎn)的右子樹上，小于根結(jié)點(diǎn)的放在根結(jié)點(diǎn)的左子樹上（等于根結(jié)點(diǎn)的視情況而定）。如果寫程序的話，可以采用遞歸的方式，而且由于不存在重疊子問題的情況，因此遞歸的性能已經(jīng)足夠好(不考慮棧溢出的情況)。類似中序遍歷。
二叉排序樹在通常情況下可以達(dá)到O(lgn)的靜態(tài)、動(dòng)態(tài)操作的時(shí)間復(fù)雜度，但是存在一種特殊情況，若輸入的本來就是有序的，這時(shí)二叉樹就退化成了鏈表。（注意轉(zhuǎn)換）為了消除二叉樹對(duì)于輸入的敏感特性，引入了平衡二叉樹（AVL），事實(shí)上平衡二叉樹應(yīng)該叫平衡二叉排序樹也合理。平衡二叉樹只要保證每個(gè)節(jié)點(diǎn)左子樹和右子樹的高度差小于等于1就可以了。
B樹 & B+樹
操作系統(tǒng)中，我們應(yīng)該學(xué)過寄存器的訪問速度和容量是此消彼漲的，速度最快的當(dāng)屬CPU上的寄存器，然后就是cache（高速緩存），然后是內(nèi)存，再就是外部磁盤等，當(dāng)兩個(gè)處在不同層級(jí)的存儲(chǔ)器（比如內(nèi)存和外部磁盤）交換數(shù)據(jù)時(shí)，我們稱之為I/O。而I/O相當(dāng)耗時(shí)，要盡量避免使用。
B樹（B-Tree，“B-樹”這種翻譯我不是很認(rèn)同）的出現(xiàn)就是為了解決這個(gè)問題。B樹由于是多路二叉樹（根結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn)，其他結(jié)點(diǎn)子結(jié)點(diǎn)不止兩個(gè)），它的高度要遠(yuǎn)低于平衡二叉樹，B樹就是為了降低高度，一般來講，二叉平衡樹每下降一層就執(zhí)行一次磁盤I/O操作，以1GB數(shù)據(jù)為例，平均需要30次磁盤I/O才能讀取到數(shù)據(jù)，而B樹每下降一層，每個(gè)結(jié)點(diǎn)都會(huì)讀入多個(gè)關(guān)鍵碼，因此B樹適用于實(shí)現(xiàn)磁盤的讀寫邏輯。
B 樹是為了磁盤或其它存儲(chǔ)設(shè)備而設(shè)計(jì)的一種多叉（相對(duì)于二叉樹，B樹每個(gè)內(nèi)結(jié)點(diǎn)有多個(gè)分支，即多叉）平衡排序樹。與下面要介紹的紅黑樹很相似，但在降低磁盤I/0操作方面要更好一些。許多數(shù)據(jù)庫系統(tǒng)都一般使用B樹或者B樹的變形結(jié)構(gòu)（如B+樹）來存儲(chǔ)信息。
B樹中的每個(gè)結(jié)點(diǎn)根據(jù)實(shí)際情況可以包含大量的關(guān)鍵字信息和分支(當(dāng)然是不能超過磁盤塊的大小，根據(jù)磁盤驅(qū)動(dòng)(disk drives)的不同，一般塊的大小在1k~4k左右)；這樣樹的深度降低了，這就意味著查找一個(gè)元素只要很少結(jié)點(diǎn)從外存磁盤中讀入內(nèi)存，很快訪問到要查找的數(shù)據(jù)。
Bucket Li："mysql 底層存儲(chǔ)是用B+樹實(shí)現(xiàn)的，why？內(nèi)存中B+樹是沒有優(yōu)勢的，但是一到磁盤，B+樹的威力就出來了"。
B樹：有序數(shù)組+平衡多叉樹； B+樹：有序數(shù)組鏈表+平衡多叉樹； B*樹：一棵豐滿的B+樹。
R-B Tree，全稱是Red-Black Tree，又稱為“紅黑樹”，它一種特殊的二叉查找樹。紅黑樹的每個(gè)節(jié)點(diǎn)上都有存儲(chǔ)位表示節(jié)點(diǎn)的顏色，可以是紅(Red)或黑(Black)。
紅黑樹的應(yīng)用比較廣泛，主要是用它來存儲(chǔ)有序的數(shù)據(jù)，它的時(shí)間復(fù)雜度是O(lgn)，效率非常之高。例如，Java集合中的TreeSet和TreeMap，C++ STL中的set、map，需要使用動(dòng)態(tài)規(guī)則的防火墻系統(tǒng)，使用紅黑樹而不是散列表被實(shí)踐證明具有更好的伸縮性。Linux內(nèi)核在管理vm_area_struct（虛擬內(nèi)存）時(shí)就是采用了紅黑樹來維護(hù)內(nèi)存塊的。
對(duì)于鏈表、數(shù)組、樹和圖來說，它們每次的動(dòng)態(tài)操作都會(huì)完全遺忘之前的狀態(tài)，轉(zhuǎn)而到達(dá)全新的狀態(tài)，這種數(shù)據(jù)結(jié)構(gòu)稱為ephemeral structure。另一種數(shù)據(jù)結(jié)構(gòu)可以記錄某一歷史時(shí)刻的狀態(tài)，在訪問時(shí)可以根據(jù)版本好+目標(biāo)數(shù)據(jù)進(jìn)行訪問，這種數(shù)據(jù)結(jié)構(gòu)稱為persistent structure。事實(shí)上，紅黑樹可以實(shí)現(xiàn)這種對(duì)歷史版本的記錄。
B樹與紅黑樹最大的不同在于，B樹的結(jié)點(diǎn)可以有許多子女，從幾個(gè)到幾千個(gè)。那為什么又說B樹與紅黑樹很相似呢?因?yàn)榕c紅黑樹一樣，一棵含n個(gè)結(jié)點(diǎn)的B樹的高度也為O（lgn），但可能比一棵紅黑樹的高度小許多，應(yīng)為它的分支因子比較大。所以，B樹可以在O（logn）時(shí)間內(nèi)，實(shí)現(xiàn)各種如插入（insert），刪除（delete）等動(dòng)態(tài)集合操作。
么是堆（大根堆、小根堆）？
這里說的“堆”是一種數(shù)據(jù)結(jié)構(gòu)，注意與jvm中的堆內(nèi)存分開。堆必須滿足以下兩個(gè)條件：（1）是完全二叉樹 （2）heap中存儲(chǔ)的值是偏序（偏序只對(duì)部分元素成立關(guān)系R,全序?qū)现腥我鈨蓚€(gè)元素都有關(guān)系R）。
大根堆：父結(jié)點(diǎn)的值大于等于其子結(jié)點(diǎn)的值；小根堆：父結(jié)點(diǎn)的值小于等于其子節(jié)點(diǎn)的值。
堆的存儲(chǔ)：
一般用數(shù)組來存儲(chǔ)堆，第i個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)下標(biāo)為,（i-1）/2，它的左右子結(jié)點(diǎn)的下標(biāo)為i2+1，i2+2。
插入一個(gè)元素：
新元素被加入到heap的末尾，然后更新樹以恢復(fù)堆的次序。每次插入都是將新數(shù)據(jù)放在數(shù)組最后。可以發(fā)現(xiàn)從這個(gè)新數(shù)據(jù)的父結(jié)點(diǎn)到根結(jié)點(diǎn)必然為一個(gè)有序的數(shù)列，現(xiàn)在的任務(wù)是將這個(gè)新數(shù)據(jù)插入到這個(gè)有序數(shù)據(jù)中——這就類似于直接插入排序中將一個(gè)數(shù)據(jù)并入到有序區(qū)間中。以大根堆為例：
刪除一個(gè)元素：
按定義，堆中每次都刪除第0個(gè)數(shù)據(jù)。為了便于重建堆，實(shí)際的操作是將最后一個(gè)數(shù)據(jù)的值賦給根結(jié)點(diǎn)，然后再從根結(jié)點(diǎn)開始進(jìn)行一次從上向下的調(diào)整。調(diào)整時(shí)先在左右兒子結(jié)點(diǎn)中找最大的，如果父結(jié)點(diǎn)比這個(gè)最小的子結(jié)點(diǎn)還大說明不需要調(diào)整了，反之將父結(jié)點(diǎn)和它交換后再考慮后面的結(jié)點(diǎn)。相當(dāng)于從根結(jié)點(diǎn)將一個(gè)數(shù)據(jù)的“下沉”過程。
棧和隊(duì)列的相同之處和不同之處？
相同點(diǎn)：
①都是線性結(jié)構(gòu)
②插入操作都是在表尾進(jìn)行
③ 插入和刪除的時(shí)間復(fù)雜度都是O(1)，在空間復(fù)雜度上也相同
④都可以通過順序結(jié)構(gòu)和鏈表實(shí)現(xiàn)
⑤多鏈棧和多鏈隊(duì)列的管理模式可以相同。
不同點(diǎn)：
①刪除數(shù)據(jù)元素的位置不同，棧在表尾進(jìn)行，隊(duì)列在表頭進(jìn)行
②順序棧能夠?qū)崿F(xiàn)多?？臻g共享，而順序隊(duì)列不能。 ③應(yīng)用場景不同；常見棧的應(yīng)用場景包括括號(hào)問題的求解，表達(dá)式的轉(zhuǎn)換和求值，函數(shù)調(diào)用和遞歸實(shí)現(xiàn)，深度優(yōu)先搜索遍歷等；常見的隊(duì)列的應(yīng)用場景包括計(jì)算機(jī)系統(tǒng)中各種資源的管理，消息緩沖器的管理和廣度優(yōu)先搜索遍歷等。
兩個(gè)棧實(shí)現(xiàn)隊(duì)列，兩個(gè)隊(duì)列實(shí)現(xiàn)棧。
◆兩個(gè)棧實(shí)現(xiàn)隊(duì)列，實(shí)現(xiàn)隊(duì)列的入隊(duì)（enqueue）和出隊(duì)（dequeue）操作。
圖（1）：將隊(duì)列中的元素“abcd”壓入stack1中，此時(shí)stack2為空；
圖（2）：將stack1中的元素pop進(jìn)stack2中，此時(shí)pop一下stack2中的元素，就可以達(dá)到和隊(duì)列刪除數(shù)據(jù)一樣的順序了；
圖（3）：可能有些人很疑惑，就像圖3，當(dāng)stack2只pop了一個(gè)元素a時(shí)，satck1中可能還會(huì)插入元素e,這時(shí)如果將stack1中的元素e插入stack2中，在a之后出棧的元素就是e了，顯然，這樣想是不對(duì)的，我們必須規(guī)定當(dāng)stack2中的元素pop完之后，也就是satck2為空時(shí)，再插入stack1中的元素。
用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧
因?yàn)殛?duì)列是先進(jìn)先出，所以要拿到隊(duì)列中最后壓入的數(shù)據(jù)，只能每次將隊(duì)列中數(shù)據(jù)dequeue至最后一個(gè)，此時(shí)這個(gè)數(shù)據(jù)為最后enqueue入隊(duì)列的數(shù)據(jù)，在每次dequeue時(shí)，將數(shù)據(jù)enqueue至隊(duì)列2中。每次執(zhí)行delete操作時(shí)，循環(huán)往復(fù)。（感覺效率低）每次刪除時(shí)間復(fù)雜度O(N)
圖（1）：當(dāng)棧里面插入元素“abcd”的時(shí)候，元素a在棧底（最后出去），d在棧頂（最先出去）；
圖（2）：將元素“abc”從q1中頭刪，然后再q2中尾插進(jìn)來之后，頭刪q1中的元素“d”，就相當(dāng)于實(shí)現(xiàn)了棧頂元素的出棧；
圖（3）：同理，將元素“ab”從q2中頭刪，然后尾插到q1中，然后再頭刪q2中的元素“c”;
圖（4）：同理，刪除元素“b”;
圖（5）：當(dāng)棧又插入一個(gè)元素“e”時(shí)，此時(shí)元素“a”不能從隊(duì)列中刪除，而是將元素“a”插入q2中，再刪除q1中的元素“e”,最后再刪除元素“a”。
說明：其中紅色框代表該隊(duì)列中的元素出隊(duì)列，該隊(duì)列為空。
