[C++随笔录] stack && queue模拟实现

简介: [C++随笔录] stack && queue模拟实现

stack的实现

🗨️stack的容器适配器应该选什么比较好呢?


首先, stack的特点是 头部入, 尾部出 ⇒ 尾插 和 尾删操作比较频繁

我们前面学过的容器有 vector 和 list,

vector 和 list的尾插 和 尾删的时间复杂度是 O(1), 还是适合做容器适配器的.

stack的基本结构

template<class T, class Continer = vector<T>> // 默认容器适配器是vector
class stack
{
private:
  Continer _con; // 维护这个容器对象就可以了
};

用这个容器对象来进行模拟实现stack


按照我们之前的想法, 容器适配器要么是 vector, 要么是 list.

这两者都是 自定义类型 ⇒ 自定义类型会调用它的默认构造 ⇒ 我们都不用写构造函数


  1. push
void push(const T& val)
{
  _con.push_back(val);
}
  1. pop
void pop()
{
  _con.pop_back();
}
  1. size
const T& top() const
{
  return _con.back();
}
  1. empty
bool empty() const
{
  return _con.size() == 0;
}
  1. top
const T& top() const
{
  return _con.back();
}

stack测试用例

void test_stack()
{
  muyu::stack<int> st;
  st.push(1);
  st.push(2);
  st.push(3);
  st.push(4);
  cout << "size->" << st.size() << endl;
  while (!st.empty())
  {
    cout << st.top() << " ";
    st.pop();
  }
  cout << endl;
  st.push(2);
  st.push(3);
  st.push(4);
  st.pop();
  st.pop();
  cout << "size->" << st.size() << endl;
  while (!st.empty())
  {
    cout << st.top() << " ";
    st.pop();
  }
  cout << endl;
}

queue的实现

🗨️queue的容器适配器能不能用 vector? 能不能使用list?


首先, queue的特点是 队尾入, 对头出 ⇒ 尾插, 头删操作比较频繁

其次, 我们来考量vector 和 list的尾插 和 头删效率如何?

vector的尾插是O(1), 头删是O(n )且 没有pop_front函数

list的尾插是O(1), 头删也是O(1) 且 有pop_front函数

⇒ 所以, 我们queue的容器适配器, list 比 vector更适合

queue的基本结构

  template<class T, class Continer = list<T>> // 默认容器适配器是list
  class queue
  {
  private:
    Continer _con; // 维护容器对象
  };
  1. push
void push(const T& val = T())
{
  _con.push_back(val);
}
  1. pop
void pop()
{
  _con.pop_front();
}
  1. front
const T& front() const
{
  return _con.front();
}
  1. back
const T& back() const
{
  return _con.back();
}
  1. empty
bool empty() const
{
  return _con.size() == 0;
}
  1. size
size_t size() const
{
  return _con.size();
}

queue测试用例

void test_queue()
{
  muyu::queue<int> q;
  q.push(1);
  q.push(2);
  q.push(3);
  q.push(4);
  q.push(5);
  cout << "front->" << q.front() << endl;
  cout << "back->" << q.back() << endl;
  cout << "size->" << q.size() << endl;
  cout << endl;
  q.pop();
  q.pop();
  cout << "front->" << q.front() << endl;
  cout << "back->" << q.back() << endl;
  cout << "size->" << q.size() << endl;
  cout << endl;
  while (!q.empty())
  {
    cout << q.front() << " ";
    q.pop();
  }
  cout << endl;
}

源码中, stack 和 queue的默认容器适配器给的是 deque.

我们来看一下deque的接口函数

我们惊奇的发现: deque不仅可以支持随机访问 [], 还支持 头插, 头删, 尾插, 尾删. 这不妥妥地是 vector 和 list 的结合体嘛.


🗨️那deque这么厉害, 我们之前为啥没有听过呢?


由于这个容器不值得我们去深度学习, 我这里就偷点懒, 盗用航哥的图了!



