从零开始手写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

这种情况下就要想到用栈