目录
前言
前面我们介绍了那个库里面的链表以及顺序表两个容器，通过这两个容器作为底层，我们可以去实现一些其他的数据结构，比如说今天我们要介绍的stack和queue，通过一个容器作为底层去封装实现另一个容器，这个过程在C++里面是适配器原理，这也是C++的一种设计模式。接下来的这篇文章，我们将着重介绍容器适配器以及stack和queen的模拟实现。
stack与queue
stack的定义：stack是一种容器适配器，只能从尾部插入和删除数据，可以支持以下操作：
1.empt():判空操作
2.back():获取尾部元素操作
3.push():尾部元素插入操作
4.pop():尾部元素删除操作
我们查看C++标准库中对stack的定义：
queue的定义： queue是一种容器适配器，只能在尾部插入数据，头部删除数据。可以实现以下操作：
1.empt():判空操作
2.back():获取尾部元素操作
3.front():获取头部元素
4.push():尾部元素插入操作
5.pop():头部元素删除操作
我们查看C++标准库中对queue的定义：
容器适配器
定义：适配器是一种设计模式，该模式就是将一个类的接口转换成客户希望的另一个接口。用通俗的话来讲就是一个类作为另一个类的迁移与转换。
举个例子，我们可以使用vector与list作为底层去实现stack的结构，具体怎么做呢？C++给我们提供的解决方案是通过传一个类模板，这个类模板的关键字是Container。可以参考下面代码，我们用vector来实现stack
template<class T,class Container=vector<T>>
class stack
{
public:
void push(const T&x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_back();
}
bool empty()
{
return _con.empty();
}
size_t size()const
{
return _con.size();
}
const T& top()
{
return _con.back();
}
private:
Container _con;
};对于queue而言，要实现头部删除，用vector作为底层头删效率过低，因此我们应该选择list作为底层，其代码如下所示：
template<class T,class Container=list<T>>
class queue
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
return _con.pop_front();
}
const T& back()
{
return _con.back();
}
const T& front()
{
return _con.front();
}
size_t size()const
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
};deque的介绍
可以看到，上述stack和queue的实现我们分别使用了vector和list作为底层，那么我们查看C++标准库中的实现会发现，C++标准库中并没有使用vector和list，而是采用了deque作为底层容器，如下图所示：
deque的定义：deque的名称是双端队列，是一种双开口的连续空间的数据结构，双开口的含义是可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与victor比较，头插效率高，不需要搬移元素与list比较，空间利用率比较高。
deque的底层
我们查看deque的源代码，如下图所示：
分析上述代码，我们看到deque的底层封装了一个中控指针数组map，里面保存每一个数组的第一个元素的地址，有两个迭代器分别指向中控数组的开始和结束，还有一个记录中控数组当中值的个数，那么我们此时就要查看deque的迭代器，如下图所示：
对于deque的迭代器而言，里面封装了四个指针，cur指向当前位置，first指向数组的第一个位置，last指向数组的最后一个位置，node表示当前数组在中控数组的位置。
由此我们可以看到deque里面既有顺序结构又有链式结构，所以它实际上是vector和list的复合体，在头部和尾部插入删除效率高，但有个致命缺陷就是顺序遍历效率低下。因此它成为了最适合stack和queue的容器。
deque的接口
我们可以看到，deque既支持迭代器访问也支持 【】遍历是vector和list的复合体
stack和queue的实现
stack模拟实现
template<class T,class Container= deque<T>>
class stack
{
public:
stack()
{
}
void push(const T&x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_back();
}
bool empty()
{
return _con.empty();
}
size_t size()const
{
return _con.size();
}
const T& top()
{
return _con.back();
}
private:
Container _con;
};queue模拟实现
template<class T,class Container=deque<T>>
class queue
{
public:
queue()
{
}
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
return _con.pop_front();
}
const T& back()
{
return _con.back();
}
const T& front()
{
return _con.front();
}
size_t size()const
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
};小结
本篇文章我们介绍了stack和queue的模拟实现以及适配器原理，通过适配器我们可以用其他容器封装实现另一个容器，并提供统一接口访问，极大提高了代码的可读性和书写的便利性。
感谢您在百忙之中能够看完本篇文章，如果本篇文章对您有所帮助的话，希望您能留下点赞评论加关注，您的支持就是我创作的最大动力。