从零开始手写STL库：Stack
从零开始手写STL库–Stack的实现
Gihub链接：miniSTL
文章目录
- 从零开始手写STL库–Stack的实现
- 一、stack是什么？
- 二、stack要包含什么函数
- 总结
一、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
这种情况下就要想到用栈