【C++】STL——stack&queue模拟实现

一、deque的简单介绍

**1.deque的物理结构 **

** deque是一种双向开口的连续性空间。所谓的双向开口，意思是可以在头尾两端分别做元素的插入和删除操作。**

2.deque的内部结构

** deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：**

** 从deque的结构图来看map就是一个指针数组， 数组中的每个元素是一个地址，地址分别对应了一块较大的连续空间，用来存储数据。**

** 需要注意：map中的元素我们称之为一个一个的buffer，当开辟第一个buffer时并不是从头开辟的，而是在从中间去开辟，当这个buffer指向的空间所存储的数据已满时，想要在这个这个buffer所指向的空间前插入元素时，就会在前面开辟一块同样大小的空间，在map数组中前一个buffer就会指向这段空间，以此类推。**

** **** deque是如何访问元素的呢？**

//假设有如下定义
deque<int> dq;

二、deque的迭代器

deque的迭代器是一个start类和finish类，分别包含了四个指针cur、first、last、node;

迭代器strart中:

cur ----- 指向此迭代器所指缓冲区中的现行元素开头

first ----- 指向此迭代器所指缓冲区的头

last ----- 指向此迭代器所指缓冲区的尾（含备用空间）

node ----- 指向的是管控中心

迭代器finish中:

cur ----- 指向此迭代器所指缓冲区中的现行元素结尾

first ----- 指向此迭代器所指缓冲区的头

last ----- 指向此迭代器所指缓冲区的尾（含备用空间）

node ----- 指向的是管控中心

通过cur指针来访问元素，当第一个buffer访问至结束时，通过node指针++操作，进入到第二个buffer，此时first、last也同时管控新的buffer；

三、为何要选用deque作为stack和queue的默认容器

stack和queue的默认容器是deque，我们仔细思考一下，在没有deque的情况下：

对于stack：我们也可以用** vector**** 和**** list**** ；**对于queue：我们只能使用 list ；

问题1：stack如果选用vector，相比选用deque，哪一个更好？为什么？

deque的优势在于：扩容代价不大，不需要拷贝数据，浪费空间也不大

问题2：stack&queue如果选用list，相比选用deque，哪一个更好？为什么？

deque的优势在于：cpu高速cache命中高，以为是一段连续的空间；此外，list需要频繁的申请小块空间。从申请和释放空间上来看，deque申请和释放空间次数少，代价低，唯一需要扩容的就是中控数组（map），但代价也很小。

总结：deque适合头尾的插入删除，但是中间插入删除和随机访问效率都差强人意。所有要高频随机访问还得是vector，要任意位置插入，还得是list；

四、stack的模拟实现

** 结合上面的分析，总结下来deque在设计出来的时候还是考虑到很多地方的，在模拟实现上，我们给模板的第二个参数加上Container，它接收的是容器，如vector、list**

#include<vector>
#include<list>

// 适配器模式
namespace mlg
{
    // 为了能够实现接收以下其他容器，模板参数需要加上Container
    // stack<int, vector<int>> s;
    // stack<int, list<int>> s;

    template<class T, class Container = deque<T>>//模板增加一个容器参数，给到缺省值
    class stack
    {
    public:
        //判断栈是否为空
        bool empty() const {return _con.empty();}

        //计算当前栈中有效元素的个数
        size_t size() const {return _con.size();}

        //取栈顶的元素
        const T& top() const {return _con.back();}

        //尾插（元素入栈）
        void push(const T& x) {_con.push_back(x);}

        //尾删（元素出栈）
        void pop() {_con.pop_back();}

    private:
        Container _con;//成员变量是未知的容器
    };

    void test_stack()
    {
        //stack<int, std::vector<int>> s;
        //stack<int, std::list<int>> s;
        stack<int> s;

        s.push(1);
        s.push(2);
        s.push(3);
        s.push(4);

        while (!s.empty())//判断栈是否为空
        {
            cout << s.top() << " ";//取栈顶的元素
            s.pop();//删除栈顶的元素，两个函数结合就能实现栈中元素出栈效果
        }
        cout << endl;
    }
}

五、queue的模拟实现

#include<vector>
#include<list>

namespace mlg
{
    // 为了能够实现接收以下其他容器，模板参数需要加上Container
    // stack<int, vector<int>> s;
    // stack<int, list<int>> s;

    template<class T, class Container = deque<T>>//模板增加一个容器参数，给到缺省值
    class queue
    {
    public:

        //判断队列是否为空
        bool empty() const {return _con.empty();}

        //计算当前队列中有效的元素个数
        size_t size() const {return _con.size();}

        //取队头的元素
        const T& front() const {return _con.front();}

        //取队尾的元素
        const T& back() const {return _con.back();}

        //队尾入数据
        void push(const T& x) {_con.push_back(x);}

        //队头出数据
        void pop() {_con.pop_front();}

    private:
        Container _con;//成员变量是未知的容器
    };

    void test_queue()
    {
        //queue<int, vector<int>> q;
        //queue<int, list<int>> q;
        queue<int> q;
        q.push(1);
        q.push(2);
        q.push(3);
        q.push(4);

        while (!q.empty())//判断队列是否为空
        {
            cout << q.front() << " ";//取队头的数据
            q.pop();//删除队头的数据，两个函数结合就能实现队列中元素出栈效果
        }
        cout << endl;
    }
}

** 最后，对于STL之前的几篇博客还要一个知识点未曾提及，那就是迭代器相关的，将会在后续的博客中进行介绍。**