2022 Medium 新版傳送門

資料結構 - 樹和堆疊

今天會講到資料結構中比較複雜的部分，
但是這些複雜的結構也可以用很簡單的方式，理解到他們的機制，
現在來看一下吧～

樹 ( tree )

樹資料結構圖，就是跟大家都知道的『 樹 』很相似（不知道樹長怎樣的...痾...）
附上一張來自維基百科的『 樹資料結構截圖 』:


有沒有跟樹很像呀？
他的特色就是每筆資料，都是一個『節點』，英文稱作 node ，
例如圖片中 『 A 』 這個節點繼續往下延伸，那這個『 A 』就會是一個『父節點』，
延伸下去的 B 和 C 就是『 子節點 』，
那 C 後來又有所延伸，那他又會是 G 和 H 的『 父節點 』，
也會是 A的『子節點』。
利用程式寫起來可以像是這樣:

class Company
	attr_accessor :ceo_name
	def initialize(name)
		@position = Position.new(name)
	end
end

class Position
	attr_accessor :name
	attr_accessor :left, :right
	
	def initialize(name)
		@member_name = name
		left = nil
		right = nil
	end
end

這是一個模擬公司組織結構的樹狀資料結構，
公司下都會有個『位置』的節點，然後每個位置下都會再有其他的位置，
分別是 left 和 right 來儲存這個位置。
而你看到的 nil ，就是 ruby 中 null 的意思～

堆疊 ( stack )

堆疊，是一種類似陣列的資料儲存方式，
只是他比較像在堆樂高，是把資料從下面往上排，
類似這樣的方式:


讀者也會注意到，圖中有『push』和『pop』兩個詞彙，
push 是把資料放入堆疊中的意思，pop 則是把資料從堆疊中取出之意。
除了堆疊外，很類似的資料結構也有佇列 (Quene), 堆( Heap ) 等等，

有興趣更深入的讀者，歡迎參考;
(Array)、堆疊(Stack)、佇列(Queue) - Mark Lin Blog - Logdown

Java 面試 02 - JVM 的 Stack 和 Heap

那 Stack 的用處為何呢？
目前最常使用在『錯誤訊息』的傳遞上，
當程式出錯時，會提供錯誤發生在程式碼的第幾行，
但在大型的程式中，可能這樣的資訊還不夠，
因此會把『使用發生錯誤程式』的『程式碼』給在列印出來。
聽起來應該有點玄唷～
大家對 function 函式設計的理念還有印象嗎？
我們會用 function 去包裝不同的程式，
而這個 function 可能是其他 function 執行的，
因此發生錯誤的程式碼，外面可能包了十幾層，
而造成錯誤的真實原因，可能是在倒數第 3, 4 行的位置。

來看看下面這個真實的錯誤堆疊案例:


最上面的，就是 stack 內最新的資料，也就是程式碼錯誤發生的地方，
是在 front_controller.rb 第 248 行中， tender 這個函式內，
看到第二行，tender 這個函式，又是 basic_implicit_render 第 4 行的 send_action 函式執行的，
剩下的以此類推...
因此可以很方便的知道說，資料的順序相依性～
這樣大家能懂堆疊了嗎？

結論

筆者這兩天只講解了資料結構最常用的幾種，
並且也只提到這幾種中，基本常用的概念，
分別都還是有一些進階的概念，像樹( tree )也會有二元樹、完全二元樹等等不同的類型，
對於讀者們來說，最重要的概念不是哪種資料結構最好，
而是懂得針對不同環節，去使用不同的資料結構儲存資料，
才能展現更好的程式效能，並進一步的增進使用者體驗喔～～

如果有任何問題，或是指證文中的錯誤，歡迎寄信給我或留言在下面喔～