# 模組20 集合與資料結構（LinkedXxx、Queue、FIFO、FILO）
:::info
<a href="/@TFA101/CherryJava" target="_self">< :notebook_with_decorative_cover: [共享目錄] Java 2 學習筆記
</a>
:::

本筆記內會介紹到一些有特別的資料結構的集合。

### 鏈結（Linked）結構的集合

* List
* **LinkedList**
* Set
* HashSet
* **LinkedHashSet**
* Map
* HashMap
* **LinkedHashMap**

### 佇列（Queue）結構的集合

* Queue
* **LinkedList**（對，又是我）
* **PriorityQueue**

### FIFO（First-In-First-Out）資料結構的集合

* Queue
* **PriorityQueue**

### LIFO（Last-In-First-Out）資料結構的集合
* List
* Vector
* **Stack**

## 鏈結（Linked）的資料結構

長得就像元素手牽手。
第一個元素沒有 predecessor（先驅者）、最後一個元素沒有 successor（後繼者），其餘的元素都只各有一個 predecessor 和一個 successor。

> 圖例（要注意，Linked 相關的集合並不是一段連續的線性儲存空間）：
> <div id="LElement">　 A <font color=red>●</font>--</div>--<div id="LElement">--<font color=red>●</font> B <font color=red>●</font>--</div>--<div id="LElement">--<font color=red>●</font> C <font color=red>●</font>--</div>--<div id="LElement">--<font color=red>●</font> D 　</div>

<style>
#LElement {
display:inline-block;
background-color: #eee;
padding:8px 4px;
border-radius: 25px;
}
</style>

A 沒有先驅者，D 沒有後繼者，B、C 都只各有一個先驅者、一個後繼者。
以 B 來說，先驅者為 A，後繼者為 C。

### 節點（Node）

圖例中的紅色圓點 <font color=red>●</font> 即是節點，用來記錄上一個或下一個元素的參考位址。

因此插入元素，只要前/後的人把原本牽的後/前手放開，改牽另外一個新來的人就好（更換節點中儲存的位址）。移除元素概念類似，一樣是牽手對象換人，不贅述。

### 以加入先後為順序

==所有的 Linked 相關的類別預設都是依照加入先後為順序排列==，包含HashSet、HashMap。

### LinkedList

#### LinkedList <=> ArrayList

從比較中可以看出鏈結的特性：

|比較|LinkedList|ArrayList|
| - | - | - |
|元素的插入與移除|適合|不適合|
|索引值的存取|（資料量大時）較差|佳|
|儲存方式與順序|元素與元素間有相對順序|一段位置連續的線性空間，依序存放著元素|

:::info
:bulb: <span style="border-bottom: 1px solid #31708f;">**Remark**</span>　**ArrayList 對插入或移除元素的反應**
<div style="margin-bottom:16px;" title="保持間距用"></div>
移除元素產生空缺時，會複製下一個元素來補，再刪除複製元素的原值，一直重覆到集合的最後一個元素為止，非常耗能。
:::

### LinkedHashSet 和 LinkedHashMap

再重述一次，<font color=red>LinkedHashSet 和 LinkedHashMap 也是依照加入先後為順序排列</font>，並且仍然保有HashSet、HashMap不重複的特性。

> 雖然很奇怪啦， 這兩位類別實作的是兩個無序集合的介面欸 :confused: ？

但其實蠻好理解的，就當作存進去的時候幫它們貼了流水號就好。

## 佇列（Queue）的資料結構

想像一個排隊的情境，第一個人買到食物之後，就會離開，他離開之後，原本的第二個人就會變成第一個人，直到最後一個人買到並離開。

佇列只能存取第一個元素，且第一個元素取出的同時也會被移除，一直到此佇列再也沒有元素可以取出、移除，成為一個空佇列（empty queue）。此現象姑且稱之為「**消化**」。

### PiorityQueue

* 擁有佇列（Queue）的特性
* ==元素依照大小順序排列==
* 有實作 Comparator 介面，可以讓使用者自行實作 `compare()` 方法，訂定排序規則

### PiorityQueue 的常用方法

* `boolean offer(E e)`：加入一個元素。<div style="margin-bottom:16px;" title="保持間距用"></div>
* `E poll()`：拿出並移除第一個元素，直到最後一個元素也被取出時，會回傳 `null` 。所以 ==同時可以被當作迴圈條件使用==。<div style="margin-bottom:16px;" title="保持間距用"></div>

    PriorityQueue pq = PriorityQueue();
	pq.offer("c");
	pq.offer("a");
	pq.offer("b");
    // 存放時就已依照大小順序排列
    
    String s; // 因為元素都是String，設一個變數來存放
    while((s = q.poll()) != null) (
        System.out.print(s + ", ");
        // 這邊就不要再poll()了，會又poll掉一個元素
    )

<div class="pm0">

:::warning
在 PriorityQueue 中：
<div style="margin-bottom:10px;" title="保持間距用"></div>

1. `add()` 和 `offer()` 使用上其實並沒有差別。
2. `poll()` <font color="red">不能寫成 `remove()`</font>，況且根本沒有這個方法，只有`remove(Object o)`（用來移除指定元素［若其存在的話］）。
3. 但都已經用 PiorityQueue 了，不要再用 `add()` ，避免方法一樣導致資料結構也搞混。
:::

