新桥做网站,wordpress 自动 图片,semir是什么牌子衣服,丰都网站1. stack的选型 对于栈的实现是我们非常熟悉的过程#xff1a; C语言基础数据结构——栈和队列_栈和队列 插入取出数据-CSDN博客 _top表示下标#xff0c;_capacity表示空间大小#xff1a; 那么按照我们原来的思路#xff0c;利用_top和_capacity T*来给stack构形。
temp…1. stack的选型 对于栈的实现是我们非常熟悉的过程 C语言基础数据结构——栈和队列_栈和队列 插入取出数据-CSDN博客 _top表示下标_capacity表示空间大小 那么按照我们原来的思路利用_top和_capacity T*来给stack构形。
templatetypename T
class stack {
public:
private:T* _arr;int _top;int _capacity;
}; 如果只是按照c语言的思路来实现一个T*的多接口数组就显得有些重复了。 2. 容器适配器
2.1设计模式 设计模式就像兵法一样不是直接拿着刀就上去看早期的代码都会相对无序而是要讲究套路和方法的要注重可维护性。只完成了功能的要求但是在后期如果要debug或者打补丁就很麻烦。现在的设计模式有23种。 我们现在已经或多或少接触了两种设计模式一种是迭代器模式一种是适配器模式。 比如迭代器模式 容器适配器一般都没有iterator因为iterator的出现会改变其最本质的访问方式。 2.2适配器
适配器是一种用于转换的装置 适配器适配器的功能就是转换 比如电源适配器。高压线中的电变压到220v的生活用电也需要电源适配器220v通过充电线变成给手机的几伏充电线也需要电源适配器。 那什么是容器适配器呢 栈就是容器适配器队列也是容器适配器。 我们可以自己手搓数组来实现各个接口。那既然要如上文的C语言思路一样使用数组为什么不直接用vector呢 既然能用vector去适配一个栈出来那为什么不能用list去适配一个栈出来呢如下 templatetypename T
class stack{
public:
private:listT _st;
}; 或者
templatetypename T
class stack{
public:
private:vectorT _st;
}; vector和list中都肯定包含push_back pop_back back front这些函数 直接去套用即可。那么我如果两个容器都想使用呢实现两个非常接近的容器适配器吗 显然不是我们直接在模版处传入我们想使用的容器。 3.代码实现
直接在template处多写一个typename方便传容器类型。 如果传入的容器不能使用push_back说明这个容器不能用于适配报错即可。 模版参数就像函数参数一样也可以给缺省值。
比如我们此处就默认stack是包装vector实现的。 templatetypename T,typename Container vectorint
class stack {
public:void push(const T x) {_st.push_back(x);}void pop() {_st.pop_back();}T top() {return _st.back();}const T top() const {return _st.back();}bool empty() {return _st.empty();}size_t size() {return _st.size();}private:Container _st;};
就可以直接像正常的vector那样使用了。 或者用list去作为适配的容器 再用代码来实现queue queue适合用vector作为容器来适配吗 在stack中的插入删除都在尾部栈顶进行vector恰好在尾部进行操作比较简单比较吻合。 而queue既需要在尾部操作又需要在头部操作所对于vector这种头插头删时间复杂度都是O(n)的容器来说就不是非常合适。因此我们认为vector不能用于适配 这是用vector实现的方法 但是代价太大了。 所以我们将queue按照list和deque作为可适配的容器实现
templatetypename T,typename Container listint
class queue {
public:void push(const T x) {_q.push_back(x);}void pop() {_q.pop_front();}bool empty() {return _q.empty();}T front() {return _q.front();}const T front() const {return _q.front();}T back() {return _q.back();}const T back() const {return _q.back();}size_t size() {return _q.size();}
private:Container _q;
};
测试 4. 初识deque双端队列 list可以头插头删和尾差尾删 vector支持尾差尾删和方括号访问当然头插头删可以通过insert和erase实现但是时间复杂度较高 deque就是list和vector的结合体 那是不是用deque来实现stack和queue的适配更方便呢 底层结构天差地别但是实际使用效果似乎都不错。
