STL——stack与queue的介绍及模拟实现

前言

stack与queue

容器适配器

deque的介绍

deque的底层

deque的接口

stack和queue的实现

stack模拟实现

queue模拟实现

小结

前言

前面我们介绍了那个库里面的链表以及顺序表两个容器，通过这两个容器作为底层，我们可以去实现一些其他的数据结构，比如说今天我们要介绍的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;
};