C++初阶：容器适配器stack与queue

目录

  • 1. stack与queue的使用练习
    • 1.1 stack的常用接口（栈）
    • 1.2 queue常用接口（队列）
    • 1.3 priority_queue的常用接口（堆）
  • 2. 容器适配器
    • 2.1 栈的实现
    • 2.2 队列的实现
    • 3. 堆（priority_queue）的实现

1. stack与queue的使用练习

1.1 stack的常用接口（栈）

  1. push（尾插）
  2. pop（尾删）
  3. top（取栈顶）
  4. empty（判空）
  5. size（栈的长度）

1. 最小栈

  1. 题目信息：
    在这里插入图片描述
  2. 题目链接：
    最小栈
  3. 一个栈存数据，一个栈存最小值
    <1> 每次插入一个数据都进行判断，并将当前栈的最小值插入
    <2> 优化1：当插入数据大于当前最小值时不插入，删除数据栈中数据时，调整最小栈当删除值等于当前最小值再删除
    <3> 优化2：最小栈中存复合类型数据，最小值与最小值的计数
class MinStack 
{
public:
    //会调用成员变量的默认构造
    MinStack() 
    {}
    
    void push(int val) 
    {
        if(minst.empty() || val <= minst.top())
        {
            minst.push(val);
        }

        st.push(val);
    }
    
    void pop() 
    {
        if(st.top() == minst.top())
        {
            minst.pop();
        }

        st.pop();
    }
    
    int top() 
    {
        return st.top();
    }
    
    int getMin() 
    {
        return minst.top();
    }

    stack<int> st;
    stack<int> minst;
};

2. 栈的弹出压入序列

  1. 题目信息：
    在这里插入图片描述
  2. 题目链接：
    栈的弹出压入序列
  3. 思路：创建一个栈来模拟弹出插入过程
class Solution 
{
public:
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) 
    {
        //用栈模拟
        //先入栈，再判断
        //1.栈中数据与出栈序列相同，出栈，出栈序列++（循环进行）
        //2. 不同，接着入栈
        //入栈序列结束后，出栈序列遍历完，没遍历完
        stack<int> st;
        int pushi = 0;
        int popi = 0;
        while(pushi < pushV.size())
        {
            st.push(pushV[pushi]);
            pushi++;
			
			//注意判断条件与越界可能
            while(!st.empty() && popV[popi] == st.top())
            {
                st.pop();
                popi++;
            }
        }

        if(popi == popV.size())
        {
            return true;
        }

        return false;
    }
};

3. 逆波兰表达式求值

  1. 逆波兰表达式，即后缀表达式，表示方式为运算符在运算数之后。
  2. 中缀表达式转后缀表达式的方法：
    遍历中缀表达式，创建一个栈存储运算符
    <1> 当遍历到运算数时，直接将运算数输出
    <2> 当遍历到运算符时：
    一，若栈为空将运算符直接入栈
    二，若栈不为空，当前运算符优先级高于栈顶运算符，将此运算符入栈；若当前运算符优先级低于栈顶运算符，将栈顶运算符输出。
  3. 当运算表达式中存在括号时，我们遇到括号就进行递归，再开一个栈
  4. switch…case…语句只能使用整形家族的数据做参数，atoi（字符串转int），atod（字符串转double）
  5. 题目信息：
    在这里插入图片描述
  6. 题目链接：
    逆波兰表达式求值
  7. 思路：后缀表达式运算方式，创建一个栈存储运算数，当遍历到运算符时，取出两个栈顶元素进行相应运算之后再入栈，重复上述步骤，直至遍历完整个后缀表达式。
class Solution
{
public:
	int evalRPN(vector<string>& tokens)
	{
		stack<int> num_st;;

		for (auto it : tokens)
		{
            if(it != "+" && it != "-" && it != "*" && it != "/")
            {
                num_st.push(atoi(it.c_str()));
            }
            else
            {
                int right = num_st.top();
				num_st.pop();
				int left = num_st.top();
				num_st.pop();
                switch (it[0])
                {
                    case '+':
                        num_st.push(left + right);
                        break;
                    case '-':
                        num_st.push(left - right);
                        break;
                    case '*':
                        num_st.push(left * right);
                        break;
                    case '/':
                        num_st.push(left / right);
                        break;
                }
            }
		}

		return num_st.top();
	}
};
  1. 补充：C++两个队列实现栈

