資料結構：電腦儲存資料的方式，例如陣列。
Stack 堆疊
- 疊盤子，後進先出。
Queue 佇列
- 排隊，先進先出。
Deque 雙端佇列
- 念作 “deck”。
- stack+queue=deque.
Linked List 連接串列
- 對每個資料紀錄前後資料的位置。
- 可以 O(1) 加入、刪除特定資料。
- 不能 O(1) 存取指定 index 的資料。
Vector
- 多功能陣列。
- 【筆記】C++ Vector
Pair
- #include <utility>
- Pair：只有兩個參數的 struct。
pair<int,int> p;
p = make_pair(5, 3);
cout << p.first << ' ' << p.second << endl;Heap 堆積
- 一個能維護極值(最大值)的資料結構。
- 功能：存取、刪除 heap 最頂端(極值)的資料。
- 複雜度：O(log N)
- STL提供的 heap 叫做 priority_queue。
- Binary Heap Tree
#include <queue>
priority_queue<int> heap;Set 集合
- Set = 集合 = 元素不重複
- 有排序的。
- 可以插入(insert)、刪除(erase)、尋找(find)資料。
- set.count(87) 回傳該元素是否存在。
- 可以利用 prev() , next() 得到前後的 iterator。
- 尋找值大於等於自己的第一個 iterator：set.lower_bound(87);
- 尋找值大於自己的第一個 iterator：set.upper_bound(87);
- Disjoint Set 併查集：詢問兩元素是否在同一集合、合併兩個元素所在的集合。
for(set<int>::iterator i=s.begin(); i!=s.end(); i++){
cout << *i << endl;
}Map 映射
- 一個 key 對到一個 value，key 不可重複，value 可以重複。
- 插入、修改、刪除、尋找
- map 是有序的(按照 key 排序)。
map<int,int> m;
m.insert(pair<int,int>(1,11));
m.insert(pair<int,int>(2,22));
m.insert(pair<int,int>(3,33));
for(map<int,int>::iterator i=m.begin(); i!=m.end(); i++){
cout << i->first << ' ' << i->second << endl;
}