相关文章
|
19天前
|
C++ 容器
【c++丨STL】stack和queue的使用及模拟实现
本文介绍了STL中的两个重要容器适配器:栈(stack)和队列(queue)。容器适配器是在已有容器基础上添加新特性或功能的结构,如栈基于顺序表或链表限制操作实现。文章详细讲解了stack和queue的主要成员函数(empty、size、top/front/back、push/pop、swap),并提供了使用示例和模拟实现代码。通过这些内容,读者可以更好地理解这两种数据结构的工作原理及其实现方法。最后,作者鼓励读者点赞支持。 总结:本文深入浅出地讲解了STL中stack和queue的使用方法及其模拟实现,帮助读者掌握这两种容器适配器的特性和应用场景。
51 21
|
4月前
|
存储 算法 调度
【C++打怪之路Lv11】-- stack、queue和优先级队列
【C++打怪之路Lv11】-- stack、queue和优先级队列
60 1
|
4月前
|
设计模式 存储 C++
C++之stack 和 queue(下)
C++之stack 和 queue(下)
60 1
|
4月前
|
C++ 容器
C++之stack 和 queue(上)
C++之stack 和 queue(上)
100 0
|
4月前
|
存储 C++ 容器
C++番外篇——stack、queue的实现及deque的介绍
C++番外篇——stack、queue的实现及deque的介绍
41 0
|
1月前
|
C++ 芯片
【C++面向对象——类与对象】Computer类(头歌实践教学平台习题)【合集】
声明一个简单的Computer类,含有数据成员芯片(cpu)、内存(ram)、光驱(cdrom)等等,以及两个公有成员函数run、stop。只能在类的内部访问。这是一种数据隐藏的机制,用于保护类的数据不被外部随意修改。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。成员可以在派生类(继承该类的子类)中访问。成员,在类的外部不能直接访问。可以在类的外部直接访问。为了完成本关任务,你需要掌握。
68 19
|
1月前
|
存储 编译器 数据安全/隐私保护
【C++面向对象——类与对象】CPU类(头歌实践教学平台习题)【合集】
声明一个CPU类,包含等级(rank)、频率(frequency)、电压(voltage)等属性,以及两个公有成员函数run、stop。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。​ 相关知识 类的声明和使用。 类的声明和对象的声明。 构造函数和析构函数的执行。 一、类的声明和使用 1.类的声明基础 在C++中,类是创建对象的蓝图。类的声明定义了类的成员,包括数据成员(变量)和成员函数(方法)。一个简单的类声明示例如下: classMyClass{ public: int
50 13
|
1月前
|
编译器 数据安全/隐私保护 C++
【C++面向对象——继承与派生】派生类的应用(头歌实践教学平台习题)【合集】
本实验旨在学习类的继承关系、不同继承方式下的访问控制及利用虚基类解决二义性问题。主要内容包括: 1. **类的继承关系基础概念**:介绍继承的定义及声明派生类的语法。 2. **不同继承方式下对基类成员的访问控制**:详细说明`public`、`private`和`protected`继承方式对基类成员的访问权限影响。 3. **利用虚基类解决二义性问题**:解释多继承中可能出现的二义性及其解决方案——虚基类。 实验任务要求从`people`类派生出`student`、`teacher`、`graduate`和`TA`类,添加特定属性并测试这些类的功能。最终通过创建教师和助教实例,验证代码
48 5
|
1月前
|
存储 算法 搜索推荐
【C++面向对象——群体类和群体数据的组织】实现含排序功能的数组类(头歌实践教学平台习题)【合集】
1. **相关排序和查找算法的原理**:介绍直接插入排序、直接选择排序、冒泡排序和顺序查找的基本原理及其实现代码。 2. **C++ 类与成员函数的定义**:讲解如何定义`Array`类,包括类的声明和实现,以及成员函数的定义与调用。 3. **数组作为类的成员变量的处理**:探讨内存管理和正确访问数组元素的方法,确保在类中正确使用动态分配的数组。 4. **函数参数传递与返回值处理**:解释排序和查找函数的参数传递方式及返回值处理,确保函数功能正确实现。 通过掌握这些知识,可以顺利地将排序和查找算法封装到`Array`类中,并进行测试验证。编程要求是在右侧编辑器补充代码以实现三种排序算法
38 5
|
1月前
|
Serverless 编译器 C++
【C++面向对象——类的多态性与虚函数】计算图像面积(头歌实践教学平台习题)【合集】
本任务要求设计一个矩形类、圆形类和图形基类,计算并输出相应图形面积。相关知识点包括纯虚函数和抽象类的使用。 **目录:** - 任务描述 - 相关知识 - 纯虚函数 - 特点 - 使用场景 - 作用 - 注意事项 - 相关概念对比 - 抽象类的使用 - 定义与概念 - 使用场景 - 编程要求 - 测试说明 - 通关代码 - 测试结果 **任务概述:** 1. **图形基类(Shape)**:包含纯虚函数 `void PrintArea()`。 2. **矩形类(Rectangle)**:继承 Shape 类,重写 `Print
47 4