1. 棧(stack)

　　棧(stack)是限制插入和刪除只能在一個位置上進(jìn)行的表，該位置是表的末端，叫做棧頂(top)。它是后進(jìn)先出(LIFO)的。對棧的基本操作只有 push(進(jìn)棧)和 pop(出棧)兩種，前者相當(dāng)于插入，后者相當(dāng)于刪除最后的元素。

　　2. 隊列(queue)

　　隊列是一種特殊的線性表,特殊之處在于它只允許在表的前端(front)進(jìn)行刪除操作，而在表的后端(rear)進(jìn)行插入操作，和棧一樣，隊列是一種操作受限制的線性表。進(jìn)行插入操作的端稱為隊尾，進(jìn)行刪除操作的端稱為隊頭。

　　3. 鏈表(Link)

　　鏈表是一種數(shù)據(jù)結(jié)構(gòu)，和數(shù)組同級。比如，Java 中我們使用的 ArrayList，其實現(xiàn)原理是數(shù)組。而LinkedList 的實現(xiàn)原理就是鏈表了。鏈表在進(jìn)行循環(huán)遍歷時效率不高，但是插入和刪除時優(yōu)勢明顯。

　　4. 散列表(Hash Table)

　　散列表(Hash table，也叫哈希表)是一種查找算法，與鏈表、樹等算法不同的是，散列表算法在查找時不需要進(jìn)行一系列和關(guān)鍵字(關(guān)鍵字是數(shù)據(jù)元素中某個數(shù)據(jù)項的值，用以標(biāo)識一個數(shù)據(jù)元素)的比較操作。

　　散列表算法希望能盡量做到不經(jīng)過任何比較，通過一次存取就能得到所查找的數(shù)據(jù)元素，因而必須要在數(shù)據(jù)元素的存儲位置和它的關(guān)鍵字(可用key表示)之間建立一個確定的對應(yīng)關(guān)系，使每個關(guān)鍵字和散列表中一個唯一的存儲位置相對應(yīng)。因此在查找時，只要根據(jù)這個對應(yīng)關(guān)系找到給定關(guān)鍵字在散列表中的位置即可。這種對應(yīng)關(guān)系被稱為散列函數(shù)(可用 h(key)表示)。

　　用的構(gòu)造散列函數(shù)的方法有：

　　(1)直接定址法： 取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)值為散列地址。

　　即：h(key) = key 或 h(key) = a * key + b，其中 a 和 b 為常數(shù)。

　　(2)數(shù)字分析法

　　(3)平方取值法： 取關(guān)鍵字平方后的中間幾位為散列地址。

　　(4)折疊法：將關(guān)鍵字分割成位數(shù)相同的幾部分，然后取這幾部分的疊加和作為散列地址。

　　(5)除留余數(shù)法：取關(guān)鍵字被某個不大于散列表表長 m 的數(shù) p 除后所得的余數(shù)為散列地址，即：h(key) = key MOD p p ≤ m

　　(6)隨機(jī)數(shù)法：選擇一個隨機(jī)函數(shù)，取關(guān)鍵字的隨機(jī)函數(shù)值為它的散列地址，即：h(key) = random(key)

　　5. 排序二叉樹

　　首先如果普通二叉樹每個節(jié)點滿足：左子樹所有節(jié)點值小于它的根節(jié)點值，且右子樹所有節(jié)點值大于它的根節(jié)點值，則這樣的二叉樹就是排序二叉樹。

　　5.1 插入操作

　　首先要從根節(jié)點開始往下找到自己要插入的位置(即新節(jié)點的父節(jié)點);具體流程是：新節(jié)點與當(dāng)前節(jié)點比較，如果相同則表示已經(jīng)存在且不能再重復(fù)插入;如果小于當(dāng)前節(jié)點，則到左子樹中尋找，如果左子樹為空則當(dāng)前節(jié)點為要找的父節(jié)點，新節(jié)點插入到當(dāng)前節(jié)點的左子樹即可;如果大于當(dāng)前節(jié)點，則到右子樹中尋找，如果右子樹為空則當(dāng)前節(jié)點為要找的父節(jié)點，新節(jié)點插入到當(dāng)前節(jié)點的右子樹即可。

　　5.2 刪除操作

　　刪除操作主要分為三種情況，即要刪除的節(jié)點無子節(jié)點，要刪除的節(jié)點只有一個子節(jié)點，要刪除的節(jié)點有兩個子節(jié)點。

　　對于要刪除的節(jié)點無子節(jié)點可以直接刪除，即讓其父節(jié)點將該子節(jié)點置空即可。

　　對于要刪除的節(jié)點只有一個子節(jié)點，則替換要刪除的節(jié)點為其子節(jié)點。

　　對于要刪除的節(jié)點有兩個子節(jié)點，則首先找該節(jié)點的替換節(jié)點(即右子樹中最小的節(jié)點)，接著替換要刪除的節(jié)點為替換節(jié)點，然后刪除替換節(jié)點。

　　5.3 查詢操作

　　查找操作的主要流程為：先和根節(jié)點比較，如果相同就返回，如果小于根節(jié)點則到左子樹中遞歸查找，如果大于根節(jié)點則到右子樹中遞歸查找。因此在排序二叉樹中可以很容易獲取最大(最右最深子節(jié)點)和最小(最左最深子節(jié)點)值。