顯示具有 queue 標籤的文章。 顯示所有文章
顯示具有 queue 標籤的文章。 顯示所有文章

2022/06/13

簡單輕鬆十分鐘學會 Tree & Binary tree & Binary search tree 刷 LeetCode

一秒理解資料結構裡的樹


一、Tree & Binary tree & Binary search tree

1.1 基本觀念介紹

1.1.1 Tree

是一種模擬現實生活中樹幹和樹枝的資料結構,分為 :

Root (根節點):沒有父節點的節點,所以每棵樹只有一個 root,如 A;在根節點之下是樹的樹枝,擁有 0 到 n 個子節點。

Node (節點):一個個連結點,如 A、B、C ... M 都是結點。

Parent (父節點) : 節點 B 是 I 和 J 的父節點。

Child (子節點) : 節點 I 和 J 是 B 的子節點。

Siblings (兄弟節點) : 擁有共同父節點,如 I 和 J、K 和 L 和 M。

Leaf (葉節點):節點沒有子節點的節點稱為葉節點,如 I、J、K、L、M、F、G、H。

Ancenstors (祖先節點) : 指某節點到根節點之間所經過的所有節點,都是此節點的祖先節點。

Level (階層) : 如果樹根是階層 1,其子節點即是階層 2,依序可以計算出樹的階層數;如節點A 階層是1,B、C 到 H 是階層 2,I、 J 到 M 是階層 3。

Height (樹高) : 又稱為 Depth (樹深),指樹的最大階層數,如此圖的樹高是 3。

Dregree (分支度):指每個節點擁有的子節點數,如節點 B 的分支度是 2,節點 E 的分支度是 3。

--
最廣義的樹對於 node 之 child 數目沒有限制,因此每個 node 可以有多個 child。

Linked list 也可以視作是樹只是每個 node 都只有一個 child。


2022/05/09

簡單輕鬆十分鐘學會 Stack & Queue (堆疊 & 佇列) 刷 LeetCode

一、Stack & Queue

1.1 基本觀念介紹

這裡講的 stack 和 queue,就是和 event loop 裡會用到的 call stack 和 callback queue 的基礎資料結構。

如果不是很清楚 event loop 是什麼,可以看這篇

Stack 和 Queue 常常用 array 或 linked list,但沒有限定,只要能實作出該資料結構即可。



1.1.1 Stack

Last in, First out (LIFO)

最後一個進去,第一個出來。

比如書籍堆疊起來,最後一本堆上去的會第一本先被拿走;


最下面 bottom 是第一個被放入的 frame,然後 frame 被一個一個堆起來 (push),

如果要把 frame 抽走,只能從最上方開始拿 (pop)。