当前位置:首页 » 《资源分享》 » 正文

【C++】—— stack & queue & deque

9 人参与  2024年09月23日 14:40  分类 : 《资源分享》  评论

点击全文阅读


【C++】—— stack & queue & deque

1 stack 与 queue 的函数接口2 适配器2.1 发现问题2.2 什么是适配器 3 stack 与 queue的模拟实现3.1 栈的基础框架3.2 栈的模拟实现3.3 队列的模拟实现 4 模板的按需实例化5 deque 的简单介绍5.1 vector 与list对比5.1.1 vector5.1.2 list 5.2 deque 的基本结构5.3 deque 的迭代器5.4 operator[] 的简单原理5.5 选择deque作为其底层容器原因

1 stack 与 queue 的函数接口

  stackqueue 的使用非常简单,相信大家看一眼他们的函数接口就会了,这里就不再过多介绍

函数说明接口说明
s t a c k stack stack()构造空的栈
e m p t y empty empty()检测 s t a c k stack stack 是否为空
s i z e size size()返回 s t a c k stack stack 中元素的个数
t o p top top()返回栈顶元素的引用
p u s h push push()将元素 v a l val val 压入 s t a c k stack stack 中
p o p pop pop()将 s t a c k stack stack 中尾部的元素弹出
stack 函数接口
函数声明接口说明
q u e u e queue queue()构造空的队列
e m p t y empty empty()检测队列是否为空,是返回 t r u e true true,否则返回 f a l s e false false
s i z e size size()返回队列中有效元素的个数
f r o n t front front()返回队列头元素的引用
b a c k back back()返回队列尾元素的引用
p u s h push push()在队尾元素 v a l val val 入队列
p o p pop pop()将队头元素出队列
queue 函数接口

  
  

2 适配器

2.1 发现问题

  我们看stackqueue的文档,会发现有这样的介绍:

在这里插入图片描述

在这里插入图片描述

  文档说stack是一种容器适配器,那么适配器又是什么呢?以及它的模板参数为什么是两个,不是传一个类型就可以了吗? d e q u e deque deque又是什么鬼
  别急,我们现在就来学习,我们先来了解什么是适配器
  

2.2 什么是适配器

  适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结),该种模式是将一个类的接口转换成客户希望的另一个接口
  适配器其实就是适配器模式。设计模式总共有 23 种,设计模式就好比孙子兵法中的战术,是前人不断总结实践出来的经验方法。迭代器的设计某种程度上来说就是一种设计模式,为迭代器模式。

  

在这里插入图片描述

  例如充电:现在插座是三孔的,两孔的插头想要充上电,可以用一个电源适配器进行转换

  适配的本质是一种转换接口

  虽然stackqueue中也可以存放元素,但在 STL 中并没有将其划分在容器的行列,而是将其称为容器适配器,这是因为栈和队列只是对其他容器的接口进行了包装
  
  

3 stack 与 queue的模拟实现

3.1 栈的基础框架

  根据我们前面学习STL库中的其他容器的经验
  我们模拟实现栈,其基本结构可以是这样的

namespace my_stack{template<class T>struct stack{public://成员函数···private:T* _a;size_t _top;size_t _capacity;};}

  现在,我们学习了适配器模式,可以不用上述方式去实现。
  我们尝试使用适配器的方式去实现

