0


C++从入门到起飞之——stack&queue&deque 全方位剖析!

🌈个人主页:秋风起,再归来~****
🔥系列专栏:C++从入门到起飞****
🔖克心守己,律己则安

>前言****:栈和队列的使用非常简单,并且我们在数据结构部分已经运用的非常熟练了,下面我们就来直接剖析它们的底层结构!

1、容器适配器

1.1 什么是适配器

适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设 计经验的总结),该种模式是将一个类的接口转换成客户希望的另外一个接口。

1.2 STL标准库中stack和queue的底层结构

虽然stack和queue中也可以存放元素,但在STL中并没有将其划分在容器的行列,而是将其称为 容器适配器,这是因为stack和队列只是对其他容器的接口进行了包装,STL中stack和queue默认 使用deque,比如:

2、deque的简单介绍(了解)

2.1、deque的原理介绍

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

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

双端队列底层是一段假象的连续空间,实际是分段连续的,为了维护其“整体连续”以及随机访问 的假象,落在了deque的迭代器身上,因此deque的迭代器设计就比较复杂,如下图所示:

那deque是如何借助其迭代器维护其假想连续的结构呢?

2.2、deque的缺陷

>与vector比较,deque的优势是:头部插入和删除时,不需要搬移元素,效率特别高,而且在扩 容时,也不需要搬移大量的元素,因此其效率是比vector高的。

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

>但是,deque有一个致命缺陷:不适合遍历,因为在遍历时,deque的迭代器要频繁的去检测其 是否移动到某段小空间的边界,导致效率低下,而序列式场景中,可能需要经常遍历,因此在实 际中,需要线性结构时,大多数情况下优先考虑vector和list,deque的应用并不多,而目前能看 到的一个应用就是,STL用其作为stack和queue的底层数据结构。

我们下面做两个简单的测试就可以很清晰的感受到这个缺陷了!

  1. void test_op1()
  2. {
  3. srand(time(0));
  4. const int N = 1000000;
  5. deque<int> dq;
  6. vector<int> v;
  7. for (int i = 0; i < N; ++i)
  8. {
  9. auto e = rand() + i;
  10. v.push_back(e);
  11. dq.push_back(e);
  12. }
  13. int begin1 = clock();
  14. sort(v.begin(), v.end());
  15. int end1 = clock();
  16. int begin2 = clock();
  17. sort(dq.begin(), dq.end());
  18. int end2 = clock();
  19. printf("vector:%d\n", end1 - begin1);
  20. printf("deque:%d\n", end2 - begin2);
  21. }

无论是在测试还是发行版本下,在相同数据下使用相同的排序算法,我们可以看见vector的效率是明显高于deque的!

  1. void test_op2()
  2. {
  3. srand(time(0));
  4. const int N = 1000000;
  5. deque<int> dq1;
  6. deque<int> dq2;
  7. for (int i = 0; i < N; ++i)
  8. {
  9. auto e = rand() + i;
  10. dq1.push_back(e);
  11. dq2.push_back(e);
  12. }
  13. int begin1 = clock();
  14. sort(dq1.begin(), dq1.end());
  15. int end1 = clock();
  16. int begin2 = clock();
  17. // 拷贝到vector
  18. vector<int> v(dq2.begin(), dq2.end());
  19. sort(v.begin(), v.end());
  20. dq2.assign(v.begin(), v.end());
  21. int end2 = clock();
  22. printf("deque sort:%d\n", end1 - begin1);
  23. printf("deque copy vector sort, copy back deque:%d\n", end2 - begin2);
  24. }

这个测试的结果一方面说明了deque的遍历效率是很低的,另一方面也说明了拷贝的代价是很低的!

>为什么选择deque作为stack和queue的底层默认容器

stack是一种后进先出的特殊线性数据结构,因此只要具有push_back()和pop_back()操作的线性 结构,都可以作为stack的底层容器,比如vector和list都可以;

queue是先进先出的特殊线性数据 结构,只要具有push_back和pop_front操作的线性结构,都可以作为queue的底层容器,比如 list。

但是STL中对stack和queue默认选择deque作为其底层容器,主要是因为

1. stack和queue不需要遍历(因此stack和queue没有迭代器),只需要在固定的一端或者两端进 行操作。

2. 在stack中元素增长时,deque比vector的效率高(扩容时不需要搬移大量数据);queue中的 元素增长时,deque不仅效率高,而且内存使用率高。 结合了deque的优点,而完美的避开了其缺陷。

3、STL标准库中对于stack和queue的模拟实现

stack和queue的模拟实现就非常简单了,这里直接给源码给大家参考一下!

  1. //适配器container
  2. template<class T,class container=deque<T>>
  3. class stack
  4. {
  5. public:
  6. //元素数量
  7. size_t size() const
  8. {
  9. return con.size();
  10. }
  11. //判空
  12. bool empty()
  13. {
  14. return con.empty();
  15. }
  16. //入栈
  17. void push(const T& val)
  18. {
  19. con.push_back(val);
  20. }
  21. //出栈
  22. void pop()
  23. {
  24. con.pop_back();
  25. }
  26. //取栈顶元素
  27. T& top()
  28. {
  29. return con.back();
  30. }
  31. const T& top() const
  32. {
  33. return con.back();
  34. }
  35. private:
  36. container con;
  37. };
  1. template<class T, class Con = deque<T>>
  2. //template<class T, class Con = list<T>>
  3. class queue
  4. {
  5. public:
  6. void push(const T& x)
  7. {
  8. _c.push_back(x);
  9. }
  10. void pop()
  11. {
  12. _c.pop_front();
  13. }
  14. T& back()
  15. {
  16. return _c.back();
  17. }
  18. const T& back()const
  19. {
  20. return _c.back();
  21. }
  22. T& front()
  23. {
  24. return _c.front();
  25. }
  26. const T& front()const
  27. {
  28. return _c.front();
  29. }
  30. size_t size()const
  31. {
  32. return _c.size();
  33. }
  34. bool empty()const
  35. {
  36. return _c.empty();
  37. }
  38. private:
  39. Con _c;
  40. };

4、完结散花

好了,这期的分享到这里就结束了~**

如果这篇博客对你有帮助的话,可以用你们的小手指点一个免费的赞并收藏起来哟~

如果期待博主下期内容的话,可以点点关注,避免找不到我了呢~

我们下期不见不散~~

标签: c++ 开发语言 stl

本文转载自: https://blog.csdn.net/2301_80221228/article/details/141958921
版权归原作者 秋风起,再归来~ 所有, 如有侵权,请联系我们删除。

“C++从入门到起飞之——stack&queue&deque 全方位剖析!”的评论:

还没有评论