第四章：适配器、双端队列、栈和队列(逻辑梳理，底层实现)

本文主要是介绍第四章：适配器、双端队列、栈和队列(逻辑梳理，底层实现)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、什么是适配器？

容器适配器（Container Adaptor）是一种设计模式，用于将一个容器的接口适配成另一个容器的接口。
在C++标准模板库（STL）中，容器适配器是一种预定义的容器，它们提供了对某些底层容器的封装，并对其接口进行了适配。
比如，stack和queue的底层实现就是用了适配器而非容器，这样stack的函数实现就可以直接封装其他容器的函数，不用再从头开始实现底层代码。

二、双端队列deque(了解原理即可，无需深究，主要还是使用vector和list)：

2.1什么是双端队列？

双端队列deque是C++标准模板库（STL）中的一种序列容器。它提供了动态数组的功能，并且支持在两端（即前端和后端）进行高效的插入和删除操作。
deque相当于vector和list的缝合版，我们知道vector和list都在特定的方面有较强的能力，比如vector的随机访问，list的双端操作。而deque既可以随机访问又可以双端操作。但是他在这两方面又都不是很突出。属于都行也都不怎么行。

2.2deque的底层实现：

将数据分成多个固定大小的块（blocks），然后通过一个指针数组(中控数组)来管理这些数组。
数据块(数组)（Blocks）：数据存储在多个固定大小的块中，每个块的大小通常是32或64个元素。这些块中的元素在内存中是连续的，但不同块之间不需要连续。
指针数组(中控数组)（Map）：指针数组中的每个指针指向一个数据块的起始位置。指针数组本身也是动态可扩展的，可以根据需要增加或减少。
deque维护两个指针，一个指向第一个有效元素的位置，另一个指向最后一个有效元素的下一个位置。

2.3deque头插实现的原理：

首先检查当前的第一个数据块的前端是否有可用空间。如果有可用空间，则直接插入新元素。
如果没有可用空间，则需要分配一个新的数据块，并将其添加到指针数组的前端。
更新指针数组以包含新的数据块。
头插一个数据到新开辟的块中，这个数据是被插入到块的末尾。比如一个块a有4个可用空间，头插会先插入a[3]而不是a[0]位置。

2.4deque尾插实现原理：

基本和头插一样，但是开辟一个新的块，尾插一个元素进去，首先被插入的地方是块的头部不是尾部。

2.5deque中间插入，实现原理：

通过指针数组快速定位到包含待插入位置的数据块。因为每一个块都是等大的，所以“位置/块大小=所在的块”。
找到目标块所要插入的位置，位置%块大小=块中位置。
根据插入位置，将元素插入到该数据块的合适位置。
如果插入后导致当前数据块容量不足，需要进行数据块的分裂或合并操作。就是挪动数据，将部分元素挪动到新创建的块。
根据需要更新指针数组和数据块的指针。

2.6中控数组(指针数组)是否需要扩容，如何扩容？

通常情况下，指针数组会被设置成一个足够大的值以容纳大部分情况下的数据块数量。
如果需要扩容时，先分配一个更大的内存空间。
将原有的指针数组中的指针复制到新的内存空间中。
释放原有的指针数组内存空间。
更新指针数组的指针指向新的内存空间。

三、stack和queue：

3.1stack和queue在库中是如何实现的？

stack和queue在库中被认为是容器适配器（container adapter），而不是容器（container）。他们并不是独立的数据结构，而是将已有的容器封装起来，以实现特定的行为。
在C++标准库中，stack通常是基于deque实现的，也可以选择基于vector实现。
在C++标准库中，queue通常也是基于deque实现的，同样也可以基于vector实现。

3.2stack和queue的接口：

stack和queue的接口比较少。
stack的接口如下：

queue的接口如下：

3.3stack的模拟实现：

namespace demo1
{template<class T, class Container>//Container表示适配器，库中实现为缺省+dequeclass stack{public://注意将成员函数设置为公有bool empty(){return _con.empty();}size_t size(){return _con.size();}const T& top(){return _con.back();}void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}private:Container _con;};
}

3.4queue的模拟实现：

#pragma oncenamespace demo2
{template<class T,class Container>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;};
}

这篇关于第四章：适配器、双端队列、栈和队列(逻辑梳理，底层实现)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！