从C语言到C++_19(容器适配器+stack和queue模拟实现+优先级队列priority_queue)(上)

简介: 从C语言到C++_19(容器适配器+stack和queue模拟实现+优先级队列priority_queue)

1. 容器适配器

1.1 什么是适配器

想了解这里的 "适配器",我们先去看看电源适配器:

【百度百科】电源适配器又叫外置电源,是小型便携式电子设备及电子电器的供电电压变换设备,常见于手机、液晶显示器和笔记本电脑等小型电子产品上。

电源适配器是进行 "转换" 的,它本质上可以理解为是一个变压器

标准家庭用电电压为220V,我们设备用电其实并不需要这么高,

而电源适配器可以使较高的交流电压降低到合适于手机电池的直流工作电压。

也就是说,电源适配器是用来 "转换" 的。

再看看容器适配器:

一种用来修饰容器,仿函数或者迭代器的接口的东西。

配接器修改类的接口,使原来不相互匹配的两个类可以相互匹配,进行合作。

1.2 STL标准库中stackqueue的底层结构

前一篇我们提到:虽然stackqueue中也可以存放元素,

但在STL中并没有将其划分在容器的行列,而是将其称为容器适配

这是因为stack和队列只是对其他容器的接口进行了包装,

STLstackqueue默认使用deque,比如:

deque(双端队列,后面讲)(可以手动换成其它的)

2. stack和queue的模拟实现

2.1 stack模拟实现

我们以前已经用C语言写过了一个数组栈:

数据结构与算法⑧(第三章_上)栈的概念和实现(力扣:20. 有效的括号)_GR C的博客-CSDN博客

数组栈和链式栈

实现栈无非就两种结构:数组结构 和 链式结构,两种结构都可以实现。


数组栈和链式栈哪种结构更好?


相对而言数组的结构实现更优,尾插尾删的效率高,缓存利用率高,它的唯一缺点只是增容,


但是增容1次扩2倍对栈来说本身就比较合理,是无伤大雅的。而链式栈虽然不会空间浪费,


用一个 malloc 申请一个,但是链式栈存在一个致命的缺点:单链表不好出数据,


必须要实现双向链表,否则尾上删除数据将会异常麻烦。


如果硬要使用链式栈:


① 如果用尾做栈顶,尾插尾删,要设计成双向链表,否则删数据效率低。


② 如果用头做栈顶,头插头删,就可以设计成单链表。

在C++我们就可以直接用vector实现数组栈了,体会一下C++的方便,直接放stack.h了:

#pragma once
#include <iostream>
#include <vector>
using namespace std;
 
namespace rtx
{
  template<class 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.pop_back();
    }
    bool empty() const
    {
      return _con.empty();
    }
    size_t size() const
    {
      return _con.size();
    }
  private:
    vector<T> _con;
  };
}

测试Test.c:

#include "Stack.h"
 
void test_stack()
{
    rtx::stack<int> st;
    st.push(1);
    st.push(2);
    st.push(3);
    st.push(4);
    st.push(5);
 
    cout << "st.size() = " << st.size() << endl;
    while (!st.empty())
    {
        cout << st.top() << " "; // 后进先出
        st.pop();
    }
    cout << endl;
}
 
int main()
{
    test_stack();
 
    return 0;
}

我们这里复用了vector,这是不是适配器呢?

这里并不是,因为底层已经写死了,它就是数组栈,如果我想要一个链式栈呢?

模板的方便又来了:

#pragma once
#include <iostream>
#include <vector>
using namespace std;
 
namespace rtx
{
  template<class T, class Container>
  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.pop_back();
    }
    bool empty() const
    {
      return _con.empty();
    }
    size_t size() const
    {
      return _con.size();
    }
  private:
    //vector<T> _con;
    Container _con;
  };
}
#include "Stack.h"
 
void test_stack()
{
    rtx::stack<int, vector<int>> st;
    st.push(1);
    st.push(2);
    st.push(3);
    st.push(4);
    st.push(5);
 
    cout << "st.size() = " << st.size() << endl;
    while (!st.empty())
    {
        cout << st.top() << " "; // 后进先出
        st.pop();
    }
    cout << endl;
}
 
int main()
{
    test_stack();
 
    return 0;
}

如果我们要链式栈:把显示传的vector换成list(包一下头文件):

前面说到,STL里面stack和queue的默认适配器是deque

把其它头文件移到Test.c ,Stack.h的最终就是这样的:

#pragma once
 
#include <deque>
 
namespace rtx
{
  template<class T, class Container = 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.pop_back();
    }
    bool empty() const
    {
      return _con.empty();
    }
    size_t size() const
    {
      return _con.size();
    }
  private:
    Container _con;
  };
}

2.2 queue的模拟实现

deque等下讲,这里先放queue的模拟实现,经过前面的学习,直接放了:

Queue.h:

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

Test.c:

#include <iostream>
#include <vector>
#include <list>
#include <string>
using namespace std;
 
#include "Stack.h"
#include "Queue.h"
 
void test_stack()
{
    rtx::stack<int> st;
    st.push(1);
    st.push(2);
    st.push(3);
    st.push(4);
    st.push(5);
 
    cout << "st.size() = " << st.size() << endl;
    while (!st.empty())
    {
        cout << st.top() << " "; // 后进先出
        st.pop();
    }
    cout << endl;
}
void test_queue()
{
    rtx::queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);
    q.push(5);
 
    cout << "q.size() = " << q.size() << endl;
    while (!q.empty())
    {
        cout << q.front() << " "; // 先进先出
        q.pop();
    }
    cout << endl;
}
int main()
{
    test_stack();
    test_queue();
 
    return 0;
}

