【C++】STL——容器适配器 queue 深度剖析及模拟实现

queue的介绍

queue的文档介绍

队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端

提取元素。

队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的

成员函数来访问其元素。元素从队尾入队列，从队头出队列。

底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操

作:

empty：检测队列是否为空

size：返回队列中有效元素的个数

front：返回队头元素的引用

back：返回队尾元素的引用

push_back：在队列尾部入队列

pop_front：在队列头部出队列

标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。

相信对于queue（队列）也不用给大家过多介绍。

3.2 queue的使用

4. queue的模拟实现

那我们来快速模拟实现一下：

#pragma once
#include <list>//如果在test.cpp里包，不放在这里也可以，不会报错（虽然下面用到了list）
//因为头文件不会被编译
namespace yin
{
    template <class T, class Container = list<T>>
    class queue
    {
    public:
        bool empty()
        {
            return _con.empty();
        }
        size_t size()
        {
            return _con.size();
        }
        //取队头数据
        const T& front()
        {
            return _con.front();
        }
        //取队尾数据
        const T& back()
        {
            return _con.back();
        }
        //队尾入数据
        void push(const T& x)
        {
            _con.push_back(x);
        }
        //队头出数据
        void pop()
        {
            _con.pop_front();
        }
    private:
        Container _con;
    };
}

就写好了。

但是大家思考一下：

queue也是容器适配器，那它的基础容器可以是什么呢？

还可以是vector吗？

是不是就不行了啊，因为vector是不是没有pop_front这个接口啊。

当然你也可以借助erase去搞，但效率是不是不好啊。

所以我们可以用list：

当然库里面默认给的还是deque。

来试一下：

没问题。

5. STL标准库中stack和queue的底层结构

通过上面的学习我们知道：

虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和queue的底层只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque。

那deque是个啥呢，我们一起来了解一下。

6. deque的简单介绍(了解)

6.1 deque的原理介绍

deque叫做双端队列，怎么理解它呢？

🆗，那其实从它的功能上来看，我们可以认为它是vector和list的一个结合体.

我们可以来看一下它的接口：

是不是好像vector和list有的功能它都同时具备，那这样看来，deque好像是个很牛逼的设计。

但是，大家想一下，它是否真的很牛逼？

如果它真的是一个很牛逼的设计，那我们数据结构的书上为什么没有学它呢？既然它这么牛，兼具vector和list的功能，那vector和list是不是就可以被淘汰了？

那它的底层到底是怎么样的呢？我们来简单了解一下：

6.2 deque的底层结构

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

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

直接看这个图，大家肯定很懵，这里给大家浅浅的解释解释：

我们数据结构阶段学过顺序表和链表，并分析过它们各自的优缺点：

那deque的产生呢大家就可以认为是想对顺序表和链表的优点进行了一个结合。

那它是怎么做的呢？

🆗，那deque其实是这样来搞的：

它是由一段段连续的小空间拼接而成的

最开始有一块空间，用完的话，我不去扩容，而是再去开一块小的空间，再用完了再去新开…

那如何把这些多个的小空间给管理起来呢？

🆗，它呢又开了一个数组，这个数组是一个中控的指针数组，用来存储指向这些小块空间的指针。
但是，从开第一个小空间开始，它的指针是从中控数组的中间位置开始存储的：

那这样的话，如果要头插的话，我们需要像vector那样挪动数据吗？
🆗，不需要，就可以这样做：

尾插如果最后一个小数组后面还有空间，可以直接往后放，没有的话，就可以这样：

那大家想：

它这样的结构有没有扩容的概念（不断开小数组的过程可以认为不是扩容）？

（至于小数组是否会扩容大家可以自己控制）

🆗，它也会引发扩容，什么时候呢？

是不是中控数组满了的话就需要扩容啊。

中控指针数组扩容的话是不是代价就比较低啊，因为只拷贝指针嘛，而且是一个小数组才需要拷贝一个指针。

所以到现在我们可以得出：

与vector相比，deque的扩容代价是很低的，另外这样的结构，deque在头部尾部插入和删除数据是不是不需要挪动数据，效率比较高。

