---
# System prepended metadata

title: 基礎資料結構與演算法

---

Edited by 廖竑羿
# 資料結構 - STL 
Standard Template Library 或 標準模板庫

==c++ 中已經被寫好的資料結構、演算法模板==

需要使用時不必自己刻

## vector
    
動態的陣列，可以改變大小

常用操作：

```cpp=
#include<vector>
int main() {
    // 宣告 vector
    vector<int> vec;

    // push_back(): 將元素添加到 vector 的最後方
    vec.push_back(10);
    vec.push_back(20);
    vec.push_back(30);

    // pop_back(): 刪除 vector 的最後方元素
    vec.pop_back();

    // size(): 返回 vector 中元素的數量
    int size = vec.size();
    cout << "Size: " << size << endl;

    // at(): 根據索引獲取 vector 中的元素，並進行邊界檢查
    int element = vec.at(1);
    cout << "Element at index 1: " << element << endl;

    // vec[id]: 與陣列 arr[id] 相同，存取 vector 索引 id 的位置
    cout << vec[2] << endl;

    // clear(): 刪除 vector 中的所有元素
    vec.clear();

    // empty(): 檢查 vector 是否為空
    bool isEmpty = vec.empty();
    if (isEmpty) {
        cout << "Vector is empty" << endl;
    }
    else {
        cout << "Vector is not empty" << endl;
    }

    // vec.begin() vec.end() 回傳指標
    sort(vec.begin(),vec.end());

    // 遍歷 vector
    for (int i = 0;i < vec.size();i++) {
        cout << vec[i] << "\n";
    }
    for(auto i : vec){
        cout<<i<<'\n';
    }

}
```
                  
