1.stack的模拟实现
在这一部分嘞，我们不再用传统的模拟实现来实现今天要实现的内容，我们使用一种设计模式来实现今天的内容
设计模式
目前接触到的设计模式一共有两种：一种是适配器模式，一种是迭代器模式
迭代器设计模式
迭代器大家都熟悉，在string,vector,list中算是老朋友了，它为我们访问容器提供了一种统一的方式，在知道迭代器这种东西之前，我们访问数据，肯定是要知道该容器的结构细节才能访问的，比如，对于顺序表，你要知道它的底层是数组你才知道如何访问它的数据，对于链表，你要知道它的底层是一个一个的节点，你才知道要如何去访问它的数据，然而，迭代器的出现，为我们访问数据提供了一种统一的方式，它屏蔽了底层的细节
适配器设计模式
适配器大家生活中比较常见的就是电源适配器器，它的作用就相当于变压器，在不同的电压下都能够保证你的手机能够充上电，如果说迭代器的思想是封装的话，那么适配器的话就是转换，那么，让我们来看看，适配器在这一部分的应用
适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口
stack的模拟实现代码
#include<iostream>
#include<deque>
//
using namespace std;
//设计模式-适配器模式-主要是封装转换
namespace bit
{
template<class T,class Container=deque<T>>
class stack
{
public:
void push_back(T x)
{
_con.push_back(x);
}
T& top()
{
return _con[_con.size()-1];
}
void pop()
{
_con.pop_back();
}
bool empty()
{
return _con.empty();
}
size_t size()
{
return _con.size();
}
private:
Container _con;
};
void test_stack01()
{
stack<int> s;
s.push_back(1);
s.push_back(2);
s.push_back(3);
s.push_back(4);
cout << s.size() << endl;
while (!s.empty())
{
cout << s.top() << " ";
s.pop();
}
cout << endl;
}
}上面用一个deque容器实现了一个stack,当让，这里也可以用其他的容器，比如，vector,list来实现，容器选择不唯一，这就是适配器模式，用别的容器来实现你想要的容器，肯定有人会好奇，deque是什么，那下面，我们就来介绍一下
deque
deque是我们得双向队列，什么意思嘞
从它得成员函数来看，它实现了头尾元素的插入删除，功能上是有点向vector和list的结合体，
我们知道vector的优点是：下标访问效率高
缺点是：头部插入删除需要挪动数据，效率非常低
list优点：任意位置插入删除只需要改变指针的指向，效率高
缺点：下标访问效率低
而deque刚好就结合了它们两个的优点：下标访问效率还可以，头部插入删除效率也高，那我们来看一下它的初略结构
deque的大致结构
deque的结构就是这样一个一个的bufer的数组，每个数组可以存储一定量的个数，当想要尾插数据的时候，如果数据个数达到容量的时候，就会在后面再插入一个数组，如果想要头插一个，就再前面再多插入一个数组
那它的下标访问是如何进行的，请看下图：
但是,deque的也是有缺点的
再上面的程序中，vector和deque中都有一定量的数据，对里面的数据进行排序，再计算两者排序需要用的时间，发现deque要用到的时间高出vector很多
那我们再来看一下下一个程序
再这个程序里面嘞，我们是把deque里面的数据拷贝到vecror里面，等到vector里面的数据排序完了，再把vector的数据放回deque里面 ，发现deque的排序时间、依然然高出后者的很多
那到这里我们就做一个总结：
deque的真实结构
首先，有两个迭代器，start迭代器指向第一个元素，finsh的迭代器指向最后一个元素的下一个位置
这里的operator*操作，就是取当前cur指向的元素
这里的operator++就是，当cur走到了当前数组的last位置，就该迭代器就就指向下一个node,也就是下一个数组
还有就是头插
queue的模拟实现
#include<iostream>
#include<queue>
#include<deque>
using namespace std;
namespace bit
{
template<class T,class Container=deque<T>>
class queue
{
public:
void push_back(T x)
{
_con.push_back(x);
}
T& top()
{
return _con[0];
}
void pop()
{
_con.pop_front();
}
bool empty()
{
return _con.empty();
}
size_t&size()
{
return _con.size();
}
private:
Container _con;
};
void test_queue01()
{
queue<int> q;
q.push_back(10);
q.push_back(20);
q.push_back(30);
q.push_back(40);
while (!q.empty())
{
cout << q.top()<<" ";
q.pop();
}
cout << endl;
}
}为什么使用deque作为默认容器
tack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性结构，都可以作为stack的底层容器，比如vector和list都可以；queue是先进先出的特殊线性数据结构，只要具有push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如list。但是STL中对stack和queue默认选择deque作为其底层容器，主要是因为：
1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。
结合了deque的优点，而完美的避开了其缺陷。
