棧##
棧是一種動態(tài)集合构资，它是一種LIFO（last in first out后進(jìn)先出）結(jié)構(gòu)
棧的實現(xiàn)：
（1）數(shù)組
（2）鏈表
棧要記錄的數(shù)據(jù)：
（1）棧頂位置top
注意這個top有兩種理解方式，一種是表示棧的最后一個數(shù)據(jù)的位置陨簇，另一種是表示棧的最后一個數(shù)據(jù)的下一個位置吐绵，這兩種理解對棧的操作代碼有一定的影響
（2）棧最大大小size
棧的操作：
（1）STACK_EMPTY（）：判斷棧是否為空
（2）PUSH（X）：向棧中添加一個值，注意棧是否為滿的
（3）POP（）：從棧中彈出一個值河绽，注意棧是否為空
棧的簡要實現(xiàn)：github棧
棧的應(yīng)用：
（1）括號匹配問題
隊列##
與棧不同己单，它是一種FIFO（first in first out先進(jìn)先出）結(jié)構(gòu)
隊列的實現(xiàn)：
（1）數(shù)組
（2）鏈表
隊列要記錄的數(shù)據(jù)：
（1）隊首位置head：第一個元素位置
（2）隊尾位置tail：下一個元素要插入的位置（最后一個元素的下一個位置）
（3）隊列最大大小size
隊列的操作：
（1）ENQUEUE（x）：入隊
（2）DEQUEUE（）：出隊
（3）EMPTY（）：隊列為空，head=tail
（4）FULL（）：隊列為滿耙饰，head=（tail+1）%size
隊列的簡要實現(xiàn)：github隊列
隊列的應(yīng)用：
（1）
鏈表##
與數(shù)組中元素地址連續(xù)不同纹笼，鏈表中兩個元素地址不一定連續(xù)，而是由專門的一個指針指明該元素的后一個（前一個）元素的地址苟跪。
鏈表種類：
（1）單向鏈表：只有指向后一個元素的指針
（2）雙向鏈表：有指向后一個和前一個元素的指針
（3）循環(huán)鏈表：鏈表內(nèi)存在一個環(huán)
鏈表節(jié)點（Node）記錄的數(shù)據(jù)：
（1）要存儲的數(shù)據(jù)data
（2）下一個節(jié)點地址Node* next
（3）若是雙向鏈表還要存儲前一個節(jié)點地址Node prev
鏈表（LinkedList）記錄的數(shù)據(jù)：
（1）鏈表的頭指針Node head
（2）可能還記錄鏈表的尾指針 Node* tail
鏈表的操作：
（1）SEARCH(x)：鏈表的搜索
（2）INSERT(i,x)：鏈表的插入廷痘，在第i個位置插入x
（3）DELETE（x）:鏈表的刪除
哨兵（sentinel）：
為了減少邊界條件的判斷（是否為空鏈表等等），引入哨兵件已，使得鏈表永遠(yuǎn)不為“空”笋额。
指針和對象的實現(xiàn)：
有些語言比如Java沒有指針（C中就存在指針），這時我們需要考慮指針的替代實現(xiàn)方式篷扩。
（1）用二維數(shù)組表示指針
我們可以設(shè)置一個n*3的數(shù)組記錄n個節(jié)點兄猩，那個3就表示存儲的數(shù)據(jù)、前一個元素的坐標(biāo)（index）和后一個元素的坐標(biāo)。
（2）用一維數(shù)組表示指針
樹##
樹的種類：
（1）二叉樹
二叉樹要存儲4個數(shù)據(jù)枢冤，分別是節(jié)點攜帶的信息和其父節(jié)點鸠姨、左右子節(jié)點的指針。
（2）分支無限制的有根樹：
上面二叉樹每個節(jié)點最多有兩個子節(jié)點淹真，而分支無限制的有根數(shù)則沒有這個限制讶迁，可能有3個、5個甚至更多子節(jié)點趟咆。所以存儲這種數(shù)據(jù)結(jié)構(gòu)的問題在于我們事先并不知道應(yīng)該設(shè)置多少個child指針添瓷，若設(shè)置的少了不能滿足要求，設(shè)置的過多又會浪費空間值纱。所以這里提出一種新的描述這種數(shù)據(jù)結(jié)構(gòu)的方法——左孩子右兄弟表示法鳞贷，這種方法每個節(jié)點設(shè)置3個指針：父指針、從左數(shù)第一個孩子的指針虐唠、其右側(cè)相鄰的兄弟指針搀愧，如下圖所示
堆##
堆實際上是以數(shù)組形式存儲的二叉樹
堆需要存儲的數(shù)據(jù):
（1）數(shù)組的大小max-size
（2）堆元素個數(shù)size，這里size要小于max-size
堆中元素通過坐標(biāo)來確定父節(jié)點疆偿、左右子節(jié)點咱筛，具體來說：
一個節(jié)點i的父節(jié)點：[i/2]
一個節(jié)點i的左子節(jié)點：[i2]
一個節(jié)點i的右子節(jié)點：[i2+1]
堆的分類：
（1）最大堆
滿足所有節(jié)點都比其父節(jié)點值小（小于等于）的堆
A[i/2]>=A[i]
（2）最小堆
滿足所有節(jié)點都比其父節(jié)點值大（大于等于）的堆
A[i/2]<=A[i]
堆的操作：
（1）維護堆的性質(zhì)（HEAPIFY）
這里指維護最大堆或最小堆的性質(zhì)杆故。假設(shè)一個數(shù)組中下標(biāo)為i的節(jié)點的子節(jié)點滿足最大（醒嘎帷）堆性質(zhì)，但自身不一定滿足這個性質(zhì)处铛，這時就需要HEAPIFY饲趋，具體來說是要比較這個節(jié)點和其兩個子節(jié)點的大小，將其中的大（谐敷 ）的和該節(jié)點位置交換奕塑，這樣這個節(jié)點及其兩個子節(jié)點就滿足最大（小）堆的性質(zhì)了家肯，但是可能交換后子節(jié)點不滿足堆的性質(zhì)龄砰，所以這里要遞歸調(diào)用HEAPIFY，直到達(dá)到最下層節(jié)點讨衣，這樣就維護了堆的性質(zhì)换棚。HEAPIFY耗時O（lgn）
（2）建堆（BUILD-HEAPIFY）
從中間那個元素開始到第一個元素，逐一調(diào)用HEAPIFY函數(shù)反镇，即可完成建堆圃泡。
逐一從中間那個元素開始遞減而不是從第一個元素遞增，這時為了保證每次調(diào)用HEAPIFY都能保證該節(jié)點的子節(jié)點都滿足最大（性赶铡）堆的性質(zhì)，否則無法調(diào)用HEAPIFY。中間那個元素是第一個可能不滿足最大（辛究鳌）堆性質(zhì)的節(jié)點风秤，所以從這里開始維護（HEAPIFY）。一個建堆的例子如下所示：[5,3,17,10,84,19,6,22,9]
建堆的期望時間為O（n）
堆的應(yīng)用:
（1）堆排序（詳見排序算法）
（2）優(yōu)先隊列
