【C++】STL之适配器---用deque实现栈和队列

目录

前言

一、deque

 1、deque 的原理介绍

 2、deque 的底层结构

 3、deque 的迭代器

 4、deque 的优缺点

  4.1、优点

  4.2、缺点

二、stack 的介绍和使用

 1、stack 的介绍

 2、stack 的使用

 3、stack 的模拟实现

三、queue 的介绍和使用

 1、queue 的介绍 

 2、queue 的使用

 3、queue 的模拟实现

前言

  容器适配器，按字面意思理解的话，就是用来对一个容器进行匹配的。在C++STL中，容器有：vector，list，deque，map，set等。而在C++STL中不把stack和queue纳入容器的范围而是纳入容器适配器的范围是因为：

  stack和queue没有下标随机访问等操作，只有普通的pop_front,push_back,pop_back()等操作，而这些函数在其他容器中完全可以有，栈和队列的实现完全可以将其他容器的操作进行复用，这就是stack和queue作为容器适配器的原因。

  适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总 结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。

一、deque

 1、deque 的原理介绍

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

 2、deque 的底层结构

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

 3、deque 的迭代器

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

 4、deque 的优缺点

  4.1、优点

• 具有 vector 的优点 ---支持随机访问、缓存命中率较高、尾部插入删除数据效率高；
• 同时具有 list 的优点 --- 空间浪费少、头部插入插入数据效率高；

    4.2、缺点

  • deque 的随机访问效率较低 --- 需要先通过中控数据找到对应的buffer数组，再找到具体的位置 (假设偏移量为 i，需先 i/10 得到位于第几个buffer数组，再 i%10 得到 buffer 数组中的具体位置)，即 deque 随机访问时一次跳过一个buffer数组，需要跳多次才能准确定位，其效率比 list 高了不少，但比 vector 也低了不少；
  • deque 在中部插入删除数据的效率是比较低的 --- 需要挪动数据，但不一定后续 buffe 数组中的数据全部挪动，可以控制只挪一部分，即中间插入删除数据的效率高于 vector，但是低于 list。

     所以综上分析， deque 结合了 vector 和 list 的优缺点，看似很完美，但是它单方面的性能是不如 vector 或者 list 的，因此 deque 在实际应用中使用的非常少。

    STL 中选择 deque 作为 stack 和 queue 默认适配容器的原因：

    • stack 和 queue 不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
    • 在 stack 中元素增长时，deque 比 vector 的效率高(扩容时不需要搬移大量数据)；queue 中的元素增长时，deque不仅效率高，而且内存使用率高。

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

        deque 特别适合需要大量进行头插和尾部数据的插入删除、偶尔随机访问、偶尔中部插入删除的场景；不太适合需要大量进行随机访问与中部数据插入删除的场景，特别是排序。

      二、stack 的介绍和使用

       1、stack 的介绍

      1. stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。
      2. stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定 的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。
      3. stack 的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：empty：判空操作 back：获取尾部元素操作 push_back：尾部插入元素操作 pop_back：尾部删除元素操作；
      4. 标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器， 默认情况下使用deque。

      

       2、stack 的使用

      函数说明	接口说明
      stack()	构造空的栈
      empty()	检测 stack 是否为空
      size()	返回 stack 中元素的个数
      top()	返回栈顶元素的引用
      push()	将元素 val 压入 stack 中
      pop()	将 stack 中尾部的元素弹出

      下面是栈的使用操作： 

      int main()
      {
      	//构造空栈
      	stack s;
      	//元素入栈
      	s.push(1);
      	s.push(2);
      	//获取栈中元素个数
      	int Size = s.size();
      	cout