值得注意的是这里的queue不能显示地传vector,因为vector没有头删。

从C语言到C++_19(容器适配器+stack和queue模拟实现+优先级队列priority_queue)(中):https://developer.aliyun.com/article/1521888?spm=a2c6h.13148508.setting.25.712b4f0eDngT44


目录
相关文章
|
3月前
|
存储 设计模式 C++
【C++】优先级队列(容器适配器)
本文介绍了C++ STL中的线性容器及其适配器,包括栈、队列和优先队列的设计与实现。详细解析了`deque`的特点和存储结构,以及如何利用`deque`实现栈、队列和优先队列。通过自定义命名空间和类模板,展示了如何模拟实现这些容器适配器,重点讲解了优先队列的内部机制,如堆的构建与维护方法。
58 0
|
4月前
|
设计模式 存储 C++
【C++】C++ STL探索:容器适配器 Stack 与 Queue 的使用及模拟实现(二)
【C++】C++ STL探索:容器适配器 Stack 与 Queue 的使用及模拟实现
|
4月前
|
存储 C++ 容器
【C++】C++ STL探索:容器适配器 Stack 与 Queue 的使用及模拟实现(一)
【C++】C++ STL探索:容器适配器 Stack 与 Queue 的使用及模拟实现
|
7月前
|
存储 算法 Java
【C++】优先级队列priority_queue模拟实现&&仿函数
【C++】优先级队列priority_queue模拟实现&&仿函数
52 1
|
7月前
|
存储 算法 C语言
【C++】详解STL的适配器容器之一:优先级队列 priority_queue
【C++】详解STL的适配器容器之一:优先级队列 priority_queue
|
1月前
|
存储 算法 C语言
【C语言程序设计——函数】素数判定(头歌实践教学平台习题)【合集】
本内容介绍了编写一个判断素数的子函数的任务,涵盖循环控制与跳转语句、算术运算符(%)、以及素数的概念。任务要求在主函数中输入整数并输出是否为素数的信息。相关知识包括 `for` 和 `while` 循环、`break` 和 `continue` 语句、取余运算符 `%` 的使用及素数定义、分布规律和应用场景。编程要求根据提示补充代码,测试说明提供了输入输出示例,最后给出通关代码和测试结果。 任务核心:编写判断素数的子函数并在主函数中调用,涉及循环结构和条件判断。
58 23
|
1月前
|
算法 C语言
【C语言程序设计——函数】利用函数求解最大公约数和最小公倍数(头歌实践教学平台习题)【合集】
本文档介绍了如何编写两个子函数,分别求任意两个整数的最大公约数和最小公倍数。内容涵盖循环控制与跳转语句的使用、最大公约数的求法(包括辗转相除法和更相减损术),以及基于最大公约数求最小公倍数的方法。通过示例代码和测试说明,帮助读者理解和实现相关算法。最终提供了完整的通关代码及测试结果,确保编程任务的成功完成。
62 15
|
1月前
|
C语言
【C语言程序设计——函数】亲密数判定(头歌实践教学平台习题)【合集】
本文介绍了通过编程实现打印3000以内的全部亲密数的任务。主要内容包括: 1. **任务描述**:实现函数打印3000以内的全部亲密数。 2. **相关知识**: - 循环控制和跳转语句(for、while循环,break、continue语句)的使用。 - 亲密数的概念及历史背景。 - 判断亲密数的方法:计算数A的因子和存于B,再计算B的因子和存于sum,最后比较sum与A是否相等。 3. **编程要求**:根据提示在指定区域内补充代码。 4. **测试说明**:平台对代码进行测试,预期输出如220和284是一组亲密数。 5. **通关代码**:提供了完整的C语言代码实现
59 24
|
1月前
|
存储 C语言
【C语言程序设计——函数】递归求斐波那契数列的前n项(头歌实践教学平台习题)【合集】
本关任务是编写递归函数求斐波那契数列的前n项。主要内容包括: 1. **递归的概念**:递归是一种函数直接或间接调用自身的编程技巧,通过“俄罗斯套娃”的方式解决问题。 2. **边界条件的确定**:边界条件是递归停止的条件,确保递归不会无限进行。例如,计算阶乘时,当n为0或1时返回1。 3. **循环控制与跳转语句**:介绍`for`、`while`循环及`break`、`continue`语句的使用方法。 编程要求是在右侧编辑器Begin--End之间补充代码,测试输入分别为3和5,预期输出为斐波那契数列的前几项。通关代码已给出,需确保正确实现递归逻辑并处理好边界条件,以避免栈溢出或结果
63 16
|
30天前
|
存储 编译器 C语言
【C语言程序设计——函数】分数数列求和2(头歌实践教学平台习题)【合集】
函数首部:按照 C 语言语法,函数的定义首部表明这是一个自定义函数,函数名为fun,它接收一个整型参数n,用于指定要求阶乘的那个数,并且函数的返回值类型为float(在实际中如果阶乘结果数值较大,用float可能会有精度损失,也可以考虑使用double等更合适的数据类型,这里以float为例)。例如:// 函数体代码将放在这里函数体内部变量定义:在函数体中,首先需要定义一些变量来辅助完成阶乘的计算。比如需要定义一个变量(通常为float或double类型,这里假设用float。
35 3

热门文章

最新文章