## stack
堆疊，先放進去最後出來
FILO -> first in last out
![](https://hackmd.io/_uploads/ByPIFtZqn.png)
```cpp=
#include<stack>
int main() {
    stack<int> myStack;

    // push(): 將元素放入堆疊
    myStack.push(10);
    myStack.push(20);
    myStack.push(30);

    // top(): 獲取最上方元素的值
    int topElement = myStack.top();
    cout << "Top element: " << topElement << endl;

    // pop(): 從堆疊丟出頂部元素
    myStack.pop();

    // empty(): 檢查堆疊是否為空
    bool isEmpty = myStack.empty();
    if (isEmpty) {
        cout << "Stack is empty" << endl;
    } else {
        cout << "Stack is not empty" << endl;
    }

    // size(): 回傳堆疊中元素的數量
    int size = myStack.size();
    cout << "Size: " << size << endl;

    return 0;
}

```
## queue
佇列，先放進去先拿出來
FIFO -> first in first out

![](https://hackmd.io/_uploads/BkZOYtZq3.png)
```cpp=
#include <queue>
int main() {
    queue<int> myQueue;

    // push(): 將元素添加到佇列的末尾
    myQueue.push(10);
    myQueue.push(20);
    myQueue.push(30);

    // front(): 獲取佇列前端元素的值
    int frontElement = myQueue.front();
    cout << "Front element: " << frontElement << endl;

    // pop(): 從佇列刪除前端元素
    myQueue.pop();

    // empty(): 檢查佇列是否為空
    bool isEmpty = myQueue.empty();
    if (isEmpty) {
        cout << "Queue is empty" << endl;
    } else {
        cout << "Queue is not empty" << endl;
    }

    // size(): 返回佇列中元素的數量
    int size = myQueue.size();
    cout << "Size: " << size << endl;

    return 0;
}

```
## set
```cpp=
int main(){
        // 定義一個 set
        set<int> mySet;

        // 插入元素
        mySet.insert(5);
        mySet.insert(2);
        mySet.insert(8);
        mySet.insert(1);

        // 檢查元素是否存在
        if (mySet.find(5) != mySet.end()) {
            cout << "5 is in the set\n";
        }

        // 遍歷 set
        cout << "Set elements: ";
        for (auto elem : mySet) {
            cout << elem << " ";
        }
        cout << "\n";

        // 刪除元素
        mySet.erase(2);

        // 再次遍歷 set
        cout << "Set elements after erasing 2: ";
        for (auto elem : mySet) {
            cout << elem << " ";
        }
}

```
## map
![](https://hackmd.io/_uploads/r1litYZqn.png)
```cpp=

int main() {
    // 定義一個 map
    map<int, string> myMap;

    // 插入鍵值對 兩種方式
    myMap[1] = "One";
    myMap[2] = "Two";
    myMap.insert({3, "Three"});
    myMap.insert({4, "Four"});

    // 檢查特定key是否存在
    if (myMap.find(2) != myMap.end()) {
        cout << "Key 2 is in the map\n";
    }

    // 遍歷 map
    cout << "Map elements: ";
    for (auto pair : myMap) {
        cout << "(" << pair.first << ": " << pair.second << ") ";
    }
    cout << "\n";

    // 刪除特定配對
    myMap.erase(3);

    // 再次遍歷 map
    cout << "Map elements after erasing key 3: ";
    for (auto pair : myMap) {
        cout << "(" << pair.first << ": " << pair.second << ") ";
    }
    cout << "\n";

    return 0;
}
```
## pair
```cpp=
#include <utility> // 包含 pair 所需的標頭檔

// 自訂比較函數，按第一個元素升序排序，如果第一個元素相等，則按第二個元素降序排序
bool customCompare(const pair<int, string>& a, const pair<int, string>& b) {
    if (a.first != b.first) {
        return a.first < b.first; // 第一個元素升序排序
    }
    return a.second > b.second; // 第二個元素降序排序
}

int main() {
    // 宣告一個 pair 變數，類型為 pair<int, string>
    pair<int, string> myPair;

    // 創建一個 pair
    myPair = make_pair(1, "Apple");
    myPair = {1, "Apple"};


    // first: 獲取 pair 第一個元素的值
    int firstElement = myPair.first;
    cout << "First element: " << firstElement << endl;

    // second: 獲取 pair 第二個元素的值
    string secondElement = myPair.second;
    cout << "Second element: " << secondElement << endl;

    // 可以直接使用初始化列表來創建 pair
    pair<int, string> anotherPair = {2, "Banana"};

    // 比較兩個 pair
    if (myPair < anotherPair) {
        cout << "myPair is less than anotherPair" << endl;
    } else {
        cout << "myPair is not less than anotherPair" << endl;
    }

    // 交換兩個 pair 的值
    myPair.swap(anotherPair);

    // 顯示交換後的值
    cout << "After swap:" << endl;
    cout << "myPair: (" << myPair.first << ", " << myPair.second << ")" << endl;
    cout << "anotherPair: (" << anotherPair.first << ", " << anotherPair.second << ")" << endl;

        // 宣告並初始化一個 vector<pair<int, string>>
    vector<pair<int, string>> myPairs = {
        {3, "Apple"},
        {1, "Banana"},
        {2, "Cherry"},
        {1, "Date"},
        {3, "Elderberry"}
    };

    // 使用 sort 函數和自訂比較函數進行排序
    sort(myPairs.begin(), myPairs.end(), customCompare);

    // 顯示排序後的結果
    for (const auto& p : myPairs) {
        cout << "(" << p.first << ", " << p.second << ")" << endl;
    }
    return 0;
}
```
## priority_queue
```cpp=
int main() {
    // 定義一個大的優先的 priority_queue
    priority_queue<int> maxHeap;

    // 插入元素
    maxHeap.push(3);
    maxHeap.push(5);
    maxHeap.push(1);
    maxHeap.push(4);

    // 查看最上方元素（最大元素）
    cout << "Top element: " << maxHeap.top() << endl;

    // 彈出頂部元素
    maxHeap.pop();

    // 再次查看最上方元素
    cout << "Top element after pop: " << maxHeap.top() << endl;

    // 使用自定義比較函數創建一個最小 priority_queue
    priority_queue<int, vector<int>, greater<int>> minHeap;

    // 插入元素
    minHeap.push(3);
    minHeap.push(5);
    minHeap.push(1);
    minHeap.push(4);

    // 查看最上方元素（最小元素）
    cout << "Top element of minHeap: " << minHeap.top() << endl;

    return 0;
}
```
# 演算法

## 貪心 - Greedy

## 二分搜尋 - Binary Search