今日內容：Stack, Queue, Priority Queue, Linked List

Stack

import java.util.Stack;
// ...

// Stack<object> name = new Stack<object>();
Stack<Integer> intStack = new Stack<>();
Stack<String> strStack = new Stack<>();

LIFO (Last In First Out)，看起來像一個垂直的塔(Vertical tower)

• push(item) 在頂部加資料
• pop() 移除頂部的資料並回傳被移除資料的物件，所以可以另外寫一個變數去接被移除的東西
• peek() 直接看頂部的資料
• search(item) 用來尋找stack中是否有item這個物件，從stack的頂部(最後一個push的元素)往下搜尋，若有找到從1開始回傳(而非0)，如果沒有回傳-1
• empty() 檢查stack是否為空

直接print stack可以將stack內的所有元素以陣列形式列出

Stack常見的應用範疇：

1. 文字編輯器的Undo/Redo
2. 瀏覽器的上一頁/下一頁
3. backtracking algorithms (這個不知道是什麼)
4. 呼叫函式(call stack)

Queue

// java中的Queue是個interface，需要透過LinkedList或Priority Queue才能實作
import java.util.Queue;
import java.util.LinkedList;
//...

Queue<String> queue = new LinkedList<>();

FIFO (First In First Out)，像一個排隊的隊伍，Linear(線性) Data Structure

由於Queue extends from Collection，所以可以使用Collection這個class裡面的函式

• isEmpty() 檢查queue是否為空，回傳bool
• size() 查看queue大小，回傳int
• contains(item) 尋找queue中是否有item，回傳bool

Queue常見的應用範疇：

1. 鍵盤輸入緩衝(Keyboard buffer)，畫面上顯示的應該要和鍵盤上按的是一致的順序
2. 印表機
3. LinkedList, PriorityQueue, Breadth-first Search(BFS)

Priority Queue

import java.util.Queue;
import java.util.PriorityQueue;
// ...
Queue<Double> queue = new PriorityQueue<>();

FIFO (First In First Out)，就是Queue，但增加了優先級順序
會自動將加入的數值以小到大排序
如果要以大到小排序，可以在PriorityQueue的constructor改成(Collections.reverseOrder())

Linked List

用於解決ArrayList中，插入與刪除指定節點過久的問題(Array是O(n)，而LinkedList是O(1))
而Singly-Linked List包含資料本身與指向下一個節點(Node)的指標，因此不需儲存於連續的記憶體

Java中的LinkedList是Doubly-Linked List，包含前一個節點與後一個節點的指標
並且Java的LinkedList implements Deque(可以想成有兩端的queue)，可以在進行插入(addFirst addLast) / 刪除(removeFirst removeLast) / 查看(peekFirst peekLast)
而我們也可以將LinkedList作為Stack或Queue進行使用，意味著可以使用到push, pop, offer, poll這些函式

對於linkedlist，可以使用：
add(index, element)，可以直接在第index的位置插入element
remove(element)，會遍歷整個linkedlist，然後刪除第一個找到的element

import java.util.LinkedList;
// ...

LinkedList<String> fruits = new LinkedList<>();
fruits.add("Orange");
fruits.add("Grape");
fruits.addFirst("Apple");
// [Apple, Orange, Grape]
fruits.remove("Grape");
// [Apple, Orange]

優點：

1. 動態資料結構(可以在執行時分配記憶體空間)
2. 快速插入與刪除(O(1), 只需要修改指標)
3. 不會或很少有記憶體浪費

缺點：

1. 更多的記憶體用量(要多存"下一個位置"的指標)
2. 沒有random access，找資料時需要遍歷
3. 查找資料時會比Array久(O(n), 需要遍歷整個串列直到找到目標)

用途：

1. 實作Stack或Queue
2. GPS導航，給予起點和終點，進行路線規劃
3. 播放清單

結語

今天是學習Java入門資料結構的一天，主要是學到LinkedList怎麼用，可能會在之後的貪食蛇專案中用到，並了解與ArrayList的差異。
今天也是快樂學習的一天，明天繼續！