#6 資料結構 - Stack - part 2

承接上一篇的內容,我們要用什麼方式來做 Stack 的 "容器" 呢? 我們前面提過 Array 和 List,你覺得那一個用來做為 Stack 的容器比較適當?

我們在前面談過 Array 和 List,兩者最大的差異在於物件位於記憶體上的位置是緊連在一起還是允許分散的.如果緊連在一起,則讀取速度快,如果是分散的,則讀取速度慢.光是這一點,我想 Array 就足夠成為我們做為 Stack 容器的人選了.接下來我們用一個簡單的模型來談如何用 Array 做 Stack 的容器.



上圖是一個 Array,這裡頭一開始宣告了 5 個空間,所以可以放 5 個物件,然後有一個變數用來記錄目前最新儲存物件的位置,在上圖用箭頭來表示它,所以一開始並不會有箭頭出現,因為一開始 Array 都是空的.當使用者呼叫 Stack 的 push() 時,就會寫入一個物件,此時箭頭沒有出現,所以這個物件就被放在編號 0 的位置,同時箭號也會出現在這個位置上.接著更多的物件會再進來,於是就往 Array 空的位置上放,但要照順序放,也就是編號 0 放完,就換到編號 1,同時箭頭也更新到編號 1 的位置.

如果使用者呼叫了 Stack 的 pop(),則 Stack 只要將箭頭所在位置的物件回傳出去,然後箭頭往左邊移動就行了,也無需刪除該物件,若有新物件再進來時,那位置上的舊物件就會被覆寫.

透過這樣的方式,你就可以簡單地實做了一個 Stack,透過一個容器和一個箭頭就能達成讓先進來的物件最後才被讀出.

接下來你可能會問一個問題,如果 Array 滿了怎麼處理? 你可以有兩個選擇,第一是丟出錯誤訊息說容器滿了,裝不下新東西了,第二個選擇是再建立更大的容器好應付更多的物件.第二點就和之前談過的 ArrayList 蠻相近的,當 Array 滿的時候,就要建立更大的 Array 或是更多新的 Array,然後再把新進來的物件放到新Array中.

由於宣告一個新的且更大的 Array 並且再把舊 Array 上的元素搬到新的 Array 上,這其實算是個蠻費力的工作,所以我們總不希望這樣的事情常常發生,因此,一開始的 Array 或許不會太大,但我們再建立新的 Array 時,我們可以建大一點.比如說,一開始 Array 長度像上圖一樣是 5,當這個 Array 滿了需要建立新的 Array 時,我們可以建立長度 15 的 Array,如果再滿了,則可以建立長度 45 的 Array.所以你可以看到要建立新的 Array 時,新的長度一定要比原長度還要再多 2 倍以上.因為我們也不知道使用者最後到底要多大的 Stack 來裝他的物件,因此這種循序漸進的變大方式對電腦效能的衝擊會小一點.

所以,當你有機會需要做類似 "undo" 功能的時候,記得用 Stack,比較方便也比較好懂,對後面維護的人來說也易於了解.

Share: