1–5 佇列 Queue
就像排隊一樣，新到的人(新增數據，enqueue)會排在隊伍的尾端，但處理(例如刪除數據，dequeue)，則會從隊伍的頭開始。
有點類似堆疊，但我們可以從字面上的意思推敲出來，佇列的“新增數據”跟“刪除數據”是分別從一列數據的兩端來進行的。
就像排隊一樣，新到的人(新增數據，enqueue)會排在隊伍的尾端，但處理(例如刪除數據，dequeue)則會從隊伍的頭，也就是最早被加進這個佇列的資料開始進行。
與堆疊相反，佇列的這個概念稱為“先進先出” First In First Out。
這樣的資料結構可以被應用在廣度優先搜尋(4–2)，之後會說明。
1–6 雜湊表 Hash Table
Hash Table可以用來儲存成對的數據，每一組數據是一個key and value pair。
例如：我們想要儲存每個人的電話號碼，key為人名，value為電話號碼。
為了瞭解hash table的優勢，我們先來看看同樣的成對數據，如果存在陣列中，會是什麼樣子。
假設我們想要知道資料中的Lisa Smith的電話號碼，在陣列中，因為我們不知道Lisa Smith在array中的index，所以得從array[0]開始，依序一個個搜索 ，直到找到key為Lisa Smith為止，才能得知相對應的電話號碼。這樣的搜尋方式稱為線性搜尋(3–1)，資料量龐大時，是非常沒有效率的。
而hash table可以解決這個問題。
首先，我們得先決定，所有的資料要被大致分為幾組。
這裡的例子分為16組。也就是說，我們先準備一個長度為16的陣列用來儲存數據。
要存入一筆新的數據時，key得先通一個hash function，這個函式會回傳一個hash值，將hash值除以組數後得到的餘數，就是這個數據現在的index。
公式如下：hash = hashfunc(key)index = hash % array_size
如下圖，John Smith的hash值除以16後的餘數是2，所以他的資料被存在index 02的箱子裡。反覆執行同樣的步驟，一一存入每筆資料。
可以想像的是，求得相同餘數的資料，可能不只一筆，這個現象稱為Collision。當發生Collision時，我們可以用列表list的形式，將同個餘數的數據們連結起來。如下圖，Sandra Dee的餘數和John Smith相同，但箱子裡已經有John Smith了，所以我們用list把Sandra Dee接在John Smith後面。(解決collision的方法還有很多，這邊僅舉出Chaining的例子。)
回到一開始的問題，當我們想得知Lisa Smith的電話時，我們一樣透過hash function得知Lisa Smith的hash值，接著求出index，便可以直接在array[index]中找到他的電話了。那如果我們想找的是Sandra Dee的電話呢？ 依照前述的步驟，我們會先找到John Smith，接著再從John Smith開始進行線性搜尋(3–1)，直到找到key為Lisa Smith的資料為止。
在一開始我們說，我們要先決定好，所有的資料要被分為幾組，這個決定是非常重要的。
組數太少時，collision的機會就會增加，導致常常需要做線性搜尋(3–1)，便無法有效發揮hash table的優勢。但組數太多時，會產生許多沒有儲存到資料的空位，造成記憶體空間浪費。
Hash Table適合用在程式語言的關聯陣列 (Associated Array)，意指有key value pair的陣列。
ps. 相對於另一種陣列是索引式陣列，用index存取array element。
1–7 堆積 Heap
堆積是一種樹狀結構，數據被存在各個節點(node)上，用於實踐 “優先佇列 Priority Queue”。
而優先佇列是什麼？可以自由新增數據，讀取數據時從最小值開始選取，就可以稱作優先佇列。
堆積有幾個原則必須遵守：
1. 每個node最多可以有兩個child node。2. Chile node的數一定要比father node大，因此最小的數會在樹狀結構的最上方，稱為root。3. 為了遵守第二點的結構原則，新增數據時，會從最左下方的node開始填入，若最下方一層被填滿時，就產生新的一層，從最左邊開始新增數據。4. 讀取數據時從最小值開始(優先佇列)，也就是樹狀結構的root。5. 取出數據後，必須將最尾端的數據提到最上面，接著再進行重整heap結構。
以下圖為例，我們依序填入1, 3, 6, 5, 9, 8 這些數據：
如果要在上圖的結構中新增一個數據4，依照前述的原則，因為最底下一層還有空位，所以4會先被填入這個位置。但填入後發現，他比他的father node 6還要小，不符合”子比父大”的原則，所以他必須跟father node 6交換位置。在堆疊中進行新增或刪除數據時，必須反覆進行“子比父大”原則的檢查，對調位置直到整個heap都符合原則為止。
因為需要反覆比較上下移動，heap的新增和刪除數據所需要的時間，都與heap的高度成正比。假設數據有n個, 則heap高度為log2(n)，執行時間為O(log n)。
在需要反覆取出最小值時，heap很方便，例如戴克斯特拉演算法(4–5)，之後會說明。
1–8 二元搜尋樹 Binary Search Tree
Binary Search Tree同樣也是樹狀結構，也將數據存在node裏。他有幾個特性：
1. 所有數都會大於連結在其左邊節點上的數 (右比左大)2. 所有數都會小於連結在其右邊節點上的數
舉例來說，在10左邊的數，藍色圈起來的部分(8, 3, 1, 6, 4, 7)全都比他小，在他右邊的數 (14, 13)則比他大。
從這個特性可以得知：
1. 最小值會在從頂點開始，沿線一路往左的最尾端2. 最大值會在從頂點開始，沿線一路往右的最尾端
新增數據時，我們先想像這個數據在樹的最頂端，為了符合前述的特性，我們必須反覆地將這個數跟現有的數比大小。
如此一來才能決定這個數在結構中，應該往左擺還是往右擺 (較小往左，較大則往右)，遇到該方向已經沒有節點時，就新增一個節點存放這個新增的數據。
如果我們要在上圖的結構中新增一個數據11，流程如下：
- 一開始，我們比較11與頂點8, 11<8，所以11往右移動
- 接著跟10比大小，11>10，所以再往右移動
- 跟14比大小，11<14，往左移動
- 跟13比大小，11<13，但目前13的左下方沒有node, 所以新增一個node存放11
新增數據11後的結構會長這樣：
刪除節點時，會分為幾種情況：
- 該節點沒有子節點，例如圖中的4，直接刪除即可。
- 該節點有一個子節點，例如圖中的13，刪除13後，把子節點11移到原本13的位置即可。
- 該節點有兩個子節點，例如圖中的3，刪除3後，可以在3左邊的tree中找最大的node(在這邊是1)，把1移到原本3的位置。或者是，在3右邊的tree中找最小的node(在這邊是4)，把4移到原本3的位置也可以。
note：如果被移動的節點本身也有子結點，就反覆進行同樣的步驟，可參考遞迴演算法河內塔。
要搜尋一個節點時，類似新增數據的邏輯，從頂端開始，比較大小，根據比大小結果決定接下來要往左邊還是右邊繼續找。
我們可以把二元搜尋樹想成，是用樹狀結構來表現二元搜尋(3–2)。比較的次數就等同於樹的高度，但這也取決於這棵樹長得平衡不平衡，當樹比較平衡的時候，執行時間會是O(log n)，但如果這棵樹長得一點都不像樹，反而是往一邊靠攏成一直線的樣子，那執行時間會提高成O(n)。
