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

摘要：本文介绍了如何使用C++ STL中的适配器以及deque来实现栈和队列。适配器是一种STL组件，它允许我们以一种特定的方式使用容器，而不改变容器的底层数据结构。通过使用deque作为底层容器，我们可以轻松地实现栈和队列操作，如push、pop、front等。这种方法不仅提高了代码的可读性和可维护性，而且充分利用了STL的灵活性和效率。

目录

deque

1、deque 的原理介绍

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

2、deque的底层结构

* deque的底层结构由一段段连续的小空间拼接而成，类似于一个动态的二维数组。

3、deque的迭代器

* 为了维护deque的“整体连续”及随机访问的假象，落在了deque的迭代器身上，deque的迭代器设计较为复杂。

4、deque的优缺点

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

缺点deque的随机访问效率较低，需要先通过中控数据找到对应的buffer数组，再找到具体的位置，deque在中部插入删除数据的效率也比较低，需要挪动数据。

stack的介绍和使用

1、stack的介绍

* stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作，stack的底层容器可以是任何标准的容器类模板或特定的容器类，这些容器类应支持判空操作、获取尾部元素操作、尾部插入元素操作、尾部删除元素操作，默认情况下，如果没有为stack指定特定的底层容器，则使用deque。

2、stack的使用

stack的主要函数包括构造空的栈、检测stack是否为空、返回stack中元素的个数、返回栈顶元素的引用、将元素压入stack中、将stack中尾部的元素弹出，下面是栈的使用操作示例（使用C++语言）。

希望这次整理的内容更加清晰和易于理解。