  我们想,可不可以像库中的一样用其他的容器进行封装转换一下,从而实现一个栈呢?
  可以的,因为栈主要支持两个东西:在栈顶插入 p u s h push push 和在栈顶删除 p o p pop pop。那理论上只要那个容器支持在同一端插入和删除就能够支持栈。那 vectorlist 都支持,这样我们的栈就不需要我们自己去实现,直接封装一下 v e c t o r vector vector 或 l i s t list list 不就行了。
  
如下:

template<class T>class stack{public://成员函数private:vector<T> _v;};

  但这样写,无疑就写死了,于是有人发明了如下写法:

template<class T, class Container = vector<T>>class stack{public://成员函数private:Container _con;};

  这里,用 C o n t a i n e r Container Container 适配转换出 s t a c k stack stack

  那 C o n t a i n e r Container Container 是什么类型呢?默认是 v e c t o r vector vector,如果传 l i s t list list 就是 l i s t list list,传其他容器就是其他容器

  
  

3.2 栈的模拟实现

  那接下来实现一个就很容易啦,只需复用 Container 中的成员函数即可

namespace my_stack{// Containerתstacktemplate<class T, class Container = vector<T>>class stack{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}const T& top() const{//return _con.func();return _con.back();}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};}

  
  

3.3 队列的模拟实现

  学习了 s t a c k stack stack 的模拟实现,队列的模拟实现就很简单啦,他们都是类似的。
  需要注意的是队列是先进后出,即一端进另一端出,就不再适合用 v e c t o r vector vector,这里我们的默认容器改为 l i s t list list

namespace my_list{template<class T, class Container = list<T>>class queue{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_front();}const T& front() const{return _con.front();}const T& back() const{return _con.back();}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};}

  
  

4 模板的按需实例化

  我们使用自己实现的队列,使用 v e c t o r vector vector 作为容器有没有问题呢?

int main(){my_list::queue<int, vector<int>> q1;q1.push(1);q1.push(2);q1.push(3);return 0;}

在这里插入图片描述

  可以看到,是没问题的。
  可是不应该啊,因为模板中我们实现的pop()函数调用了容器的pop_front()函数,而 vector 容器是没有 pop_front() 函数的,这不应该报错吗?
  
  这里要讲一个新的知识点:按需实例化
  类模板实例化时,编译器只会实例化那些显式调用了的函数,使用哪些成员函数就实例化哪些,不会全部实例化
  
  my_list::queue<int, vector<int>> q1; 这一句代码是把类模板实例化了。但是将这个类模板实例化了,编译器会将这个类所有的成员函数都实例化吗?不会,编译器实例化这个类时,它的原则是:用什么成员函数实例化哪些成员函数。

  而编译器对模板只会检查大框架(比如:漏了一个 ‘;’),而不会检查具体的实现细节。编译器只会对实例化了的东西进行细致的检查

  上述代码,编译器只实例化了 p u s h push push 和 构造函数,剩下的函数都没实例化。而 p o p pop pop 函数并没有被实例化。没有实例化,没有生成具体的函数,里面的语法自然就不会细节地去检查

int main(){my_list::queue<int, vector<int>> q1;q1.push(1);q1.push(2);q1.push(3);q1.pop();return 0;}

在这里插入图片描述

  调用了 p o p pop pop 函数才会报错。

  所以模板没有全部使用之前,并不能保证里面的语法没有问题
  
  

5 deque 的简单介绍

  不知大家发现没有,库中 stackqueue 的默认容器并不是 v e c t o r vector vector 或 l i s t list list,而是 deque

在这里插入图片描述

在这里插入图片描述

  那么 d e q u e deque deque 是什么呢?我们一起来简单了解一下。
  

5.1 vector 与list对比

  我们先来简单对比一下 v e c t o r vector vector 与 l i s t list list 的优缺点

5.1.1 vector

优点:

尾插尾删效率不错,支持高效下标随机访问物理空间连续,所以高速缓存利用率高

缺点:

空间需要扩容,扩容有一些代价(效率和空间浪费)头部和中部插入删除效率低

  

5.1.2 list

优点:

按需申请释放空间,不需要扩容任意位置插入删除效率高

缺点:

不支持下标随机访问物理空间不连续,高速缓存利用率

  
  

5.2 deque 的基本结构

  deque 的中文名是:双端队列,虽然名字和 q u e u e queue queue 有点像,但它和 q u e u e queue queue 没有任何关系
   d e q u e deque deque 可以看成是 v e c t o r vector vector 和 l i s t list list 的缝合

   d e q u e deque deque 是由一段一段小数组(这里取名为 b u f f buff buff 数组)和一个中控数组组成。
  中控数组是一个指针数组放着每一个 buff 数组的指针。而 b u f f buff buff 数组则存放数据。第一个 b u f f buff buff 的数组会放在中控数组的中间

在这里插入图片描述

  
  如果进行头插,则在中控数组最前面增加一个数组指针,并在 b u f f buff buff 数组从后往前插入数据;如果尾插,则在中控数组最后面增加数组指针,并在 b u f f buff buff 数组中从前往后插入数据。
  如果空间不够需进行扩容,只需扩容中控数组拷贝中控数组的指针,并新开辟一个 buff 即可
  

在这里插入图片描述

  
  

5.3 deque 的迭代器

   d e q u e deque deque 的迭代器由四个指针组成

cur:指向当前访问 b u f f buff buff 的数据first:指向一个 b u f f buff buff 的开始last:指向一个 b u f f buff buff 的结束node:为二级指针,反向指向中控数组

在这里插入图片描述

  
  那么 d e q u e deque deque 的迭代器是如何管理整个结构的呢?
  我们结合图来简单了解一下

在这里插入图片描述

   d e q u e deque deque 中主要的成员变量由两个迭代器组成:startfinish。 s t a r t start start 即 b e g i n begin begin() 返回的迭代器; f i n i s h finish finish 即 e n d end end() 返回的迭代器。
  
  当用迭代器遍历整个 d e q u e deque deque:

iterator it = begin();while(it != end()){cout << *it << " ";++it;}
while(it != end()),!= 其实比较的是迭代器中的 c u r cur cur 是否相等cout << *it << " "; *it,其本质是解引用 c u r cur cur++it;分为两种情况 当前的 b u f f buff buff 没有走完(判断条件 c u r cur cur != l a s t last last):++cur当前 b u f f buff buff 走完(判断条件 c u r cur cur == l a s t last last):通过 n o d e node node 找到当前 buff 地址在中控数组的位置,++ n o d e node node 找到下一个 b u f f buff buff 的地址,解引用就是下一个 b u f f buff buff。更新 f i r s t first first 与 l a s t last last, c u r cur cur 指向第一个位置。

  
  

5.4 operator[] 的简单原理

  这里讲一下 o p e r a t o r operator operator[] 的实现,即查找第 i 个数据

因为第一个 b u f f buff buff 前面的空的,所以先对第一个buff特殊处理,先判断是否在第一个 b u f f buff buff 中。之后假设第一个buff是满的。比如第一个 b u f f buff buff 只有后面三个位有数据,则假设补满;找第 i i i 个数据,改为找第 i i i + 5 个后通过 i / N 找到第 n n n 个 b u f f buff buff,再通过 i % N 找到其在第 n n n 个 b u f f buff buff 的第 m m m 个位置。( N N N 为每个 b u f f buff buff 的长度)

  
  这里我们演示一下 d e q u e deque deque 的 o p e r a t o r operator operator[] 效率:

void test1(){srand(time(0));const int N = 1000000;deque<int> dq;vector<int> v;for (int i = 0; i < N; ++i){auto e = rand() + i;v.push_back(e);dq.push_back(e);}int begin1 = clock();sort(v.begin(), v.end());int end1 = clock();int begin2 = clock();sort(dq.begin(), dq.end());int end2 = clock();printf(" vector:%d\n", end1 - begin1);printf(" deque:%d\n", end2 - begin2);}

在这里插入图片描述

  相差两倍左右

void test1(){srand(time(0));const int N = 1000000;deque<int> dq1;deque<int> dq2;for (int i = 0; i < N; ++i){auto e = rand() + i;dq1.push_back(e);dq2.push_back(e);}int begin1 = clock();sort(dq1.begin(), dq1.end());int end1 = clock();int begin2 = clock();// 拷贝到vectorvector<int> v(dq2.begin(), dq2.end());sort(v.begin(), v.end());dq2.assign(v.begin(), v.end());int end2 = clock();printf(" deque sort:%d\n", end1 - begin1);printf(" deque copy vector sort, copy back deque:%d\n", end2 - begin2);}

在这里插入图片描述

  依然是 v e c t o r vector vector 快,同时也可以看成拷贝的代价是很低的

  
  

5.5 选择deque作为其底层容器原因

d e q u e deque deque的优缺点:

d e q u e deque deque 的头插尾插效率很高,更甚于 v e c t o r vector vector 和 l i s t list list下标随机访问也还不错,但相比 v e c t o r vector vector 略逊一筹但中间插入效率很低,需要挪动数据,是 O( n n n)deque 在实践中应用并不多,主要是用于 s t a c k stack stack 和 q u e u e queue queue 的底层结构

s t a c k stack stack 和 q u e u e queue queue 不需要遍历(因此 s t a c k stack stack 和 q u e u e queue queue 没有迭代器),只需要在固定的一端或者两端进行操作,完美符合 d e q u e deque deque 头插尾插效率高的优点。

在 s t a c k stack stack 中元素增长时, d e q u e deque deque 比 v e c t o r vector vector 的效率高(扩容时不需要搬移大量数据); q u e u e queue queue 中的元素增长时, d e q u e deque deque不仅效率高,而且内存使用率高(不需要频繁开辟细碎的空间)。 结合了 d e q u e deque deque 的优点,而完美的避开了其缺陷。

  
  
  
  
  


  好啦,本期关于 s t a c k stack stack & q u e u e queue queue & d e q u e deque deque 的知识就介绍到这里啦,希望本期博客能对你有所帮助。同时,如果有错误的地方请多多指正,让我们在 C++ 的学习路上一起进步!


点击全文阅读


本文链接:http://zhangshiyu.com/post/163472.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1