C++中的deque（双端队列）详解

创作时间:

作者:

@小白创作中心

C++中的deque（双端队列）详解

引用

CSDN

https://m.blog.csdn.net/2302_79331124/article/details/139473628

deque（双端队列）是C++标准模板库（STL）中的一种容器，它结合了vector和list的优点，可以在两端进行高效的插入和删除操作。本文将详细介绍deque的原理、使用场景以及为什么它被选为stack和queue的默认容器。

一、deque

1.1 deque的原理介绍

deque(双端队列)：是一种双开口的“连续空间”的数据结构。双开口的含义是：可以在头尾两端进行插入和删除操作，并且时间复杂度是O(1)的，与vector相比，头插效率高，不需要搬移元素；与list比较空间利用率高。

vector:连续的物理结构，优势：支持下标访问，劣势：扩容头部插入删除的效率低。
list:一块一块的分散结构，优势：按需申请释放任意位置插入删除的效率高，劣势：下标访问效率低，在标准库的实现中是不支持下标访问的。

以下是deque的图示：

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

双端队列底层是一段假象的连续空间，实际上是分段连续的，为了维护其“整体连续”以及随机访问的假象，落在了deque的迭代器身上，因此deque的迭代器的实现比较复杂，如下图所示：

deque借助迭代器维持假象的连续结构的原理：

中控数组的本质就相当于一个指针数组，中控数组中的每个元素指向一个小数组，从而实现一个连续空间的假象，其实是有一段段小的连续空间通过中控数组联系起来的。

1.2 deque的缺陷

与vector比较，deque的优势是：头部插入和删除时，不用挪动元素，效率比较高，而且在扩容时也不需要挪动元素，因此效率是一定比vector高的。

与list比较，deque的底层是一个伪连续空间，空间利用率高，不需要存储额外字段。

致命缺陷：deque不适合用来遍历，因为在遍历时deque的迭代器需要频繁的检测其是否移动到某段小空间的边界，导致效率低下，但是在序列式的场景下，可能要经常进行遍历，因此在实际中对于线性结构大多数的情况下还是优先使用vector和list，deque的引用并不多，deque作为stack和queue的底层数据结构是比较好的。

二、为何选择deque作为stack和queue的默认容器

1，stack和queue是不需要进行遍历的（因此stack和queue是没有迭代器的），只需要固定的一端或者两端进行操作。

2，在stack中元素增长时，deque比vector的效率高（因为扩容时不需要进行挪动数据）；queue中的元素增长时deque不仅效率高，而且内存使用率同样也高。

对于在作为stack和queue的底层容器是正好结合了deque的优点而且完美的避开了它的缺点。

三、deque的使用

3.1 stack的模拟实现：

template<class T, class Con = deque<T>>
//栈
class stack
{
public:
    //栈的构造
    stack() {}
    //push直接借助传入容器的push即可
    void push(const T& x)
    {
        c.push_back(x);
    }
    //pop借助容器的pop将栈顶元素即数组中的最后一个元素pop掉
    void pop()
    {
        c.pop_back();
    }
    //返回栈顶元素即数组的最后一个元素
    T& top()
    {
        return c.back();
    }
    const T& top()const
    {
        return c.back();
    }
    //返回栈内的元素个数，直接返回容器的size即可
    size_t size()const
    {
        return c.size();
    }
    //判断栈是否为空，直接判断容器是否为空即可
    bool empty()const
    {
        return c.empty();
    }
private:
    Con c;
};

3.2 queue的模拟实现：

template<class T, class Con = deque<T>>
//队列
class queue
{
public:
    //队列的构造
    queue() {}
    //进队列，先进先出，队尾进队头出，选择头插
    void push(const T& x)
    {
        c.insert(c.begin(), x);
    }
    //出队列尾删即可
    void pop()
    {
        c.pop_back();
    }
    //返回队尾元素，即返回容器的头
    T& back()
    {
        return c.front();
    }
    const T& back()const
    {
        return c.front();
    }
    //返回队头元素，即返回容器的尾
    T& front()
    {
        return c.back();
    }
    const T& front()const
    {
        return c.back();
    }
    //返回队列中的有效数据，即返回容器的size
    size_t size()const
    {
        return c.size();
    }
    //判断队列是否为空，即判断容器是否为空即可
    bool empty()const
    {
        return c.empty();
    }
private:
    Con c;
};