一、stack接口

栈是一种容器适配器，专门设计用于在后进先出的上下文中操作，元素仅从容器的末尾插入和提取。

1. 构造函数

//容器适配器，内存池对象我们不用自己传，一般直接使用默认的就可以，需要的话就自己传
initialize(1)explicit stack (const container_type& ctnr);
move-initialize(2)explicit stack (container_type&& ctnr = container_type());
allocator(3)template <class Alloc> explicit stack (const Alloc& alloc);
init + allocator(4)template <class Alloc> stack (const container_type& ctnr, const Alloc& alloc);
move-init + allocator(5)template <class Alloc> stack (container_type&& ctnr, const Alloc& alloc);
copy + allocator(6)template <class Alloc> stack (const stack& x, const Alloc& alloc);
move + allocator(7)template <class Alloc> stack (stack&& x, const Alloc& alloc);

2. empty

//判空，size为0，返回true,否则，返回false
bool empty() const;

3. size

//返回stack中元素的个数
size_type size() const;

4. top

//返回的是栈顶元素的引用
reference top();
const_reference top() const;

5. push

//在栈顶上插入元素
void push (const value_type& val);
void push (value_type&& val);

6. pop

//删除栈顶元素
void pop();

7. swap

//交换两个stack对象的内容
void swap (stack& x) noexcept

8. 友元函数

//比较两个stack对象的大小，按照从栈底到栈顶的元素顺序进行比
//较，那个容器的元素大，整个栈就大
//本质是依赖底层容器完成的
(1)template <class T, class Container>
bool operator== (const stack<T,Container>& lhs, const stack<T,Container>& rhs);
(2)template <class T, class Container>
bool operator!= (const stack<T,Container>& lhs, const stack<T,Container>& rhs);
(3)template <class T, class Container>
bool operator<  (const stack<T,Container>& lhs, const stack<T,Container>& rhs);
(4)template <class T, class Container>
bool operator<= (const stack<T,Container>& lhs, const stack<T,Container>& rhs);
(5)template <class T, class Container>
bool operator>  (const stack<T,Container>& lhs, const stack<T,Container>& rhs);
(6)template <class T, class Container>
bool operator>= (const stack<T,Container>& lhs, const stack<T,Container>& rhs);

二、queue的接口

queue也是一个容器适配器，专门设计用来先进先出的上下文操作中，元素的插入在队尾，提取在队头。

1. 构造

//queue的构造和statck的构造一样，参数一般不需要传，需要的话，自己传
initialize(1) explicit queue (const container_type& ctnr);
move-initialize(2) explicit queue (container_type&& ctnr = container_type());
allocator(3) template <class Alloc> explicit queue (const Alloc& alloc);
init + allocator(4)	template <class Alloc> queue (const container_type& ctnr, const Alloc& alloc);
move-init + allocator(5) template <class Alloc> queue (container_type&& ctnr, const Alloc& alloc);
copy + allocator(6)	template <class Alloc> queue (const queue& x, const Alloc& alloc);
move + allocator(7)	template <class Alloc> queue (queue&& x, const Alloc& alloc);

2. empty

//判空
bool empty() const;

3. size

//返回的是queue中元素的个数
size_type size() const;

4. front

//返回的是队头元素的引用
reference& front();
const_reference& front() const;

5. back

//返回的是队尾元素的引用
reference& back();
const_reference& back() const;

6. push

//在队尾插入一个新的元素
void push (const value_type& val);
void push (value_type&& val);

7. pop

//删除的是队头的元素
void pop();

8. swap

//交换的是两个queue对象的内容
void swap (queue& x) noexcept

9. 友元函数

//比较的是两个queue对象的大小
(1)template <class T, class Container>
bool operator== (const queue<T,Container>& lhs, const queue<T,Container>& rhs);
(2)template <class T, class Container>
bool operator!= (const queue<T,Container>& lhs, const queue<T,Container>& rhs);
(3)template <class T, class Container>
bool operator<  (const queue<T,Container>& lhs, const queue<T,Container>& rhs);
(4)template <class T, class Container>
bool operator<= (const queue<T,Container>& lhs, const queue<T,Container>& rhs);
(5)template <class T, class Container>
bool operator>  (const queue<T,Container>& lhs, const queue<T,Container>& rhs);
(6)template <class T, class Container>
bool operator>= (const queue<T,Container>& lhs, const queue<T,Container>& rhs);

三、容器适配器deque

1. deque的认识

deque是一个双端队列，允许在队列的前端(front)和后端(back)，都能进行插入和删除操作的数据结构。

这里我们不再进行接口的认识，deque显示使用的场景比较少，一般作为底层的容器适配器，间接使用的场景比较高。因此，我们需要了解deque的结构与实现的大致思路。

那么，看到这里，相信大家对于什么是容器适配器已经有了大致的了解了吧。

所谓容器适配器本身也是一个容器，但它是为了作为另一个容器的底层结构。

例如，我们前面已经实现了vector，那么在stack这里，还需要从头在实现底层结构吗？答案是不需要了。因为stack的底层可以选用数组呀（选择数组比较好），而vector的底层也是数组，所以，我们也可以直接使用vector作为stack的底层结构。这就是容器适配器，为容器选择合适的一个底层结构。

