Algorithms Part 1 — Week 2之Queues筆記

Free online course presented by Robert Sedgewick and Kevin Wayne

這篇將會概括PPT 1.3的以下內容:

• Queues
• Generics
• Iterators

Queues

• 跟排隊一樣，先進先出FIFO
• 可以用Linked-list實作，前後兩指針
• 也可以用Resizing array實作

Generics

當我們想要把同一個資料結構套用到不同類型上，就需要使用generics的概念，這樣就不用每個類型都要再重寫一次相同功能了，不僅容易出錯也非常的低效。

Casting也不是一個好方法，因為Cast必須要Client來操作，而且有錯的話會是runtime error，這非常不利於debug。

Welcome compile-time errors; avoid run-time errors.

因此我們使用Generics

• Client無須操作Casting
• Type mismatch可以在compile-time被發現，而不是run-time了

但在Java麻煩的一點是，雖然可以用，但是遇到array，我們必須這樣做(Item是泛型)

public FixedCapacityStack(int capacity) { 
  s = (Item[]) new Object[capacity]; 
}

而不是漂亮的

public FixedCapacityStack(int capacity) {
  s = new Item[capacity];
} 

這是Java天生的限制，我們只能服從😢

Iterators

讓我們可以疊代一坨東西的好工具，Client也無須知道內部的結構。
想讓自己的Class可以Iterate，那就要實作 java.lang.Iterable 介面。

其餘細節參照PPT

• 一樣可以用Linked-list實作
• Array也可以

補充

Java collections library其實不好用

• java.util.ArrayList 和 java.util.LinkedList 只有一些operations是efficient的
• java.util.Stack 也是過度開發，導致這些庫都變得臃腫低效

說實話聽到這些我很震驚，因為覺得發展這麼多年的Java，他的library應該是千錘百鍊，現在應該是最optimal的狀態，但沒想到有這些問題。這就是為何這門課，教授也是從頭自己打造API。

就是這些簡單的資料結構，打造出千變萬化的功能與應用，PPT裡也舉了一些例子。演算法蓬勃發展的時期至今不到百年，教授說可能還有很多演算法還沒有被發現，真是激勵人心的一句話😄雖然知道自己不太可能找到新的演算法，但會讓人期待又會有哪些未知的演算法出現。