【C++第十课 - stack_queue】stack、queue的使用、适配器模型stack、queue和priority_queue的底层实现、deque

目录

  • 一、stack使用
    • 1、push
    • 2、pop
    • 3、empty
    • 4、top
    • 题目
      • 1、最小栈
      • 2、栈的压入、弹出序
      • 3、逆波兰表达式求值
  • 二、queue的使用
    • priority_queue
    • 习题
  • 三、适配器
    • stack的底层实现
    • queue的底层实现
    • priority_queue的底层实现
    • 仿函数/函数对象
    • 函数指针
  • 四、deque

一、stack使用

stack是个容器适配器
stack想要访问里面所有的数据必须pop和top，不能使用范围for

1、push

插入向量
在这里插入图片描述

	stack<int> s;
	s.push(1);
	s.push(2);
	s.push(3);
	s.push(4);

2、pop

移除栈顶数据
在这里插入图片描述

3、empty

stack为空返回true
stack非空返回false

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

4、top

取栈顶元素

题目

1、最小栈

https://leetcode.cn/problems/min-stack/
在这里插入图片描述
双栈解决
方案一
设计两个stack，一个stack存放数值，另一个stack存放最小值

存了这么多5有点浪费空间
改进方案二

在这里插入图片描述
方案二

当_stpop的与_minst栈顶元素一样的时候，_minst也pop
存在的问题：当有好多个最小值是_minst要push进去多个，->改进：方案三

在这里插入图片描述

class MinStack {
public:
    MinStack() { 
    }
    
    void push(int val) {
        _st.push(val);
        if(_minst.empty() || val <= _minst.top())
        {
            _minst.push(val);
        }
    }
    
    void pop() {
        if(_st.top() == _minst.top())
        {
            _minst.pop();
        }
        _st.pop();
    }
    
    int top() {
        return _st.top();
    }
    
    int getMin() {
        return _minst.top();
    }
private:
    stack<int> _st;
    stack<int> _minst;
};

方案三
在这里插入图片描述

2、栈的压入、弹出序

用栈来模拟入栈和出栈过程

（1）如果pushV当前入栈的值和popV当前出栈的值一样，pushV向后移一位，popV向后移一位
（2）如果pushV当前入栈的值和popV当前出栈的值不一样，分两种情况
第一种情况：如果栈顶元素与popV当前出栈元素一样，popv向后移一位，栈顶元素弹出
第二种情况：如果栈为空或栈顶元素与popV当前的出栈元素不一样，将pushV当前入栈元素压入栈中，pushV向后移一位

之后开始对栈中元素按照popV的顺序进行出栈，如果对不上就是False

简化：先入栈，再判断

1、入栈序列当前数据入栈
2、栈顶元素与出栈序列进行比较
（1）相等，出栈，出栈序列++
（2）不相等
2的结束标志，栈为空或不相等
所有的结束标志：入栈序列走完

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pushV int整型vector 
     * @param popV int整型vector 
     * @return bool布尔型
     */
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        // write code here
        stack<int> s;
        size_t pushi = 0;
        size_t popi = 0;
        while(pushi < pushV.size())
        {
            s.push(pushV[pushi]);
            while(!s.empty() && s.top() == popV[popi])
            {
                s.pop();
                ++popi;
            }
            ++pushi;
        }
        return popi == popV.size();
    }
};

3、逆波兰表达式求值

逆波兰表达式求值

前缀表达式（波兰）
所有的符号都是在要运算的操作数字的前面出现。例如 /++abcde
中缀表达式
所有的符号都是在要运算的操作数字的中间出现。例如（a+b+cd）/e
后缀表达式（逆波兰）
所有的符号都是在要运算的操作数字的后面出现。例如 abcd*++e/

在这里插入图片描述

二、queue的使用

在这里插入图片描述

容器container默认是deque(双端队列)

在这里插入图片描述

priority_queue

不是先进先出，是按优先级出
底层是：堆
是适配器，不是容器了
compare是比较的函数

在这里插入图片描述
在这里插入图片描述

习题

在这里插入图片描述
方法一

在这里插入图片描述

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> q;
        queue<int> qlayer;
        vector<vector<int>> vv;
        int layer = 1;
        if(root)
        {
            q.push(root);
            qlayer.push(layer);
        }
        while(!q.empty())
        {
            vector<int> v;
            while(qlayer.front() == layer )
            {
                TreeNode* cur = q.front();
                q.pop();
                v.push_back((*cur).val);
                if(cur->left)
                {
                  q.push(cur->left);
                  qlayer.push(layer + 1);
                }
                if(cur->right)
                {
                    q.push(cur->right);
                    qlayer.push(layer + 1);
                }
                qlayer.pop();
            }
            vv.push_back(v);
            ++layer;
        }
        return vv;
    }
};

方法二

三、适配器

