---
title: 真‧基礎資料結構
description: 介紹Stack, Queue與其實作
tags: 基礎資料結構
robots: noindex, nofollow
langs: zh
---
# 資料結構
> 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)
幾本上就沒什麼問題了