1.2 queue常用接口（队列）

  1. push（尾插）
  2. pop（头删）
  3. front（队首元素）
  4. back（队尾元素）
  5. empty（判空）
  6. size（队列长度）

1. 二叉树层序遍历

  1. 题目信息：
    在这里插入图片描述
  2. 题目链接：
    二叉树的层序遍历
  3. 思路：队列存储，计数变量
class Solution 
{
public:
    vector<vector<int>> levelOrder(TreeNode* root) 
    {
        vector<vector<int>> ret;
        queue<TreeNode*> travel;
        int levelSize = 0;

        if(root == NULL)
        {
            return ret;
        }

        travel.push(root);
        levelSize++;

        while(!travel.empty())
        {
            vector<int> part;
            while(levelSize)
            {
                TreeNode* node = travel.front();
                part.push_back(node->val);
                travel.pop();
                levelSize--;
                if(node->left)
                    travel.push(node->left);
                if(node->right)
                    travel.push(node->right);
            }
            ret.push_back(part);
            levelSize = travel.size();
        }

        return ret;
    }
};

1.3 priority_queue的常用接口（堆）

  1. push
  2. pop（删除堆顶元素）
  3. top（返回堆顶元素）
  4. empty（判空）
  5. size（返回堆的长度）
    补充：默认为大堆

1. 堆排序

priority_queue<int> heap;
heap.push(10);
heap.push(3);
heap.push(6);
heap.push(2);
heap.push(1);

while (!heap.empty())
{
	cout << heap.top() << " ";
	heap.pop();
}
cout << endl;
  1. 补充：此种堆排的空间复杂度很高O(n)，推荐在vector容器中直接建堆堆排

2. TopK算法

int arr[] = { 10,3,2,5,6,8,9,4,1,7,11 };
int k = 3;
//greater建小堆，less建大堆
priority_queue<int, vector<int>, greater<int>> heap(arr, arr + k);
while (k < sizeof(arr) / sizeof(arr[0]))
{
	if (arr[k] > heap.top())
	{
		heap.pop();
		heap.push(arr[k]);
	}
	k++;
}

while (!heap.empty())
{
	cout << heap.top() << " ";
	heap.pop();
}
cout << endl;
  1. 取数据头部k个数据建立一个小堆，在从第k + 1个数开始遍历，当数据大于堆顶数据时，交换二者，制止遍历完整个数组。
  2. 建堆的时间复杂度为O(N)，堆的一次向下调整时间复杂度为O( l o g N log^N logN)，TopK算法的时间复杂度为K + (N - K) l o g K log^K logK

2. 容器适配器

  1. 在数据结构的学习中，我们知道栈，队列，堆等数据结构，底层数据存储的方式上仍使用的是实现过链表顺序表等基础结构，只是对外的接口不同，仅支持规定的插入删除操作，且不支持遍历。
  2. 因此，再去专门实现一份重复性极高的代码于效率上是极低的也没有必要，我们将已经实现过的顺序表链表等数据结构进行封装，只对外开放特定的接口，从而来到达栈，队列等数据结构的效果。这里采用模板参数的方式进行具体实现。
  3. const迭代器增加模板参数的原因为，只有一个运算符重载的返回值不同，其他参数与返回值都相同

2.1 栈的实现

  1. 自定义类型的成员变量会自动调用自己的默认成员函数
template<class T, class Container = vector<T>>
class stack
{
public:
	void push(const T& val)
	{
		con.push_back(val);
	}

	void pop()
	{
		con.pop_back();
	}

	T& top()
	{
		return  con.back();
	}

	const T& top() const
	{
		return con.back();
	}

	int size()
	{
		return con.size();
	}

	bool empty()
	{
		return con.size() == 0;
	}

private:
	Container con;
};

2.2 队列的实现

template<class T, class Container = list<T>>
class queue
{
public:
	void push(T val)
	{
		con.push_back(val);
	}

	void pop()
	{
		con.pop_front();
	}

