1. 棧(stack)

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

　　2. 隊(duì)列(queue)

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

　　3. 鏈表(Link)

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

　　4. 散列表(Hash Table)

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

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

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

　　(1)直接定址法： 取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(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)鍵字被某個(gè)不大于散列表表長(zhǎng) m 的數(shù) p 除后所得的余數(shù)為散列地址，即：h(key) = key MOD p p ≤ m

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

　　5. 排序二叉樹

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

　　5.1 插入操作

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

　　5.2 刪除操作

　　刪除操作主要分為三種情況，即要?jiǎng)h除的節(jié)點(diǎn)無(wú)子節(jié)點(diǎn)，要?jiǎng)h除的節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)，要?jiǎng)h除的節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)。

　　對(duì)于要?jiǎng)h除的節(jié)點(diǎn)無(wú)子節(jié)點(diǎn)可以直接刪除，即讓其父節(jié)點(diǎn)將該子節(jié)點(diǎn)置空即可。

　　對(duì)于要?jiǎng)h除的節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)，則替換要?jiǎng)h除的節(jié)點(diǎn)為其子節(jié)點(diǎn)。

　　對(duì)于要?jiǎng)h除的節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)，則首先找該節(jié)點(diǎn)的替換節(jié)點(diǎn)(即右子樹中最小的節(jié)點(diǎn))，接著替換要?jiǎng)h除的節(jié)點(diǎn)為替換節(jié)點(diǎn)，然后刪除替換節(jié)點(diǎn)。

　　5.3 查詢操作

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