从零开始手写STL库：Stack

从零开始手写STL库–Stack的实现

Gihub链接：miniSTL

一、stack是什么？

栈是一种后进先出（LIFO，Last In First Out）的数据结构

这意味着最后被压入栈的元素将是第一个被弹出的

这种结构类似于一堆叠放的盘子，只能在顶部添加或移除盘子

底层实现可以使用deque，也可以是list或者vector，取决于使用场景，STL库中默认是deque，也可以修改

这里使用之前实现的myDeque作为底层进行栈的搭建，同样的也是一层封装

二、stack要包含什么函数

必要的三个函数：push, pop 和 top

不过这里留下一个接口，用于修改实现底层

template <typename T, typename Container = myDeque<T> >
class myStack
{
private:
    Container data;  // 修改container，并且对应地函数名称改一改就可以了

public:
    void push(const T & value)
    {
        data.push_back(value);
    }

    void pop()
    {
        if(data.empty()) throw std::runtime_error("Stack is empty!");
        else data.pop_back();
    }

    T& top()
    {
        if(data.empty()) throw std::runtime_error("Stack is empty!");
        else return data[data.getSize()-1];
    }

    size_t size()
    {
        return data.getSize();
    }

    bool empty()
    {
        return data.empty();
    }
};

总结

栈并不会在面试场景中出现太多，更多的是在笔试中，如判断括号是否平衡，如力扣20

这种情况下就要想到用栈