資料結構

Algorithms + Data Structures = Programs
- by Niklaus Wirth

資料結構就是一種有效儲存資料的方式，使得你可以在特定複雜度的時間與空間內取出資料，並利用它的特性來解決麻煩的問題

Stack (棧)

後進去的人先出來，稱之LIFO(Last In First Out)

實作

一個陣列+一個變數紀錄stack尾部

template<typename T>
class Stack{
private:
    vector<T> content;
    // top 指向最後面有空位的地方
    size_t _top;
public:
    Stack(){
        _top = 0;
    }
    void pop(){
        // 我懶得回收空間了
        // 反正你只要把Top指針往後移，東西就假裝被你變不見了
        // 即使他還在記憶體中
        --_top;
    }
    T top(){
        return content[_top-1];
    }
    void push(T val){
        // 若陣列不夠大就先讓他變大
        if(content.size() <= _top) content.resize(_top);
        // 把東西先放進空位再把指針向後移 OwO
        content[top++] = val;
    }
}

這樣就是一個優雅的Stack了
事實上C++98開始就有提供stack這個STL容器了
可以#include <stack>來使用

複雜度

插入	移除	存取
$O(1)$	$O(1)$	$O(1)$

Queue(佇列)

先進去的人先出來，稱之FIFO(First In First Out)

實作

用陣列很不方便
我自己個人會偏好使用雙向Linked List來實作

複雜度

插入	移除	存取
$O(1)$	$O(1)$	$O(1)$

Linked List (串列)

「真像人形蜈蚣啊。」一位外號叫「大食客」的同學緊接著說。

結構如圖所示，有著快速於尾端插入移除與存取的特性，也可以輕鬆地從中間移除某個元素，缺點就是隨機存取(任意存取任意位置的元素)的速度很慢

實作

真的要我實作喔，我好懶喔

template <typename T>
class List{
private:
    T content;
    List *prev, *next;
public:
    List(){
        prev = next = nullptr;
    }
    void insert_next(T cont){
        // 記下原本的下一個節點
        List *n = next;
        // 把新節點弄出來
        next = new List();
        next->content = cont;
        // 讓現在的下一個節點的下一個人指向原本的下一個節點
        next->next = n;
        // 新節點的上個人就是自己
        next->prev = this;
        // 原本的下個節點的上個節點 現在要是新節點
        if(n != nullptr){
            n->prev = next;
        }
    }
    List* get_prev(){return prev;}
    T get(){return content;}
}

懶得刻移除了XDD
但概念與插入相仿
一樣要記得好好處理麻煩的飛來飛去的指標
還有new出來的東西一定要delete掉(不然等等記憶體洩漏我坐等你MLE)
幾本上就沒什麼問題了