Algorithms Part 1 — Week 2之Stacks筆記
Free online course presented by Robert Sedgewick and Kevin Wayne
這篇將會概括PPT 1.3的stack以及resizing arrays:
Stacks
對就是那個Stack，LIFO的資料結構。這門課的老師很強調把Client, implementation, 還有interface分開，因為有以下優點
Client不用知道實作細節，但可以完整使用
可以實做出modular, reusable libraries
效能上可以在需要的地方寫上optimized implementation
有點離題了，拉回來。個人覺得PPT裡寫得非常詳細，這裡就補充一些可能看不懂或是複雜的地方吧。
一開始PPT給的是StackOfStrings，存放string的stack，裡面有實作，請參考PPT。用Linked-list實作stack
看到這個PPT我才想起Java有inner class，很久以前有用過，但後來就沒必要也就沒寫過了。
如圖，而inner class的access modifier，也就是那個private無所謂，反正都存取得到。
而這個Stack會用到的Memory大約是40N，見下圖
注意實際String的內容都沒有算進來，只是算最少要多少，還加上了String的reference。
另外也可以用Array實作stack，code也在PPT裡面了。但目前需要傳入capacity，否則array最終會超出範圍。
Stack的隱憂與解法
Underflow: 如果在空的stack pop的話，拋出exception
Overflow: 用可變大小數組
Null items: 允許null item插入
Loitering: Garbage collector不知道可以回收，所以浪費了空間，解決方法參照PPT P.14
於是引出我們下一個主題
Resizing Arrays
如果每次超過array size就只增加到多出來的長度，那需要N²/2的時間才能插入從第一個到N個items，因為每次都要再copy。因此我們每次增加都直接增加兩倍，這樣就可以把時間壓到剩3N(不考慮新建一個array的時間)，因為很少需要擴充。這個行為叫做amortize攤銷。
而如果太多空間的話，我們每次剩一半以下就直接砍掉一半空間就好了?
不對，這樣如果有case是在一半的前一個push又pop，push又pop，這樣反反覆覆那時間會很可觀，因為每次要增加兩倍空間，接著又要去掉一半空間，每次操作基本上要N次。
那該怎麼做?在剩25%的時候shrink就好，這樣不會跟擴充array衝突，也能解決那樣極端的例子。
Stack的performance以及memory如何
這裡我不懂為何8N的時候是stack滿的時候，反而32N是只有25%滿…
教授說array來實作stack使用的空間比Linked-list還少
用resizing array還是Linked list實作stack
有好有壞，看怎麼選擇