	T& top()
	{
		return con.front();
	}

	const T& top() const
	{
		return con.front();
	}

	int size()
	{
		return con.size();
	}

	bool empty()
	{
		return con.size() == 0;
	}

private:
	Container con;
};

3. 堆（priority_queue）的实现

template<class T>
class Greater
{
public:
	bool operator()(const T& left, const T& right)
	{
		return left > right;
	}
};

template<class T>
class less
{
public:
	bool operator()(const T& left, const T& right)
	{
		return left < right;
	}
};

//支持[]访问
template<class T, class Container = vector<T>, class Compare = Greater<T>>
class pirority_queue
{
public:
	int size()
	{
		return con.size();
	}

	bool emtpy()
	{
		return con.size() == 0;
	}

	T& top()
	{
		return con.front();
	}

	const T& top() const
	{
		return con.front();
	}

	void Adjustup()
	{
		int child = con.size() - 1;
		int parent = (child - 1) / 2;

		while (child > 0)
		{
			if (comp(con[parent], con[child]))
			{
				std::swap(con[child], con[parent]);
			}

			child = parent;
			parent = (child - 1) / 2;
		}
	}

	//向上调整
	void push(T val)
	{
		con.push_back(val);
		Adjustup();
	}

	void Adjustdown()
	{
		size_t parent = 0;
		size_t child = parent * 2 + 1;
		while (child < con.size())
		{
			if (child + 1 < con.size() && comp(con[child], con[child + 1]))
			{
				child++;
			}

			if (comp(con[parent], con[child]))
			{
				std::swap(con[parent], con[child]);
			}
			else
			{
				break;
			}

			parent = child;
			child = parent * 2 + 1;
		}
	}

	void pop()
	{
		std::swap(con[0], con[size() - 1]);
		con.pop_back();
		Adjustdown();
	}

private:
	Container con;
	Compare comp;
};
  1. 堆的数据结构可以细分为大堆与小堆，面对不同的使用场景我们使用的堆也不同，正常情况下，我们更改堆的模式只能通过手动调整源码，更改比较符号的方式。
  2. 手动调整的方式使得堆的切换十分麻烦且失去了应用价值，大小堆分别实现又增加了代码的冗余性，这里我们采用仿函数或回调函数的方式来解决这一问题。
  3. 回调函数，C语言中函数也是有指针的，我们可以通过传递函数指针类型的参数对象，从而达到在一个函数内部通过指针调用其他需要函数的效果。（函数指针类型相同，内部实现不同，返回值不同）
  4. 仿函数是一个类，是通过重载operator()运算符来达到函数调用的表现形式与效果。
  5. 回调函数使用的函数指针其本质只是一个指针，我们将其作为参数使用时还需要传递所需要函数的确定地址，当作为类成员时我们需要专门为其编写构造函数，调用时也需要传参，而仿函数其每个对象的内部都具有operator()重载。
  6. 函数指针可以作为函数模板的类型参数，在函数的内部实现中通过传参调用对应函数。（库函数sort）

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

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

相关文章

在Python Matplotlib中让X轴标签向右对齐并且向右稍微移动一些距离

在Python Matplotlib中让X轴标签向右对齐并且向右稍微移动一些距离

在Python Matplotlib中让X轴标签向右对齐并且向右稍微移动一些距离 在Matplotlib中画图时&#xff0c;当x轴标签很长时&#xff0c;我们通常会使用rotation对标签进行倾斜显示。但是这个时候有些标签&#xff08;长度过长的&#xff0c;例如很长的单词&#xff09;会重叠。这个…
阅读更多...
MySQL驱动Add Batch优化实现

MySQL驱动Add Batch优化实现

MySQL 驱动 Add Batch 优化实现 MySQL 驱动会在 JDBC URL 添加 rewriteBatchedStatements 参数时&#xff0c;对 batch 操作进行优化。本文测试各种参数组合的行为&#xff0c;并结合驱动代码简单分析。 batch参数组合行为 useServerPrepStmts 参数 PreparedStatement psmt…
阅读更多...
设置MATLAB三维绘图的视角

设置MATLAB三维绘图的视角

