DSA_05：棧

棧，一個非常基礎、常用的數據結構。

其用途十分廣泛，如：

　　1. 理論上所有的遞歸都可以用非遞歸實現，其中絕大部分需要用棧。

　　2. 表達式求值演算法中要用棧。

　　3. 括弧匹配演算法要用棧。

　　4. 瀏覽器前進後退演算法要用雙棧。

　　5. DFS 演算法要用棧。

可以說用棧的地方數不勝數，因此，這是必須熟練掌握並能熟練應用的結構。

括弧匹配演算法：力扣第 20 題。

用數組實現的棧，我們叫作順序棧，用鏈表實現的棧，我們叫作鏈式棧

棧的基本規則：先進先出。

其他廢話不多說，這裡用 C++ 模擬一個幾乎與 STL stack 一樣的棧（當然會簡化一些東西，鏈式棧）。

相關介面及註釋已經寫於源碼中。

這是鏈式棧及基本操作：

源碼：

#include <iostream>
#include <iomanip>


/* 鏈式棧 */
template<typename _Ty>
class Stack
{
    // 定義節點結構
    struct Node
    {
        _Ty data;
        Node* next = nullptr;
        explicit Node(const _Ty& _data) :data(_data) {}
    };

public:
    Stack() = default;
    ~Stack();

    // 棧是否為空
    bool empty() const { return n_size == 0; }    // or return p_top == nullptr

    // 返回棧長度
    size_t size() const { return n_size; }

    // 返回棧頂數據引用
    _Ty& top() const;

    // 壓棧
    void push(const _Ty& _data);
    // 出棧
    void pop();

private:
    Node* p_top = nullptr;
    size_t n_size = 0;
};
template<typename _Ty>
Stack<_Ty>::~Stack()
{
    Node* temp = p_top;
    while (temp != nullptr)
    {
        p_top = p_top->next;
        delete temp;
        temp = p_top;
    }
    n_size = 0;
}
template<typename _Ty>
_Ty& Stack<_Ty>::top() const
{
    if (p_top == nullptr) throw std::exception("Stack is empty.");
    else return p_top->data;
}
template<typename _Ty>
void Stack<_Ty>::push(const _Ty& _data)
{
    Node* temp = new Node(_data);
    temp->next = p_top;
    p_top = temp;
    temp = nullptr;
    ++n_size;
}
template<typename _Ty>
void Stack<_Ty>::pop()
{
    if (p_top == nullptr) return;
    Node* temp = p_top;
    p_top = p_top->next;
    delete temp;
    --n_size;
}


int main()
{
    std::cout.setf(std::ios_base::boolalpha);

    Stack<int> sk;

    std::cout << "Empty?: " << sk.empty() << std::endl;

    std::cout << "Push datas..." << std::endl;
    for (int i = 0; i < 5; ++i) sk.push(i + 1);

    std::cout << "Now empty?: " << sk.empty() << std::endl;
    std::cout << "Now size: " << sk.size() << std::endl;
    std::cout << "Now top: " << sk.top() << std::endl;

    std::cout << "Pop top..." << std::endl;
    sk.pop();

    std::cout << "Now empty?: " << sk.empty() << std::endl;
    std::cout << "Now size: " << sk.size() << std::endl;
    std::cout << "Now top: " << sk.top() << std::endl;

    return 0;
}