棧
棧算是一種特殊的線性表论笔，有后進先出的特性赚瘦，只需要在一端進行入棧（插入數(shù)據(jù)）或者出棧（刪除數(shù)據(jù)）的操作爹谭。要實現(xiàn)的話從數(shù)組和鏈表兩方面來考慮祟牲。
數(shù)組實現(xiàn)
一般選擇數(shù)組下標最小的作為棧底隙畜，設(shè)置一個top表示當前棧頂?shù)奈恢茫绻迦胍粋€元素疲眷，先判斷棧還有沒有容量禾蚕，有的話就把top++令宿，然后元素放到當前top上熬苍。如果刪除元素就讓一個值等于當前元素，然后top--真屯。
初始化的時候几颜，要把top設(shè)置為-1倍试，表示棧空蛋哭，如果top等于數(shù)組的容量capacity - 1县习，就代表棧滿了。
鏈表實現(xiàn)
每次插入一個節(jié)點谆趾，就把該節(jié)點的next指針指向當前棧頂?shù)脑卦暝浮６鴦h除節(jié)點的時候，就讓top指針指向棧頂元素的next指針沪蓬，然后棧頂元素的next就可以設(shè)置為null彤钟。可以說是沒有頭結(jié)點的單鏈表跷叉。
隊列
隊列是先進先出的特性逸雹，從一端增加數(shù)據(jù)（入隊）营搅，從另一端刪除數(shù)據(jù)（出隊）。刪除這端叫做隊頭梆砸，增加這個是隊尾转质。
順序隊列
一個front隊頭指針，一個rear隊尾指針帖世，初始化的時候兩個都指向位置0休蟹，如果插入數(shù)據(jù)的話，就放到隊尾指針的元素狮暑，然后rear++鸡挠。如果刪除就取出隊頭的元素，然后front++搬男。這樣子就會造成一個問題拣展，因為出隊后front++，而capacity不會變缔逛，那么這個隊列的容量就會一直變小备埃，所以循環(huán)隊列出現(xiàn)了。
循環(huán)隊列
如果是一個圈的話褐奴，就不會出現(xiàn)有空間浪費的情況按脚。初始化兩個指針都是0，如果隊列滿了敦冬，這兩個指針的位置就會相等辅搬，就無法判斷隊列是空還是滿，所以在最后設(shè)置一個元素空間脖旱，這個空間不會用來放任何元素堪遂，如果（rear + 1） & QueueSize == front的話就表示隊列滿了。出隊和入隊的時候萌庆，front或者rear + 1后都要對QueueSize取模溶褪。
鏈式存儲
入隊的話，rear的next指向入隊元素践险，然后rear指針指向入隊元素猿妈。出隊的話，先取出元素的值巍虫，然后隊頭指針指向該元素的next彭则，如果這個時候隊尾也指向該元素，那么隊尾指針等于隊頭指針占遥，表示隊列為空贰剥，然后把該元素的next變?yōu)閚ull。
二叉樹
- 二叉樹第i層的節(jié)點數(shù)最多為2的i-1次方
- 非空二叉樹葉子節(jié)點數(shù)等于度為2的節(jié)點數(shù)+1筷频，即n0 = n2 + 1蚌成；
前序遍歷：根節(jié)點->左子樹->右子樹
中序遍歷：左子樹->根節(jié)點->右子樹
后序遍歷：左子樹->右子樹->根節(jié)點
如果二叉樹中除去最后一層節(jié)點為滿二叉樹，且最后一層的結(jié)點依次從左到右分布凛捏，則此二叉樹被稱為完全二叉樹担忧。
完全二叉樹的性質(zhì)有 n 個結(jié)點的完全二叉樹的深度為 ?log2n?+1。即log2n向下取整然后+1坯癣。
二叉排序樹一般用于查找瓶盛，性質(zhì)有左子樹所有節(jié)點的值小于根節(jié)點，右子樹所有節(jié)點的值大于根節(jié)點示罗。
平衡二叉樹的定義：根節(jié)點的左右子樹高度之差不能超過1惩猫，在構(gòu)建的時候如果某顆子樹不是平衡的，就對于一整個子樹進行調(diào)整蚜点，變成平衡二叉樹轧房，然后在放回原來子樹的位置。
已知平衡二叉樹的深度為k绍绘，那么平衡二叉樹最少節(jié)點數(shù)為N(k)=F（k + 2） - 1奶镶，即斐波那契數(shù)列對應(yīng)k+2的值-1，最大節(jié)點數(shù)就是滿二叉樹了陪拘，那么就是2的n次方 - 1
二叉樹存儲結(jié)構(gòu)
可以用數(shù)組順序存儲厂镇，一個根節(jié)點有值val，左孩子左刽，右孩子三個屬性捺信。遇到數(shù)組存放null值就把所有設(shè)置為空。如果是鏈表來構(gòu)建的話欠痴，每個節(jié)點都有值和兩個指針迄靠，指針分別指向左孩子右孩子的值。
計算hash值
- 直接定址法：定一個公式f（key）= a * key + b斋否；直接通過計算來得知該存放的位置
- 除留余數(shù)法：對key取模梨水，得出存放的位置f（key） = key mod p，一般p選接近于表長的最小質(zhì)數(shù)
處理hash沖突方法
- 開放地址法：一旦遇到?jīng)_突我就尋找下一個空的散列地址茵臭，然后存進去疫诽。
- 鏈地址法：如果遇到?jīng)_突，把這個位置變成一個單鏈表旦委，就是java中的hashmap在jdk1.7之前的解決方法奇徒。
- 再散列函數(shù)法：準備多個散列函數(shù)，如果這個發(fā)生沖突缨硝，就換下一個函數(shù)進行計算摩钙。