然后大家再思考一个问题：

deque支持下标的随机访问要怎么做到？

首先deque这样的结构，要进行随机访问，效率上肯定是没有vector高的，vector的话通过指针一加就直接访问到了。

那deque如何进行随机访问呢？

那就要去算访问的数据在第几个小数组。比如现在是这样的：

要访问第25个数据怎么办？

是不是要先减去第一个小数组的3个，然后/10，就可以得到它在第几个小数组里，%10，就可以得到它在第几个位置。

但是，它应该是比list随机访问的效率高的。库里面list压根就没提供operator[]，为什么？就是效率太低了嘛。

6.3 deque的优点

那上面分析的这些可以认为是deque的优点：

1. 与vector相比，扩容代价低
2. 头部尾部插入和删除数据是不需要挪动数据，效率比较高
3. 支持随机访问且效率比list好

6.4 deque的缺点

那它有没有什么缺点呢？

🆗，它的中间插入删除是不是很难搞啊。

当然这里采用不同的实现可能会导致效率不同。

第一种方案是每个小数组（一般叫做buff数组）的大小可以不一样，不固定，可以每个数组配一个size和capacity去控制（那这样是不是就和vector很像了），这样如果删除中间某个数据就可以只挪动当前的这一个小数组里面的数据，后面的不用动。

那这样在中间进行插入删除就会好一点，但是，这样是不是对随机访问就造成了影响，我们就不能像上面那样直接除、直接模去计算了，因为每个小数组大小不一样，那就要一个一个去减了。

那这样随机访问的效率就下去了。

而如果每个数组大小一样，中间插入删除挪动数据量是不是就大了。

所以说很难搞，当然这两种方式都可以。

那这里告诉大家SGI版本的STL里面是采用的固定大小，每个小数组大小一样。

那还有没有其它缺点？

🆗，我们看到deque看似好像兼具了vector和list功能，兼具了两者的优点，但是，这些优点在deque身上是不是没有vector和list极致啊。

6.5 为什么选择deque作为stack和queue的底层默认容器

那经过上面的分析：

我们发现，deque最突出的一个优点是啥？

是不是就是头插头删、尾插尾删效率很高啊。

而我们的stack和queue是不是都是只在两端进行操作啊，所以说deque用来作为stack和queue的底层默认容器是不是确实非常适合啊。

所以：

stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性结构，都可以作为stack的底层容器，比如vector和list都可以；queue是先进先出的特殊线性数据结构，只要具有

push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如list。

但是STL中对stack和queue默认选择deque作为其底层容器，主要是因为：

stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作，而deque头插头删、尾插尾删效率很高.

在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高（与list相比）。

结合了deque的优点，而完美的避开了其缺陷。

6.6 deque的迭代器了解

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

那deque的迭代器是什么工作原理呢？

大家来尝试看一下这张图。

我们看到deque的迭代器由四个指针组成，首先大家看出来cur指针指向的是哪里吗？

🆗，cur就是指向迭代器当前对应的那个位置，我们看到图中start的cur指针指向第一个元素的位置，finish的cur指针指向的就是最后一个元素的下一个位置。

然后，first和last就是指向其对应buffer数组的起始和结束位置。

node呢？

是不是指向其对应buffer数组的地址在中控指针数组中存储的位置。

那再问大家，如果有一个迭代器it，*it如何拿到该迭代器对应位置的数据？

🆗，是不是*cur就拿到该数据了。

那++cur是怎么走的？

如果cur不等于last，是不是++cur就行了；但是如果++cur走到last，那当前这个buffer数组是不是就遍历完了，再往后遍历的话就要去访问下一个buffer数组了，怎么办？

那这时候node是不是就起作用了，node++是不是就拿到下一个buffer数组的地址了，然后就可以访问了。

那这就是deque的迭代器的一个工作原理，大家简单了解一下。

那从这里呢其实我们还能得出：

deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历。

因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。

🆗，那我们这篇文章关于stack和queue的讲解就先到这里，欢迎大家指正！！！大家有什么问题也可以评论区或私信与我交流。