本文代码已同步Github一、stack的介绍与使用1、介绍首先还是先给出stack的接口文档[stack使用参考文档](stack - C Reference)stack属于特殊的线性表其特点是LIFO(后进先出)对于stack我们在前期的数据结构中已经学过其结构特点同时通过数组来模拟实现其底层结构传送门数据结构入门栈实现全解析2、使用下面我们来看一下其接口相较于vectorliststack的接口少了很多我们同样整理出核心接口函数说明接口说明stack()构造空的栈empty()检测 stack 是否为空size()返回 stack 中元素的个数top()返回栈顶元素的引用push()将元素 val 压入 stack 中pop()将 stack 中尾部的元素弹出都是一些很简单的接口依次来使用二、stack的模拟实现注意⚠️我们先根据 stack 的数据结构特点完成最直观的模拟实现1、底层结构分析由于stack后进先出特殊结构我们该用什么样的方式来实现呢在前面学习数据结构时我们采用顺序存储的结构来进行模拟实现为什么选择顺序存储呢答案就是栈本身就可以被看成一个特殊的一维数组push就是尾插pop就是尾删top就是末尾元素那现在我们直接选择封装好的底层容器来进行模拟实现省去了造轮子的功夫对于push_back和pop_backvector和list都有这两个接口该怎么选呢stack只需要在一端进行插入和删除而vector的尾插、尾删都非常适合这一场景因此可以使用vector作为底层容器2、代码实现① 基础框架首先来完成基础框架的搭建底层采用封装好的vector//stack.h#pragmaonce#includevectornamespacestl{templateclassTclassstack{public:private:std::vectorT_v;};}下面来思考一下是否需要构造函数当成员变量是自定义类型时构造函数会调用自定义类型的构造函数对于内置类型则是未定义的行为‘显然当前类不需要手动实现构造函数② 核心接口实现核心接口其实就是调用底层的vector的接口即可public:voidpush(constTx){_v.push_back(x);}voidpop(){_v.pop_back();}Ttop(){return_v.back();}constTtop()const{return_v.back();}constsize_tsize()const{return_v.size();}boolempty(){return_v.empty();}下面来测试一下三、queue的介绍与使用1、介绍同样地先给出queue的接口文档[queue的使用参考文档](queue - C Reference)queue同样属于特殊的线性表其特点是FIFO(先进先出)对于queue我们在学习数据结构时已经通过链式存储进行实现同样给出传送门数据结构队列详解从概念到代码实现2、使用先来看接口整理出核心接口函数声明接口说明queue()构造空的队列empty()检测队列是否为空是返回true否则返回falsesize()返回队列中有效元素的个数front()返回队头元素的引用back()返回队尾元素的引用push()在队尾将元素val入队列pop()将队头元素出队列下面我们依次来测试使用四、queue的模拟实现注意⚠️我们先根据 queue 的数据结构特点完成最直观的模拟实现1、底层结构分析由于queue时先进先出需要多次头删vector显然就不合适了那么便采用list作为底层容器来说实现queue2、代码实现① 基础框架//queue.h#pragmaonce#includelistnamespacestl{templateclassTclassqueue{public:private:std::listT_lt;};}由于成员变量时自定义类型同样不需要手动实现构造函数编译器默认生成的构造函数对于自定义类型便会调用其构造函数② 核心接口和stack的模拟实现同理调用list的接口即可public:voidpush(constTx){_lt.push_back(x);}voidpop(){_lt.pop_front();}Tfront(){return_lt.front();}constTfront()const{return_lt.front();}Tback(){return_lt.back();}constTback()const{return_lt.back();}constsize_tsize()const{return_lt.size();}boolempty(){return_lt.empty();}来测试一下五、容器适配器1、介绍适配器模式容器适配器是 C 标准库中的一种类模板它本身不是完整的容器而是对底层容器如vector、deque、list的一层封装目的是提供更精简、更专用的操作接口。我们来看文档中对stack和queue的介绍发现对stack和queue的描述是容器适配器并非容器因此我们可以通俗的理解给通用容器套上一个“固定外壳”只保留特定场景需要的动作同时能够发现:stack和queue的底层采用的是deque作为容器为什么呢我们下一篇便会详细介绍2、优化代码为了和文档中使用的容器保持一致我们需要优化stack和queue的模拟实现先对刚才实现的stack进行优化其实就是加上deque作为类的模板参数//stack.h#pragmaonce#includedequenamespacestl{templateclassT,classContainerstd::dequeTclassstack{public:voidpush(constTx){_con.push_back(x);}voidpop(){_con.pop_back();}Ttop(){return_con.back();}constTtop()const{return_con.back();}constsize_tsize()const{return_con.size();}boolempty()const{return_con.empty();}private:Container _con;};}接着来优化queue的实现#pragmaonce#includelistnamespacestl{templateclassT,classContainerstd::dequeTclassqueue{public:voidpush(constTx){_con.push_back(x);}voidpop(){_con.pop_front();}Tfront(){return_con.front();}constTfront()const{return_con.front();}Tback(){return_con.back();}constTback()const{return_con.back();}constsize_tsize()const{return_con.size();}boolempty(){return_con.empty();}private:Container _con;};}当没有显示传入用什么容器作为参数时默认就会用缺省值deque来作为底层容器如果觉得有帮助可以关注Github项目持续更新