JavaScript 實作資料結構 – Stack 篇

Stack 以中文直翻的話,就是堆疊,可以理解成一直堆東西上去的感覺。
大家應該都有去大賣場的經驗吧? 如果有去過 Costco 應該更能體會貨櫃的 fu。
一脫拉庫的貨物一個一個由低到高,層層疊疊蓋上去。

「其實蠻像蓋飯的阿。」
「我看倒像一塊塊綠豆糕呢。」

堆疊的應用之處就像是程式語言中的 Compiler 和記憶體中貯存變數阿,遞迴阿,方法呼叫阿。
進一步來說,Stack 是種 FILO ( First In Last Out )的結構形式。
也就是說,資料若是最晚進去的,將會是最快出來的。
哀,人生有時候也是這樣不公平的吧,最晚出發的卻是最快抵達終點的。

Stack

不管啦,試著用 JavaScript 的語法實作看看堆疊吧。
先宣告這個類別吧:

當然你還需要一個陣列來儲存這些元素:

再來就是方法要先定義出來。

  • push(element): 新增一個元素到堆疊中。
  • pop( ): 從堆疊頂部移除元素,其值將會被 return 回來。
  • peek( ): 傳回堆疊頂部的元素,單純查看的動作。
  • isEmpty( ): 堆疊若為空則 true, 否則返回 false。
  • clean( ): 清除堆疊中的所有元素。
  • size( ): 傳回堆疊中的所有元素個數,類似於 Array 的 length 屬性。

首先來看看 push。

當你添加元素到堆疊時一定是,絕對是,鐵定是,鋼定是,你看,連鋼定是都出來了。
push 只會新增元素到堆疊的最尾端,也就是頂部,大致上可以這麼表示:

至於 pop 也能用類似的方法實做出來:

接著來看看 peek 方法吧,這是一個輔助用的察看方法,此外要記得,因為是用 Array 儲存的緣故,索引值都會是從 0 開始計算的:

再來到了 isEmpty 這個方法,我們通常會使用它來觀察堆疊是否為空的:

很快的來到了 size 這個方法,也就是想知道堆疊的元素個數的一個方法,上述有提到,跟 length 屬性頗多相似,那不如就用 length 實作吧:

Last but not the least, 來實作 clean 方法吧:

咦,都做了這麼多方法,不如把這些東西印出來看看吧:

很好,我們完成了整個堆疊的實作過程,全部彙整起來吧:

資料引用及圖片參考出處:

  • http://www.binarycoder.org/wp-content/uploads/2016/05/stack.png
  • Learning JavaScript Data Structures and Algorithms
  •  

    WeiChiaChang

    A junior web developer who fascinated by the charm of ruby and rails.