# IT鐵人賽: 從零開始搞懂寫程式，資工系4年最重要的學科，資料結構，演算法，物件導向
###### tags:`資料結構`

[老師的筆記](https://hackmd.io/@ashleylai/js-ds-algo)
[小組討論筆記](https://hackmd.io/cx_dw4hUSm6ioo3NAA4VwQ?both)
[Link-list鏈結串列](https://www.youtube.com/watch?v=VBpA6KtMTtw)
[[C/C++] 鏈結串列(Linked List)](https://pisces1026.wordpress.com/2017/09/21/cc-linked-list/)
[IT鐵人賽: 從零開始搞懂寫程式，資工系4年最重要的學科，資料結構，演算法，物件導向](https://www.youtube.com/watch?v=gA815MIEFg0&list=PLhxdaTcUMi3nRM5mtOdQgO4VEtAEsTiYd&index=16)

### 陣列(array)
* 分為一維陣列二維陣列三維陣列
* 用來儲存有序串列的相同資料型別於==連續記憶體空間==
* ==需事先宣告記憶體空間==因此容易造成記憶體浪費
* 讀取與修改串列的資料時間==很快==
* 刪除加入新元素==需要移動大量資料==

### 連結串列(Linked list)
* 記憶體位置==不連續==以隨機的方式儲存
* 因為==不用事先定義好一塊連續的記憶體空間==，所以插入刪除資料都很方便
* 當想查詢特定節點時，必須==從頭==節點開始走訪

### 堆疊(Stack)
Last In First Out (LIFO): 後進先出，後疊的(後進)，先拿走(先出)。
Fisrt In Last Out (FILO): 先進後出，先疊的(先進)，最後拿走(後出)。
放進: 放進stack 的尾巴(疊盤子) ==> push
拿出: 從 stack 的尾巴拿出來(拿盤子) ==> pop
看一下最上面的是甚麼 ==> peek
Linked List比Array更容易實做stack

### 行列、隊伍、佇列、排隊(Queue)
First In First Out (FIFO): 先進先出隊伍(Queue) 是一種 先進先出 的資料結構。
Queue 的特性就是新增元素時發生在 Back後端，刪除元素時發生在 Front 前端。不像 Stack 新增刪除都是發生在頂端。
放進:放在最後面(排隊) ==> unshift enqueuing
拿出:先來的先出去(排隊) ==> shift dequeuing

### 集合(Set)
不能重複
可以取交集and
可以取聯集or
### 映射(Map)
key value

### 樹(tree)
degree兒子
sibling兄弟
level階層

節點(node)每一個圈圈
根(root)A圈圈
葉節點(leaf)下面沒東西的JKLMN
父(parent)J的爸爸是E
子(child)E的孩子是JK
兄弟(siblings)J的兄弟KLMN

levelorder tree traversal
從最上面開始
inorder tree traversal
從最左邊開始往右
==preorder tree traversal==
從根往右
==postorder tree traversal==
從下面開始走往右

圖graph:有迴路的樹
樹tree:沒有迴路的樹
二元樹binary tree:一個跟下面最多2個節點
完全二元樹complete tree:完全篩滿比較平衡
完滿樹full tree:
二元搜尋樹binarysearch tree:往左邊的比較小，往右邊得比較大
紅黑樹red black tree:比較像完滿樹

### 堆積(Heap)
上面小下面大(子孫比較大)
最小堆積min heap(上面最小)
最大堆積max heap(上面最大)

### 雜湊(hash)