</div>
<style>
.pm0 .alert ol {
margin-bottom:0;
}
</style>

## Comparator（比較器）介面
:::danger
請注意：本條目所指的並非 Comparable 介面或 `compareTo()` 方法（維基百科？）。
:::

### 使用時機

1. 想改變排序規則的資料，**是標準 API 的項目**（如：Integer、String 等）
* String 實作了 Comparable，也很貼心的幫你 Override 了比較的方法，即使你不喜歡它訂的排序，根本不可能去改標準 API

3. 想改變排序規則，但是**沒有原始碼可以調整**（別人寫的）
* 別人寫的類別原本就沒有實作 Comparable，你根本拿不到原始碼去 implements。
* 別人寫的類別實作了 Comparable，你很不滿意對方訂的排序，你也沒辦法改掉他寫的 `equals()` 方法

只要 ==你使用的物件類別無法實作 Comparable 介面 / 無法覆寫 equals() 方法== 都可以使用 Comparator 介面。

### 實作範例
例一：

class TestComparator implements Comparator<String> {
    @Override
    public int compare(int num1, int num2) {
        return num1 - num2;
    }
}

<span id="ex2">例二：</span>

class ArtistCompare implements Comparator<Song> {
// 注意泛型，必須和要比較的參數Song one, Song two型別相符
    @Override
    public int compare(Song one, Song two) {
    return one.getArtist().compareTo(two.getArtist());
    // 呼叫字串的比較來用
    }
}

<span id="ex3">例三（老師的範例，==使用**匿名內部類別**［Annonymous Inner Class］==）：</span>

Comparator<String> comparator = new Comparator<String>() {
// 這個匿名內部類別「實作」了Comparator介面並直接產生實例（建造物件）
    @Override
    public int compare(String a, String b) {
        return a.compareTo(b) * -1;
    }
};

:::warning
[覆寫方式](https://hackmd.io/@czyue/SynzuBxEd#Override-compareToT-target-方法)與 `compareTo()` 大致相同，但需要注意方法名稱為 `compare()`！
:::

### 呼叫範例

以[例二](#ex2)為例，呼叫實作 Comparator 的介面的 `sort()`，會以它覆寫過後的 `compare()` 為規則做排序：

List<song> songList = new ArrayList<song>();
// 陣列裡面的東西先略過不寫...
ArtistCompare artistCompare = new ArtistCompare();
// 建構自訂Comparator的實體
Collections.sort(songList, artistCompare);

以[例三](#ex3)為例：

PriorityQueue<String> pq = new PriorityQueue<String>(3, comparator);
// 請看下面說明
pq.offer("c");
pq.offer("a");
pq.offer("b");
String s;
while ((s = pq.poll()) != null) {
    System.out.print(s + ", ");
}

PriorityQueue 的建構子中有一個[奇行種](https://docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html#PriorityQueue-int-java.util.Comparator-)可用：

* `public PriorityQueue(int initialCapacity, Comparator<? super E> comparator)`

例三中的第一行就是在呼叫這個奇行種建構子。

PriorityQueue 裡的匿名內部類別實作了 Comparator 介面，在它類別的內部實作的 `compare()` 方法，就可以被拿來呼叫（例三中用建構子的第 2 個參數呼叫），用這個方法內的規則去排序 PriorityQueue 集合裡的元素。

## FIFO、LIFO 的資料結構

* **First-In-First-Out**：先進先出的「消化」特性，先排隊的人可以先買到、離開。
* 實作 Queue 集合介面的類別 **PriorityQueue 類別**

* [常用方法](#PiorityQueue-的常用方法)

* **Last-In-First-Out**：後進先出的「堆疊（Stack）」特性，盤子先放進來的通常都最晚被拿到，大家都是拿最後放進來的（最上方）。
* 實作 List 介面下 Vector 子介面的 **Stack 類別**
* 常用方法：

1. <font color=red id="stackpop">`E pop()`：取出（回傳）並移除 Stack 最上方（最後）的元素</font>。
2. `E peek()`：查看（回傳）但不移除 Stack 最上方（最後）的元素。
3. `E push(E item)`：將元素加入到 Stack 最上方（最後）的位置。
4. `boolean add(E e)`：將元素加入 Stack（繼承自父類別 Vector）。

## 參考資料
1. [DAY 03 : 線性串列](https://www.coderbridge.com/series/4166931ce56145259387d5834e172195/posts/adcf4d4382ef4e05ad41585d5f2efcda)
2. [Comparable 與 Comparator](https://openhome.cc/Gossip/Java/ComparableComparator.html)
3. [Head_First_Java_Second_Edition.pdf](https://www.rcsdk12.org/cms/lib/NY01001156/Centricity/Domain/4951/Head_First_Java_Second_Edition.pdf)
4. [匿名內部類別](https://openhome.cc/Gossip/Java/AnonymousInnerClass.html)
5. [Java匿名物件與匿名內部類](https://codertw.com/%E7%A8%8B%E5%BC%8F%E8%AA%9E%E8%A8%80/297946/)