适配器就是一个设计模式
由容器（string、vector、list、deque）封装、转换而成的，底层数据的管理不是由自己负责的
默认容器：
stack -> deque
queue -> deque
priority_queue -> vector

stack的底层实现

站和队列的底层实现都是复用的容器(string、vector、list)

在这里插入图片描述

	template<class T, class Container = deque<T>>
	class stack
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}
		void pop()
		{
			_con.pop_back();
		}
		const T& top()
		{
			return _con.back();
		}
		size_t size()
		{
			return _con.size();
		}
		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;
	};

在这里插入代码片

queue的底层实现

在这里插入图片描述

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

priority_queue的底层实现

在这里插入图片描述
是优先级队列，优先级高的先出，因此用堆进行实现

	template<class T, class Container = vector<T>>
	class priority_queue
	{
	public:
		void adjust_up()
		{
			int child = _con.size() - 1;
			int parent = (child - 1) / 2;

			while (parent >= 0)
			{
				if (_con[child] > _con[parent])
				{
					swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}

		}
		void push(const T& x)
		{
			_con.push_back(x);
			adjust_up();
		}
		void adjust_down()
		{
			int parent = 0;
			int left = parent * 2 + 1; 
			int right = parent * 2 + 2;
			int size = _con.size();
			while (left < size)
			{
				int big = left;
				if (right < size && _con[right] > _con[left])
				{
					big = right;
				}
				if (_con[big] > _con[parent])
				{
					swap(_con[big], _con[parent]);
					parent = left;
					left = parent * 2 + 1;
					right = parent * 2 + 2;
				}
				else
				{
					break;
				}
			}
		}
		//优先出优先级高的
		void pop()
		{
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			adjust_down();
		}
		const T& top()
		{
			return _con[0];
		}
		size_t size()
		{
			return _con.size();
		}
		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;
	};

priority_queue里面用的仿函数–第三个模板参数

仿函数/函数对象

为了解决函数指针的缺陷
回调函数：这个函数已经写好了，在用到它的时候再去调它（C语言用这个）
Compare可以定义成成员对象，也可以在用的时候创建一个Compare com;
模板参数：传的是类型，编译的时候传递

namespace zyh
{
	template<class T>
	class less
	{
	public:
		bool operator()(T x, T y)
		{
			return x < y;
		}
	};
	template<class T>
	class greater
	{
	public:
		bool operator()(T x, T y)
		{
			return x > y;
		}
	};


	template<class T, class Container = vector<T>, class Compare = greater<T>>
	class priority_queue
	{
	public:
		void adjust_up()
		{
			int child = _con.size() - 1;
			int parent = (child - 1) / 2;

			while (parent >= 0)
			{
				if (_com(_con[child], _con[parent]))
				{
					swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}

		}
		void push(const T& x)
		{
			_con.push_back(x);
			adjust_up();
		}
		void adjust_down()
		{
			int parent = 0;
			int left = parent * 2 + 1; 
			int right = parent * 2 + 2;
			int size = _con.size();
			while (left < size)
			{
				int big = left;
				if (right < size && _com(_con[right], _con[left]))
				{
					big = right;
				}
				if (_com(_con[big], _con[parent]))
				{
					swap(_con[big], _con[parent]);
					parent = left;
					left = parent * 2 + 1;
					right = parent * 2 + 2;
				}
				else
				{
					break;
				}
			}
		}
		//优先出优先级高的
		void pop()
		{
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			adjust_down();
		}
		const T& top()
		{
			return _con[0];
		}
		size_t size()
		{
			return _con.size();
		}
		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;
		Compare _com;
	};
}

在这里插入图片描述
模板参数不仅能在类里面传递还能在函数里面传递
在这里插入图片描述

上面是类模板，只能穿仿函数。如果传函数指针，类里面也是将它转换成类型还是拿不到函数指针
下面是函数模板，可以传仿函数对象、函数指针。能传函数指针是因为，可以根据函数指针推出类型，同时参数那也可以得到函数指针。

函数指针

传递的是对象是参数变量，运行时传递的

在这里插入图片描述

四、deque

双端队列，但不是队列。就像优先级队列也不是队列

拥有list和vector的所有功能，尾插尾删、头插头删、[ ]
[ ]的效率没有vector的高

vector
优点：物理结构连续存储的优势
（1）下标随机访问
（2）缓存命中高
缺点：
（1）前面插入删除效率低
（2）扩容有消耗
list
优点：
（1）扩容没有消耗
（2）随机插入删除效率高
缺点：
（1）不支持下标随机访问
（2）缓存命中低

在这里插入图片描述

deque
优势：头插头删，尾插尾删很不错
不足：
随机访问效率没有vector高
访问第i个值，【假设保持每个buff一样大，都是10】
如果第一个buff不是从头开始的，不在第一个buff，那么i -= 第一个buff的数据个数
第i/10个buff中
在这个buff的第i%10位置
中间插入删除如何实现？
如果不需要保持每个buff一样大，只能挪动数据
如果不需要保持每个buff一样大，可以对当前buff，扩容或者挪动数据

结论
1、小标随机访问，效果不错，但是跟vector仍有差距
2、中间插入删除，效率差

如果一个适配器经常头插头删、尾插尾删 -> deque
如果少量的下标访问 -> 可以用deque
如果大量的下标访问 -> 需要用vector
如果中间插入删除 -> list

在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/780953.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【74LS163做24进制计数器】2021-11-19

【74LS163做24进制计数器】2021-11-19

缘由用74LS163做24进制计数器-其他-CSDN问答,仿真multisim两个74LS163芯片如何构成47进制计数器-吐槽问答-CSDN问答 参考74ls163中文资料汇总&#xff08;74ls163引脚图及功能_内部结构图及应用电路&#xff09; - 电子发烧友网
阅读更多...
1.pwn的汇编基础（提及第一个溢出：整数溢出）

1.pwn的汇编基础（提及第一个溢出：整数溢出）

汇编掌握程度 能看懂就行&#xff0c;绝大多数情况不需要真正的编程(shellcode题除外) 其实有时候也不需要读汇编&#xff0c;ida F5 通常都是分析gadget&#xff0c;知道怎么用&#xff0c; 调试程序也不需要分析每一条汇编指令&#xff0c;单步执行然后查看寄存器状态即可 但…
阅读更多...
【Python机器学习】模型评估与改进——多分类指标

【Python机器学习】模型评估与改进——多分类指标

多分类问题的所有指标基本是上都来自于二分类问题&#xff0c;但是要对所有类别进行平均。多分类的精度被定义为正确分类的样本所占的比例。同样&#xff0c;如果类别是不平衡的&#xff0c;精度并不是很好的评估度量。 想象一个三分类问题&#xff0c;其中85%的数据点属于类别…
阅读更多...
Java（七）——多态

Java（七）——多态

个人简介 &#x1f440;个人主页&#xff1a; 前端杂货铺 ⚡开源项目&#xff1a; rich-vue3 &#xff08;基于 Vue3 TS Pinia Element Plus Spring全家桶 MySQL&#xff09; &#x1f64b;‍♂️学习方向&#xff1a; 主攻前端方向&#xff0c;正逐渐往全干发展 &#x1…
阅读更多...
Go语言如何入门，有哪些书推荐？

Go语言如何入门，有哪些书推荐？

Go 语言之所以如此受欢迎&#xff0c;其编译器功不可没。Go 语言的发展也得益于其编译速度够快。 对开发者来说&#xff0c;更快的编译速度意味着更短的反馈周期。大型的 Go 应用程序总是能在几秒钟之 内完成编译。而当使用 go run编译和执行小型的 Go 应用程序时&#xff0c;其…
阅读更多...
VMware虚拟机搭建CentOS7环境

VMware虚拟机搭建CentOS7环境

相关资料 安装VMware 双击VMware-workstation(16.1.1软件安装包.exe安装文件，点下一步 激活码文件复制激活码激活安装linux 1、点击创建虚拟机
阅读更多...
Open3D 删除点云中重叠的点（方法一）

Open3D 删除点云中重叠的点（方法一）

目录 一、概述 二、代码实现 三、实现效果 3.1原始点云 3.2处理后的点云 3.3计算结果 一、概述 在点云处理中&#xff0c;重叠点&#xff08;即重复点&#xff09;可能会对数据分析和处理的结果产生负面影响。因此&#xff0c;删除重叠点是点云预处理中常见且重要的步骤。…
阅读更多...
【网络安全】实验一（网络拓扑环境的搭建）

【网络安全】实验一（网络拓扑环境的搭建）

一、本次实验的实验目的 学习利用 VMware 创建虚拟环境 学习利用 VMware 搭建各自网络拓扑环境 二、创建虚拟机 三、克隆虚拟机 选择克隆的系统必须处于关机状态。 方法一&#xff1a; 方法二&#xff1a; 需要修改克隆计算机的名字&#xff0c;避免产生冲突。 四、按照要求完…
阅读更多...
机器学习原理之 -- 神经网络：由来及原理详解

机器学习原理之 -- 神经网络：由来及原理详解

神经网络&#xff08;Neural Networks&#xff09;是受生物神经系统启发而设计的一类计算模型&#xff0c;广泛应用于图像识别、语音识别、自然语言处理等领域。其基本思想是通过模拟人脑神经元的工作方式&#xff0c;实现对复杂数据的自动处理和分类。本文将详细介绍神经网络的…
阅读更多...
Scrapy框架的基本使用教程

Scrapy框架的基本使用教程

1、创建scrapy项目 首先在自己的跟目录文件下执行命令&#xff1a; PS D:\BCprogram\python_pro\bigdata> scrapy startproject theridion_grallatorscrapy startproject 项目名 具体执行操作如下&#xff1a;1、创建项目目录&#xff1a;Scrapy会在当前工作目录下创建一…
阅读更多...
【python中级】图像从从笛卡尔坐标系转换为极坐标系

【python中级】图像从从笛卡尔坐标系转换为极坐标系

【python中级】图像从从笛卡尔坐标系转换为极坐标系 1.背景2.生成二维图3.极坐标转换1.背景 笛卡尔坐标系就是我们常说的直角坐标系。 笛卡尔坐标系，也称为直角坐标系，是由法国数学家和哲学家勒内笛卡尔（Ren Descartes）发明的一种二维或三维坐标系统。它使用两个或三个相互…
阅读更多...
【Qt】Qt开发环境搭建

【Qt】Qt开发环境搭建

目录 一. Qt SDK的下载&安装 二. Qt相关工具介绍 Qt的常用开发工具有&#xff1a; Qt CreatorVisual StudioEclipse 一. Qt SDK的下载&安装 Qt 下载官网&#xff1a; http://download.qt.io/archive/qt/ 国内清华源: https://mirrors.tuna.tsinghua.edu.cn/qt/arc…
阅读更多...
C# WinForm —— 37 TabControl 控件介绍

C# WinForm —— 37 TabControl 控件介绍

1. 简介 管理一个TabPages集合的控件&#xff0c;也是一个分组控件 如果一个模块有多个子页面&#xff0c;可以使用TabControl控件进行页面切换 2. 属性 属性解释(Name)控件ID&#xff0c;在代码里引用的时候会用到Enabled控件是否启用Alignment确定选项卡是否显示在控件的…
阅读更多...
扩散模型笔记2

扩散模型笔记2

Ref:扩散模型的原理及实现&#xff08;Pytorch&#xff09; 在扩散模型中&#xff0c;每一步添加的噪声并不是完全一样的。具体来说&#xff0c;噪声的添加方式和量在每一步是根据特定的规则或公式变化的。这里我们详细解释每一步添加噪声的过程。 正向过程中的噪声添加&…
阅读更多...
两种转5V的DCDC电路：

两种转5V的DCDC电路：

最大电流&#xff1a;5A 最大电流&#xff1a;3A 验证通过&#xff1a;RT8289GSP性能更佳&#xff0c;带载能力更强&#xff1a;
阅读更多...
前端JS特效第22波：jQuery滑动手风琴内容切换特效

前端JS特效第22波：jQuery滑动手风琴内容切换特效

jQuery滑动手风琴内容切换特效&#xff0c;先来看看效果&#xff1a; 部分核心的代码如下&#xff1a; <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xm…
阅读更多...
Guitar Pro8.2让你的吉他弹奏如虎添翼！

Guitar Pro8.2让你的吉他弹奏如虎添翼！

亲爱的音乐爱好者们&#xff0c;今天我要跟大家安利一个让我彻底沉迷其中的神器——Guitar Pro8.2&#xff01;这可不是一般的软件&#xff0c;它简直是吉他手们的福音。不管你是初学者还是老鸟&#xff0c;这个打谱软件都能给你带来前所未有的便利和价值。 让我们来聊聊Guita…
阅读更多...
昇思25天学习打卡营第9天|ResNet50图像分类

昇思25天学习打卡营第9天|ResNet50图像分类

一、Resnet残差网络模型 构建残差网络结构;Building BlockBottleneck 残差结构由两个分支构成&#xff1a;一个主分支 &#x1d439;(&#x1d465;)&#xff0c;一个shortcuts&#xff08;图中弧线表示,&#x1d465;&#xff09;。 得到残差网络结构:&#x1d439;(&#x…
阅读更多...
python根据父母身高预测儿子身高

python根据父母身高预测儿子身高

题目 从键盘输入父母的升高&#xff0c;并使用eval()或float()转换输入的数据类型。计算公式&#xff1a;儿子身高&#xff08;父亲身高母亲身高&#xff09;*0.54. father_heighteval(input(请输入爸爸的身高&#xff1a;)) mother_heighteval(input(请输入妈妈的身高&#…
阅读更多...
RAID 冗余磁盘阵列

RAID 冗余磁盘阵列

RAID也是Linux操作系统中管理磁盘的一种方式。 只有Linux操作系统才支持LVM的磁盘管理方式。 而RAID是一种通用的管理磁盘的技术&#xff0c;使用于多种操作系统。 优势&#xff1a;提升数据的读写速度&#xff0c;提升数据的可靠性。具体实现哪什么功能&#xff0c;要看你所…
阅读更多...
最新文章

Copyright @ 2022~2023