【C++】了解设计模式、 stack&queue的使用与模拟实现(下)

简介: 【C++】了解设计模式、 stack&queue的使用与模拟实现(下)

2.queue的模拟实现

1.queue的结构

和stack的结构非常相似,代码框架如下:

namespace zht//这里把实现的queue包在命名空间中
{
  template<class T, class Container = std::deque<T>>
  class queue
  {
  public:
    //成员函数
  private:
    Container _con;
  };
}


2.接口实现

queue的接口实现方式和queue也是非常的类似,唯一需要改的就是push和pop数据的位置

//构造函数:我们不显示写,编译器生成。直接调用_con的默认构造
bool empty() const
{
    return _con.empty();
}
size_t size() const
{
    return _con.size();
}
const T& top() 
{
    return _con.back();//适配这类操作的容器都是支持back或者front接口的,直接调用即可
}
void push(const T& val)//这里的push我们采用尾插的方式插入
{
    _con.push_back(val);
}
void pop()//由于push使用的是尾插,所以pop采用头删的方式
{
    _con.pop_back();
}


至此,我们就算是能够手撕stack和queue了哈哈。


4.了解deque


我们注意到,stack和queue的容器都是deque。这是为什么呢?在学习数据结构的时候,实现的stack和queue一般是使用顺序表和链表实现的。为什么这里不使用vector和list呢?

vector和list的结构都存在一些缺陷:vector真正的缺点在于扩容消耗,不支持头插头删,因为头部中部删除效率低。而list不支持随机访问,且CPU高速缓存命中率低,空间不连续。而deque兼具了vector和list的优点,虽然deque也有很多缺点,但是作为适配器的容器恰好避免了这些。


对于deque,我们稍微了解一下即可,因为deque合适的使用场景很少。


1.deque的原理介绍

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

be195aa4aeaf53c32489a88c8d264f02.png

这只是逻辑图,deque在底层并不是真的连续空间


2.deque的底层结构

deque的底层是由很多段连续的小空间拼接而成类似一个二维数组,然后这些小空间的地址存放在一个中控指针数组中。结构示意图如下:

9c1ffc947c3a6362dd3d8ed281378cb8.png

3.deque的迭代器设计

那么deque是如何使用迭代器来维护这个假想的连续结构的呢?

这里参考一下侯捷老师的STL源码剖析中的图:

04e80704ae8aa49fa61f86d091123a45.png

deque的迭代器包含四个指针,其中cur指向当前值,first和last指向当前cur所在的小段连续空间,node指向中控数组中存放所在连续空间的地址。


4.deque的优缺点分析

优点:头部插入和删除时,不需要搬移元素,效率特别高,扩容时,也不需要搬移大量的元素,因此其效率是比vector高的。与list比较,其底层是连续空间,空间利用率比较高,不需要存储额外字段。


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


5.为什么选择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不仅效率高,而且内存使用率高。
  3. 结合了deque的优点,而完美的避开了其缺陷


和queue默认选择deque作为其底层容器,主要是因为:


  1. stack和queue不需要遍历(因此stack和queue没有迭代器),只需要在固定的一端或者两端进行操作。
  2. 在stack中元素增长时,deque比vector的效率高(扩容时不需要搬移大量数据);queue中的元素增长时,deque不仅效率高,而且内存使用率高。
  3. 结合了deque的优点,而完美的避开了其缺陷
相关文章
|
27天前
|
设计模式 C++ 容器
c++中的Stack与Queue
c++中的Stack与Queue
|
2月前
|
C++ 容器
【c++丨STL】stack和queue的使用及模拟实现
本文介绍了STL中的两个重要容器适配器:栈(stack)和队列(queue)。容器适配器是在已有容器基础上添加新特性或功能的结构,如栈基于顺序表或链表限制操作实现。文章详细讲解了stack和queue的主要成员函数(empty、size、top/front/back、push/pop、swap),并提供了使用示例和模拟实现代码。通过这些内容,读者可以更好地理解这两种数据结构的工作原理及其实现方法。最后,作者鼓励读者点赞支持。 总结:本文深入浅出地讲解了STL中stack和queue的使用方法及其模拟实现,帮助读者掌握这两种容器适配器的特性和应用场景。
68 21
|
5月前
|
存储 算法 调度
【C++打怪之路Lv11】-- stack、queue和优先级队列
【C++打怪之路Lv11】-- stack、queue和优先级队列
70 1
|
5月前
|
设计模式 存储 C++
C++之stack 和 queue(下)
C++之stack 和 queue(下)
80 1
|
5月前
|
C++ 容器
C++之stack 和 queue(上)
C++之stack 和 queue(上)
119 0
|
5月前
|
存储 C++ 容器
C++番外篇——stack、queue的实现及deque的介绍
C++番外篇——stack、queue的实现及deque的介绍
44 0
|
5月前
|
存储 算法 C++
C++入门10——stack与queue的使用
C++入门10——stack与queue的使用
69 0
|
24天前
|
编译器 C++ 开发者
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。
|
2天前
|
设计模式 安全 C++
【C++进阶】特殊类设计 && 单例模式
通过对特殊类设计和单例模式的深入探讨,我们可以更好地设计和实现复杂的C++程序。特殊类设计提高了代码的安全性和可维护性,而单例模式则确保类的唯一实例性和全局访问性。理解并掌握这些高级设计技巧,对于提升C++编程水平至关重要。
31 16
|
6天前
|
安全 C++
【c++】继承(继承的定义格式、赋值兼容转换、多继承、派生类默认成员函数规则、继承与友元、继承与静态成员)
本文深入探讨了C++中的继承机制,作为面向对象编程(OOP)的核心特性之一。继承通过允许派生类扩展基类的属性和方法,极大促进了代码复用,增强了代码的可维护性和可扩展性。文章详细介绍了继承的基本概念、定义格式、继承方式(public、protected、private)、赋值兼容转换、作用域问题、默认成员函数规则、继承与友元、静态成员、多继承及菱形继承问题,并对比了继承与组合的优缺点。最后总结指出,虽然继承提高了代码灵活性和复用率,但也带来了耦合度高的问题,建议在“has-a”和“is-a”关系同时存在时优先使用组合。
45 6