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;
}