【C++】适配器模式 - - stack/queue/deque

目录

一、适配器模式

1.1迭代器模式

1.2适配器模式

二、stack

2.1stack 的介绍和使用

2.2stack的模拟实现

三、queue

3.1queue的介绍和使用

3.2queue的模拟实现

 四、deque（不满足先进先出，和队列无关）

4.1deque的原理介绍

4.2deque的特点（支持头删，支持随机访问）

4.3deque的底层结构（buffer+中控指针数组）

五、总结

答案一： 

答案二：

答案三：

---

一、适配器模式

1.1迭代器模式

其实我们在前面学习 string、vector 和 list 时就已经接触过设计模式了 – 迭代器就是一种设计模式；迭代器模式是封装后提供统一的接口 iterator，在不暴露底层实现细节的情况下，使得上层能够以相同的方式来访问不同的容器。

1.2适配器模式

适配器模式则是：

用已有的东西封装转换出想要的东西

---

二、stack

2.1stack 的介绍和使用

 和我们以前学的容器不同，为了不破坏栈 LIFO 的特性，stack 不提供迭代器，所以 stack 不是迭代器模式，而是一种容器适配器

如图，stack 使用 dqueue 容器作为默认的适配容器（后面讲一个吕布和诸葛亮的参照），关于 dqueue 的内容，我们放在文章最后面讲。

stack的常用接口：

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

2.2stack的模拟实现

在了解了适配器模式之后，我们就可以将适配器作为类的第二个模板参数，然后通过传递不同的适配容器来实现栈了：

 

如上，vector 和 list 都可以作为 stack 的适配容器，我们可以通过给定不同的第二个模板参数来使用不同的容器适配 stack；

但是出于随机抽取和缓存命中的考虑，vector 显然更适合作为 stack 的适配容器，那么我们可以还可以将 vector 设置为 stack 的默认适配容器，这样，我们以后定义栈对象时就不用显式指定 vector 了

stack.h 文件

#include <iostream>
#include <vector>
#include <list>namespace lzy {template<class T, class Container = std::vector<T>>class stack {public://构造和析构不用写，默认生成的构造和析构对于自定义类型会调用它们的构造和析构函数bool empty() const {return _Con.empty();}size_t size() const {return _Con.size();}T& top() {return _Con.back();  //数组尾部作为栈的栈顶}const T& top() const {return _Con.back();}void push(const T& val) {_Con.push_back(val);  //在数组尾部插入数据}void pop() {_Con.pop_back();}private:Container _Con;};
}

 测试代码：

void test_stack() {//stack<int, std::vector<int>> st1;//stack<int, std::list<int>> st2;//stack<int> st1;  //默认使用vector做适配容器//stack<int, std::list<int>> st2;  //使用其他容器做适配容器需要显式指定stack<int> st;st.push(1);st.push(2);st.push(3);st.push(4);st.push(5);cout << st.size() << endl;while (!st.empty()) {cout << st.top() << " ";st.pop();}cout << endl;
}

---

三、queue

3.1queue的介绍和使用

 和 stack 一样，queue 也是一种容器适配器，也不提供迭代器

可以看到，queue 也是使用 deque 作为默认适配容器，和之前一样，deque 我们放在最后面讲。

queue 常用接口的使用

函数声明	接口说明
queue()	构造空的队列
empty()	检测队列是否为空
size()	返回队列中有效元素的个数
front()	返回队头元素的引用
back()	返回队尾元素的引用
push()	在队尾将元素val入队列
pop()	将队头元素出队列

3.2queue的模拟实现

 

这里queue与stack不同的是，stack俩个均可，但是vector更好；但是队列这里头删用vector是效率很低的办法，所以队列只可以用list

queue.h

#pragma once#include <iostream>
#include <vector>
#include <list>namespace lzy {template<class T, class Container = std::list<T>>class queue {public://构造和析构不用写，默认生成的构造和析构对于自定义类型会调用它们的构造和析构函数bool empty() const {return _Con.empty();}size_t size() const {return _Con.size();}T& front() {return _Con.front();  //第一个节点为队头}const T& front() const {return _Con.front();}T& back() {return _Con.back();  //最后一个节点为队尾}const T& back() const {return _Con.back();  //最后一个节点为队尾}void push(const T& val) {_Con.push_back(val);  //在链表尾部插入节点}void pop() {_Con.pop_front();  //删除第一个节点}private:Container _Con;};
}

测试代码：

void test_queue() {queue<int> q; //默认使用list做适配容器q.push(1);q.push(2);q.push(3);q.push(4);q.push(5);cout << q.size() << endl;while (!q.empty()) {cout << q.front() << " ";q.pop();}cout << endl;
}

 

---

 四、deque（不满足先进先出，和队列无关）

4.1deque的原理介绍

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

4.2deque的特点（支持头删，支持随机访问）

我们的stack用vector是为了缓存命中，而且因为先进后出的特性用链表不合适

我们的queue用list是因为list的头删效率更高

但是deque横空出世，具有随机访问和头插头删效率不错的特点（只不过每一个特点都没有发挥到极致）

不过不可否认的是 deque 确实很适合作为 stack 和 list 的默认适配容器，毕竟它对于 stack 和 list 的通用的，这也是 STL 中选择 deque 作为 stack 和 queue 默认适配容器的原因。

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

总结：他没有vector访问数据那么极致，也没有list插入数据那么牛逼，但是他俩个特点都有，作为俩个容器的适配器也是非常合适的！

4.3deque的底层结构（buffer+中控指针数组）

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

关于扩容：只有当中空指针数组满了，才会扩容

关于尾插：后面新开一个buffer

关于头插：前面新开一个buffer

关于随机访问：1.查询哪一个buffer2.查询在哪一个buffer的哪一个位置

五、总结

答案一： 

答案二：

答案三：

希望对大家有所帮助！