C++学习笔记(十九)——stack和queue的模拟实现

简介: C++学习笔记(十九)——stack和queue的模拟实现

容器适配器


适配器:一种设计模式,该种模式是将一个类的接口转换成客户希望的另外一个接口.

stack和queue的底层结构

image.png

可以看出的是,这两个容器 相比我们之间见过的容器多了一个模板参数,也就是容器类的模板参数,他们在STL中并没有将其划分在容器的行列,而是将其称为容器适配器,它们的底层是其他容器,对其他容器的接口进行了包装,它们默认的是使用deque

deque的简单介绍


image.png

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

deque底层结构

它并不是一段连续的空间,而是由多个连续的小空间拼接而成,相当于一个动态的二维数组.

如下图:

image.png

deque的迭代器

迭代器原理:迭代器用cur成员进行访问,每当走到last的位置,node的位置就往前挪动一个位置,然后cur继续从first我位置遍历到last的位置,一直如此,cur走到最后一个node的last的位置就停止遍历.

image.png

deque的优点

1.相比于vector,deque可以进行头插和头删,且时间复杂度O(1),扩容是也不需要大量挪动数据,因此效率是比vector高的.

2.相比于list,deque底层是连续的空间,空间利用率高,也支持随机访问,但没有vector那么高.

3.总的来说,deque是一种同时具有vector和list两个容器的优点的容器,有一种替代二者的作用,但不是完全替代.

deque的缺点

1.不适合遍历,因为在遍历是,deque的迭代器要频繁地去检测是否运动到其某段小空间的边界,所以导致效率低下.

2.deque的随机访问的效率是比vector低很多的,实际中,线性结构大多数先考虑vector和list.

下面是通过排序来测试vector和deque随机访问的效率

void TestDeque()
{
  srand((unsigned int)time(nullptr));
  deque<int> d;
  vector<int> v;
  for (size_t i = 0; i < 100000; ++i)
  {
    int randNum = rand();
    v.push_back(randNum);
    d.push_back(randNum);
  }
  int begin1 = clock();
  sort(v.begin(), v.end());
  int end1 = clock();
  int begin2 = clock();
  sort(d.begin(), d.end());
  int end2 = clock();
  cout << "vector排序用时:" << end1 - begin1 << "ms" << endl;
  cout << "deque排序用时:" << end2 - begin2 << "ms" << endl;
}

代码运行结果如下:

image.png

容易看出,deque的随机访问的效率是比vector低很多的。

deque可以作为stack和queue底层默认容器的原因:

  • stack和queue并不需要随机访问,也就是说没有触及到deque的缺点,只是对头和尾进行操作。
  • 在stack增容时,deque的效率比vector高,queue增容时,deque效率不仅高,而且内存使用率也高。

stack的模拟实现


知道了容器适配器后,stack的模拟实现就显得相当简单,我们只需要调用所指定容器的各个成员函数即可实现stack的各个函数接口。

成员函数 函数作用 实现方法
push 元素入栈 调用所指定容器的push_back
pop 元素出栈 调用所指定容器的pop_back
top 获取栈顶元素 调用所指定容器的back
size 获取栈中有效元素个数 调用所指定容器的size
empty 判断栈是否为空 调用所指定容器的empty
swap 交换两个栈中的数据 调用所指定容器的swap
namespace cl //防止命名冲突
{
  template<class T, class Container = std::deque<T>>
  class stack
  {
  public:
    //元素入栈
    void push(const T& x)
    {
      _con.push_back(x);
    }
    //元素出栈
    void pop()
    {
      _con.pop_back();
    }
    //获取栈顶元素
    T& top()
    {
      return _con.back();
    }
    const T& top() const
    {
      return _con.back();
    }
    //获取栈中有效元素个数
    size_t size() const
    {
      return _con.size();
    }
    //判断栈是否为空
    bool empty() const
    {
      return _con.empty();
    }
    //交换两个栈中的数据
    void swap(stack<T, Container>& st)
    {
      _con.swap(st._con);
    }
  private:
    Container _con;
  };
}

queue的模拟实现


同样的方式,我们也是通过调用所指定容器的各个成员函数来实现queue的。

成员函数 函数作用 实现方法
push 队尾入队列 调用所指定容器的push_back
pop 队头出队列 调用所指定容器的pop_front
front 获取队头元素 调用所指定容器的front
back 获取队尾元素 调用所指定容器的back
size 获取队列中有效元素个数 调用所指定容器的size
empty 判断队列是否为空 调用所指定容器的empty
swap 交换两个队列中的数据 调用所指定容器的swap
namespace cl //防止命名冲突
{
  template<class T, class Container = std::deque<T>>
  class queue
  {
  public:
    //队尾入队列
    void push(const T& x)
    {
      _con.push_back(x);
    }
    //队头出队列
    void pop()
    {
      _con.pop_front();
    }
    //获取队头元素
    T& front()
    {
      return _con.front();
    }
    const T& front() const
    {
      return _con.front();
    }
    //获取队尾元素
    T& back()
    {
      return _con.back();
    }
    const T& back() const
    {
      return _con.back();
    }
    //获取队列中有效元素个数
    size_t size() const
    {
      return _con.size();
    }
    //判断队列是否为空
    bool empty() const
    {
      return _con.empty();
    }
    //交换两个队列中的数据
    void swap(queue<T, Container>& q)
    {
      _con.swap(q._con);
    }
  private:
    Container _con;
  };
}
目录
打赏
0
0
0
0
15
分享
相关文章
|
6月前
|
【c++丨STL】stack和queue的使用及模拟实现
本文介绍了STL中的两个重要容器适配器:栈(stack)和队列(queue)。容器适配器是在已有容器基础上添加新特性或功能的结构,如栈基于顺序表或链表限制操作实现。文章详细讲解了stack和queue的主要成员函数(empty、size、top/front/back、push/pop、swap),并提供了使用示例和模拟实现代码。通过这些内容,读者可以更好地理解这两种数据结构的工作原理及其实现方法。最后,作者鼓励读者点赞支持。 总结:本文深入浅出地讲解了STL中stack和queue的使用方法及其模拟实现,帮助读者掌握这两种容器适配器的特性和应用场景。
132 21
【C++打怪之路Lv11】-- stack、queue和优先级队列
【C++打怪之路Lv11】-- stack、queue和优先级队列
114 1
C++之stack 和 queue(下)
C++之stack 和 queue(下)
110 1
|
9月前
|
C++之stack 和 queue(上)
C++之stack 和 queue(上)
190 0
C++番外篇——stack、queue的实现及deque的介绍
C++番外篇——stack、queue的实现及deque的介绍
71 0
C++入门10——stack与queue的使用
C++入门10——stack与queue的使用
101 0
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。
c++模板初阶----函数模板与类模板
class 类模板名private://类内成员声明class Apublic:A(T val):a(val){}private:T a;return 0;运行结果:注意:类模板中的成员函数若是放在类外定义时,需要加模板参数列表。return 0;
43 0
c++的类(附含explicit关键字,友元,内部类)
本文介绍了C++中类的核心概念与用法,涵盖封装、继承、多态三大特性。重点讲解了类的定义(`class`与`struct`)、访问限定符(`private`、`public`、`protected`)、类的作用域及成员函数的声明与定义分离。同时深入探讨了类的大小计算、`this`指针、默认成员函数(构造函数、析构函数、拷贝构造、赋值重载)以及运算符重载等内容。 文章还详细分析了`explicit`关键字的作用、静态成员(变量与函数)、友元(友元函数与友元类)的概念及其使用场景,并简要介绍了内部类的特性。
110 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问