MATLAB三维绘图plot3在生成绘图后&#xff0c;默认显示视角是斜着的&#xff1a; 使用view(2)命令可以使其转成XoY平面&#xff08;从上往下看的视角&#xff09;&#xff1a;
阅读更多...
推荐多样性 - 华为OD统一考试(C卷)

推荐多样性 - 华为OD统一考试(C卷)

OD统一考试&#xff08;C卷&#xff09; 分值&#xff1a; 200分 题解&#xff1a; Java / Python / C 题目描述 推荐多样性需要从多个列表中选择元素&#xff0c;一次性要返回N屏数据&#xff08;窗口数量&#xff09;&#xff0c;每屏展示K个元素&#xff08;窗口大小&#…
阅读更多...
深度强化学习（十）（TRPO）

深度强化学习（十）（TRPO）

深度强化学习&#xff08;十&#xff09;&#xff08;TRPO与PPO&#xff09; 一.信赖域方法 原问题&#xff1a; maxmize J ( θ ) \text{maxmize} \qquad\qquad J(\theta) maxmizeJ(θ) J J J是个很复杂的函数&#xff0c;我们甚至可能不知道 J J J 的解析表达式&#xff…
阅读更多...
【Entity Framework】 EF三种开发模式

【Entity Framework】 EF三种开发模式

【Entity Framework】 EF三种开发模式 文章目录 【Entity Framework】 EF三种开发模式一、概述二、DataBase First2.1 DataBase First简介2.2 DataBase First应用步骤2.3 DataBase First总结 三、Model First3.1 Model First简介3.2 Model First实现步骤 四、Code First4.1 Cod…
阅读更多...
YOLOv9有效改进专栏汇总|未来更新卷积、主干、检测头注意力机制、特征融合方式等创新！[2024/3/23]

YOLOv9有效改进专栏汇总|未来更新卷积、主干、检测头注意力机制、特征融合方式等创新！[2024/3/23]

​ 专栏介绍&#xff1a;YOLOv9改进系列 | 包含深度学习最新创新&#xff0c;助力高效涨点&#xff01;&#xff01;&#xff01; 专栏介绍 YOLOv9作为最新的YOLO系列模型&#xff0c;对于做目标检测的同学是必不可少的。本专栏将针对2024年最新推出的YOLOv9检测模型&#xff0…
阅读更多...
一文看懂，如何精细化地进行跨域文件管控

一文看懂，如何精细化地进行跨域文件管控

随着企业规模的扩大和分支机构的增多&#xff0c;会出现不同地理位置、组织机构或网络安全域之间进行文件交换的场景。 像很多金融机构在全国或全球范围内会设立不同的分支机构和办事处&#xff0c;因此会存在不同组织机构之间的数据流转&#xff0c;即跨域文件传输。跨域文件传…
阅读更多...
知识分享|视频号带货需要满足什么硬性条件?

知识分享|视频号带货需要满足什么硬性条件?

视频号带货作为一种新兴的电商模式&#xff0c;已经逐渐受到越来越多人的关注。然而&#xff0c;想要在这一领域取得成功&#xff0c;并不是一件轻松的事情。除了需要具备一定的营销技巧和内容创作能力外&#xff0c;还有一些硬性条件必须得到满足。 首先&#xff0c;视频号带货…
阅读更多...
GIMP - GNU 图像处理程序 - 中文版

GIMP - GNU 图像处理程序 - 中文版

GIMP - GNU 图像处理程序 - 中文版 1. Edit -> Preferences -> Interface2. Chinese [zh_CN]3. 重启 GIMP 即可References 1. Edit -> Preferences -> Interface 2. Chinese [zh_CN] 3. 重启 GIMP 即可 References [1] Yongqiang Cheng, https://yongqiang.blog.…
阅读更多...
Xcode Launching “XXX“ is taking longer than expected

Xcode Launching “XXX“ is taking longer than expected

文章目录 1.问题2.如何进入iOS DeviceSupport目录3.解决方法4.参考博客 1.问题 LLDB is likely reading from device memory to resolve symbols 2.如何进入iOS DeviceSupport目录 3.解决方法 进入iOS DeviceSupport目录&#xff0c;删除该真机对应的架构文件&#xff08;比如…
阅读更多...
谁再问你数据库三范式，这篇文章甩给他！！！