但是，vector也是有缺点的。因为vector的底层是数组，所以它的优点是可以支持随机访问，访问效率高。

但是在插入和删除操作方面就要逊色很多了，因为需要挪动数据，时间复杂度为O(N)，效率很低，其次，还可能存在空间浪费，因为扩容是按照倍数扩容的，不一定需要这么多的空间。

而队列的底层结构可以选用链表，因为队列插入元素在队尾，不论是选用数组还是链表都可以，但是在删除队头元素时，链表就更占优，因为链表直接可以删除，而数组还需要挪动数据，所以选用链表更合适。

然而，任何事物都有自己的优缺点。链表的优点是插入删除效率很高，时间复杂度为O(1)，可以按需获取空间，缺点是不支持随机访问。

所以，能不能有一种数据结构既可以有数组的优点也可以有链表的优点，于是就有了deque（双端队列的出现）。

这就好比现实中，有人要通过嫁接得到一个新的品种一样。

2. deque的设计原理

vector需要申请一段连续的空间，而list一次申请1个空间。deque集合了两种方式，它也是一次性申请一段连续的空间，当插入数据满了之后，它不是在原基础上进行扩容，而是重新开辟一段新的空间，插入数据。那么，这样的空间会有很多个，访问数据的时候怎么才能找到对应的空间位置呢？

deque中有一个中控数组map，它的类型是T**，本质是一个指针数组，我们把它叫做中控数组。当第一次申请空间时，插入数据，迭代器start中的first指针就会指向这段空间的起始地址，last指针指向这段空间的末尾，并将这段空间的起始地址填入map（中控数组）中间的位置，这段空间插入数据满了之后，就会在开辟一段新的空间，将新开辟的空间的起始地址填入中控数组中间的下一个位置。而deque中另一个迭代器finish中的first指针指向中控数组最后一个空间的起始地址，last指针指向最后一段空间的末尾。

用一张图简单理解一下。

其实，迭代器当中不仅有first，last指针，还有cur，node指针，cur指针指向一段空间中的第一个有效元素的位置，node指针的类型是T，回指向map数组中正在访问某段空间的位置。

不过需要注意的是，迭代器start的cur指针指向第一段空间的第一个有效元素的位置，而迭代器finish中的cur指针指向最后一段空间的最后一个有效元素的下一个位置。

如果要尾插，那么最后一段空间有空余位置，就可以直接插入数据并更新finish.cur指针，没有空余位置的话，就可以申请一段新的空间，再插入数据，同时更新迭代器finish（内部成员变量全部更新），将新申请的空间的起始地址填入map数组中finish指向的下一个位置。

同理尾删，只需要更改cur指针往前走一步，如果尾删之后，这段空间无效了，那就要释放这段空间，并让迭代器- -finish。

如果要头插，和尾插是很相似的，头插如果第一段空间有空余位置，直接插入即可，并更新start.cur指针，如果没有就申请新空间，将空间的起始地址填入到map数组里start指向的前一个位置，不过这里要注意的是，此时头插应该让数据插入到新申请空间的末尾位置，因为要保持数据的连贯性，访问下一个数据，中间不能为随机值，应该访问到了具体的数据。

头删也是一样的，更改start.cur指针就可以了，或者更改迭代器start。

在插入数据的时候，有可能会申请很多的新空间，这些空间的起始地址都要填写到map数组里，所以，map数组也是会满的，因此也需要扩容，不过这里扩容的代价就会小很多，这里扩容之后，只需要拷贝原map数组中的指针到新空间里就可以了。

那么,deque是否有缺陷呢？答案是有的。

与vector比较，deque的优势是：头部插入删除时，不需要移动元素，效率特别高。

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

但是，deque有两个非常致命的缺陷：

1.不适合遍历，因为在遍历时，deque的迭代器需要频繁的去检测其是否移动到某段小空间的边界，导致效率低下。

2.不适合中间数据的插入和删除，因为，如果空间满了的话，插入数据要么需要移动数据，要么需要对这一段小的空间进行扩容，反之，空间没满，也需要移动数据，而无论是哪一种情况，都是不可取的。移动数据时间复杂度就是O(N)，而扩容的话又会导致每一段空间的大小是不一样的，所以也不可取。

一般访问deque中的某个数据，还是挺方便的，因为每段空间的大小是固定的，那么假如访问空间中的第100位数据，只需要进行 /=，%=运算即可确定位置，相比于vector稍逊一筹，不过也还好。但是一旦选择了扩容，那么就麻烦了。

所以，deque也是有缺陷的。那么，为什么选择deque作为stack和queue的底层默认容器呢？

虽然deque有缺陷，在遍历方面，中间元素的插入和删除方面有着非常大的缺点，但是其它方面还是很高效的，而stack和queue只需要在两端进行操作，没有中间位置的困扰，deque刚好完美避免了这个问题，所以选择deque作为stack和queue的底层默认容器。

deque在局部上有着致命的缺点，但是在这种场景下就是非常完美的。

转载自CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/2402_84532723/article/details/151192647