谁再问你数据库三范式，这篇文章甩给他！！！

前几天有粉丝私信说面试被问到了数据库三范式&#xff08;面试问这种的不去也好&#xff09;&#xff0c;今天我们就来聊聊。在数据库设计的过程中&#xff0c;为了确保数据的准确性和完整性&#xff0c;我们通常遵循一定的规则和标准&#xff0c;其中最为人所熟知的便是“数据…
阅读更多...
C++模版（基础）

C++模版（基础）

目录 C泛型编程思想 C模版 模版介绍 模版使用 函数模版 函数模版基础语法 函数模版原理 函数模版实例化 模版参数匹配规则 类模版 类模版基础语法 C泛型编程思想 泛型编程&#xff1a;编写与类型无关的通用代码&#xff0c;是代码复用的一种手段。 模板是泛型编程…
阅读更多...
优化选址问题 | 基于和声搜索算法求解基站选址问题含Matlab源码

优化选址问题 | 基于和声搜索算法求解基站选址问题含Matlab源码

目录 问题代码问题 和声搜索算法（Harmony Search, HS）是一种模拟音乐创作过程中乐师们凭借自己的记忆，通过反复调整各乐器的音调，直至达到最美和声状态为启发，通过反复调整解向量的各分量来寻求全局最优解的智能优化算法。 下面是一个基于和声搜索算法求解基站选址问题的…
阅读更多...
大创项目推荐 基于图像识别的跌倒检测算法

大创项目推荐 基于图像识别的跌倒检测算法

前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 基于图像识别的跌倒检测算法 该项目较为新颖&#xff0c;适合作为竞赛课题方向&#xff0c;学长非常推荐&#xff01; &#x1f9ff; 更多资料, 项目分享&#xff1a; https://gitee.com/dancheng-senior/…
阅读更多...
MySQL数据库的日志管理以及备份和恢复

MySQL数据库的日志管理以及备份和恢复

目录 1、日志管理 2、查询日志 3、数据备份的重要性 4、数据库备份的分类 4.1物理备份 4.2逻辑备份&#xff1a; 4.3完全备份 5、常见的备份方法 6、MySQL完全备份 6.1MySQL完全备份优缺点 6.2数据库完全备份分类 6.2.1物理冷备份与恢复 6.2.2mysqldump备份…
阅读更多...
什么是回归测试？

什么是回归测试？

今天看看回归测试的基本概念。 什么是回归测试? 回归测试被定义为一种软件测试&#xff0c;以确认最近的程序或代码更改没有对现有功能产生不利影响。回归测试只是对已经执行的测试用例的全部或部分选择&#xff0c;重新执行这些用例以确保现有功能正常工作。 进行此测试是…
阅读更多...
MYSQL高级语句(一)

MYSQL高级语句(一)

目录 一、常用查询 1、order by 按关键字排序 1.升序排序 2.降序排序 3.结合where进行条件过滤再排序 4.多字段排序 2、区间判断及查询不重复记录 1. and / or 且与或的使用 2.嵌套、多条件使用 3.distinct 查询不重复记录 3、GROUP BY 对结果进行分组 4、Li…
阅读更多...
就业班 第二阶段 2401--3.25 day5 mycat读写分离

就业班 第二阶段 2401--3.25 day5 mycat读写分离

[TOC] 启动并更改临时密码 [rootmysql1~]# systemctl start mysqld && passwdgrep password /var/log/mysqld.log | awk END{ print $NF} && mysqladmin -p"$passwd" password Qwer123..; MyCAT读写分离 Mycat 是一个开源的数据库系统&#xff0c;但…
阅读更多...
【Node.js】WebSockets

【Node.js】WebSockets

概述 WebSockets是一种在浏览器和服务器之间建立持久连接的协议&#xff0c;它允许服务器主动推送数据给客户端&#xff0c;并且在客户端和服务器之间实现双向通信。 建立连接&#xff1a;客户端通过在JavaScript代码中使用WebSocket对象来建立WebSockets连接。例如&#xff1…
阅读更多...
最新文章

Copyright @ 2022~2023