【C++】stack/queue

链表完了之后就是我们的栈和队列了,当然我们的STL中也有实现,下面我们先来看一下简单用法,跟我们之前C语言实现的一样,stack和queue有这么几个重要的成员函数

最主要的就是这么几个:empty,push,pop,top(front),size,为什么要说这几个重要的呢?因为我们发现,stack和queue并没有我们之前的容器的迭代器,说明它们跟之前学的容器并不同,它们叫做适配器

什么叫做适配器呢?我们听过笔记本电脑的电源适配器,它就是将220V的电压转化成电脑需要的电压,所以适配器的本质是转换回到我们这里,stack和queue这个适配器就可以将其他的容器转换成实例化后的stack和queue

我们可以看到,类模板的第二个参数是要传一个容器,当然不传也行,它是有缺省值的,这里的缺省值是deque,这个容器是介于vector和list之间的,为什么要有一个这样的容器呢?

我们首先来总结一下vector和list的优缺点

vector:优点是下标随机访问和缓存命中率高(缓存命中率就是指比如我要给定vector中连续几个元素的值,我要一个一个给定,当我给定第一个的时候,它并不是只把第一个给定到内存中,而是把它及周围的位置都拿到了内存中,这样我给定第二个值时,就不需要再拿入到内存中了),缺点是前面部分插入删除效率低,扩容有消耗

list:优点是任意位置插入删除效率高和按需申请释放(每次就申请一个节点的空间,不会浪费),缺点是不支持下标随机访问,缓存命中率低

我们可以来试一下

既然如此,我们要模拟实现的话,就不用像之前那么写了,而是跟库一样,模板参数传个容器,下面的几个关键函数赋用容器的就可以了

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

下面来几道有关的题来帮助我们更好的使用

这个题其实就是模拟我们人脑在做这种题时的想法,我们一般先看弹出顺序的第一个,然后看怎么怎么压入才会让它第一个弹出。第一个其实跟后边几个都一样,最后走到头,看栈是否为空,为空就是符合

class Solution {
  public:
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        stack<int>s;
        int n = popV.size();
        for (int pushi = 0, popi = 0; pushi < n && popi < n;) {
            while (s.empty() || s.top() != popV[popi]) {
                s.push(pushV[pushi++]);
                if (pushi == n)break;
            }
            while (!s.empty() && s.top() == popV[popi]) {
                s.pop();
                popi++;
            }
        }
        if (s.empty())return true;
        return false;
    }
};

这里实际上就是给你一个后缀表达式,让你求出表达式的值,我们人一般看的就是中缀表达式,那么后缀表达式是什么呢?其实就是把运算符放到两个操作数的后面。所以解题思路就是看到数字就入栈,看到运算符就从栈中取两个值进行运算,把结果再放到栈中,直到把后缀表达式走完

class Solution {
public:
    int evalRPN(vector<string>& t) {
stack<int>st;
for(auto e:t){
    if(e=="+"||e=="-"||e=="*"||e=="/"){
        int right=st.top();
        st.pop();
        int left=st.top();
        st.pop();
switch(e[0]){
    case '+':
    st.push(left+right);
    break;
    case '-':
    st.push(left-right);
    break;
    case '*':
    st.push(left*right);
    break;
    case '/':
    st.push(left/right);
    break;
}
    }
    else st.push(stoi(e));
}
return st.top();
    }
};

我们这里是给定一个后缀表达式,那么我们应该如何求一个中缀表达式的后缀表达式呢?我这里简单实现了一下,可以传一个string,string里面要么是字母用来表示数字,要么是+-*/

string postfix(string s) {
	stack<char>st;
	string ret;
	for (int i = 0; i < s.size();) {
		char e = s[i];
		if (e == '+' || e == '-' || e == '*' || e == '/') {
			if (st.empty()) {
				st.push(e);
				i++;
			}
			else if ((e == '*' || e == '/') && (st.top() == '+' || st.top() == '-')) {
				st.push(e);
				i++;
			}
			else {
				ret += st.top();
				st.pop();
			}
		}
		else if (e == '(') {
			int j = i;
			int k = j;
			int num = 1;
			for (k = j+1; k < s.size(); k++) {
				if (s[k] == '(')num++;
				if (s[k] == ')'&&num==1)break;
				if (s[k] == ')')num--;
			}
			string tmp(s.begin() + j + 1, s.begin() + k);
			ret += postfix(tmp);
			i+=k-j+1;
		}
		else {
			ret += e;
			i++;
		}
	}
	while (!st.empty()) {
		ret += st.top();
		st.pop();
	}
	return ret;
}

先简单说一下一个正常的式子转后缀表达式是什么逻辑,先说没有括号的情况下

给一个string,从左向右开始:先创建一个栈

1.如果遇到非运算符直接写入到最终结果中

2.如果遇到运算符,(1).如果栈为空或此运算符比栈顶运算符的优先级高,那么就入栈;(2).如果优先级相等或低,那么栈顶元素出栈,放到最终结果,继续仍然用此运算符进行下一轮判断

一直循环,直到string结束,最后把栈中的都移入到最终结果

如果有括号,将括起来的部分进行函数递归,重复上述过程,把递归完之后的结果加入到最终结果中

层序遍历肯定是要用到队列的,这个题的返回值告诉我们要一层一层的给到vector中,这就要求我们记录下每一层的节点个数才可以

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ret;
        if (root == nullptr)
            return ret;
        queue<TreeNode*> qu;
        qu.push(root);
        int levelsize = qu.size();
     while(!qu.empty()){
         vector<int>f;
         while(levelsize--){
             TreeNode* tmp=qu.front();
             qu.pop();
             f.push_back(tmp->val);
             if(tmp->left!=nullptr)qu.push(tmp->left);
             if(tmp->right!=nullptr)qu.push(tmp->right);
         }
         ret.push_back(f);
         levelsize=qu.size();
     }
     return ret;
    }
};

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

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

相关文章

python读取大型csv文件,降低内存占用,提高程序处理速度

文章目录 简介读取前多少行读取属性列逐块读取整个文件总结参考资料 简介 遇到大型的csv文件时&#xff0c;pandas会把该文件全部加载进内存&#xff0c;从而导致程序运行速度变慢。 本文提供了批量读取csv文件、读取属性列的方法&#xff0c;减轻内存占用情况。 import pand…

git commit --amend

git commit --amend 1. 修改已经输入的commit 1. 修改已经输入的commit 我已经输入了commit fix: 删除无用代码 然后现在表示不准确&#xff0c;然后我通过命令git commit --amend修改commit

鼓楼夜市管理wpf+sqlserver

鼓楼夜市管理系统wpfsqlserver 下载地址:鼓楼夜市管理系统wpfsqlserver 说明文档 运行前附加数据库.mdf&#xff08;或sql生成数据库&#xff09; 主要技术&#xff1a; 基于C#wpf架构和sql server数据库 功能模块&#xff1a; 登录注册 鼓楼夜市管理系统主界面所有店铺信…

企业电子招投标系统源码-从源码到实践:深入了解鸿鹄电子招投标系统与电子招投标

在数字化采购领域&#xff0c;企业需要一个高效、透明和规范的管理系统。通过采用Spring Cloud、Spring Boot2、Mybatis等先进技术&#xff0c;我们打造了全过程数字化采购管理平台。该平台具备内外协同的能力&#xff0c;通过待办消息、招标公告、中标公告和信息发布等功能模块…

Tictoc3例子

在tictoc3中&#xff0c;实现了让 tic 和 toc 这两个简单模块之间传递消息&#xff0c;传递十次后结束仿真。 首先来介绍一下程序中用到的两个函数&#xff1a; 1.omnetpp中获取模块名称的函数 virtual const char *getName() const override {return name ? name : "&q…

Python 一步一步教你用pyglet制作汉诺塔游戏(终篇)

目录 汉诺塔游戏 完整游戏 后期展望 汉诺塔游戏 汉诺塔&#xff08;Tower of Hanoi&#xff09;&#xff0c;是一个源于印度古老传说的益智玩具。这个传说讲述了大梵天创造世界的时候&#xff0c;他做了三根金刚石柱子&#xff0c;并在其中一根柱子上从下往上按照大小顺序摞…

js【详解】Promise

为什么需要使用 Promise &#xff1f; 传统回调函数的代码层层嵌套&#xff0c;形成回调地狱&#xff0c;难以阅读和维护&#xff0c;为了解决回调地狱的问题&#xff0c;诞生了 Promise 什么是 Promise &#xff1f; Promise 是一种异步编程的解决方案&#xff0c;本身是一个构…

套接字的地址结构,IP地址转换函数,网络编程的接口

目录 一、套接字的地址结构 1.1 通用socket地址结构 1.2 专用socket地址结构 1.2.1 tcp协议族 1.2.3 IP协议族 二、IP地址转换函数 三、网络编程接口 3.1 socket() 3.2 bind() 3.3 listen() 3.4 accept() 3.5 connect() 3.6 close() 3.7 recv()、send() 3.8 recv…

手写简易操作系统(五)--获得物理内存容量

前情提要 上一章中我们进入了保护模式&#xff0c;并且跳转到了32位模式下执行。这一章较为简单&#xff0c;我们来获取物理内存的实际容量。 一、获得内存容量的方式 在Linux中有多种方法获取内存容量&#xff0c;如果一种方法失败&#xff0c;就会试用其他方法。其本质上是…

考研数学|汤家凤《1800》vs 张宇《1000》,怎么选?

汤家凤的1800题和张宇的1000题都是备考数学考研的热门选择&#xff0c;但究竟哪个更适合备考呢&#xff1f;下面分享一些见解。 首先&#xff0c;让我们来看看传统习题册存在的一些问题。虽然传统习题册通常会覆盖考试的各个知识点和题型&#xff0c;但其中一些问题在于它们可…

JDBC连接MysqL

import java.sql.*;public class Demo {public static void main(String[] args) throws ClassNotFoundException, SQLException {//1.注册驱动&#xff0c;加载驱动&#xff1b;Class.forName("com.mysql.jdbc.Driver");//2.获得连接,返回connection类型的对象&…

汤唯短发造型:保留经典和适合自己的风格,也许才是最重要的

汤唯短发造型&#xff1a;保留经典和适合自己的风格&#xff0c;也许才是最重要的 汤唯短发造型登上Vogue四月刊封面&#xff0c;引发网友热议。#李秘书讲写作#说说是怎么回事&#xff1f; 这次Vogue四月刊的封面大片&#xff0c;汤唯以一头短发亮相&#xff0c;身穿五颜六色的…

钉钉平台“智”领宠物界,开启萌宠智能新时代!

在当前数字化转型的浪潮中&#xff0c;钉钉用便捷的数字化解决方案推动了宠物业界的智能升级。一家宠物用品公司采用无雀科技数字化管理系统&#xff0c;与钉钉平台结合&#xff0c;解决了小型企业普遍存在的财务管理不清晰、业务流程不规范、客户信息核对繁琐等痛点问题。 针对…

一周学会Django5 Python Web开发-Django5内置模板引擎-模板继承

锋哥原创的Python Web开发 Django5视频教程&#xff1a; 2024版 Django5 Python web开发 视频教程(无废话版) 玩命更新中~_哔哩哔哩_bilibili2024版 Django5 Python web开发 视频教程(无废话版) 玩命更新中~共计34条视频&#xff0c;包括&#xff1a;2024版 Django5 Python we…

Linux中文件的权限

我们首先需要明白&#xff0c;权限 用户角色 文件的权限属性 一、拥有者、所属组和other&#xff08;用户角色&#xff09; 以文件file1为例 第一个箭头所指处即是文件的拥有者&#xff0c;拥有者为zz 第二个箭头所指处即使文件的所属组&#xff0c;所属组为zz 除去拥有者…

嵌入式系统工程师错题总结

笔者来介绍一下嵌入式系统工程师考试的一些易错题目 题目介绍  流水线指令计算公式&#xff1a;一条指令总时间max&#xff08;单个指令执行时间&#xff09;*&#xff08;指令数-1&#xff09;  平均故障间隔时间  ICMP协议&#xff1a;传送通信问题相关的消息。 …

电脑打开应用慢

电脑打开什么应用都很慢 我的电脑是i73060&#xff0c;但是打开应用很慢 解决办法&#xff1a; 在注册表[HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\CI\Policy]将"VerifiedAndReputablePolicyState"的值设置为0&#xff0c;如果没有这一项&#xff0c;就…

SPI、Spring SPI、SpringFactoriesLoader

一、SPI技术 SPI全名Service Provider interface&#xff0c;翻译过来就是“服务提供接口”&#xff0c;再说简单就是提供某一个服务的接口&#xff0c; 提供给服务开发者或者服务生产商来进行实现。 Java SPI 是JDK内置的一种动态加载扩展点的实现。 这个机制在一般的业务代…

【数据集】2023自动驾驶开源数据集-学习笔记

文章目录 1. 自动驾驶有哪些公开数据集2. 预测相关的数据集有哪些 1. 自动驾驶有哪些公开数据集 waymo open dataset 适应任务: 域适应&#xff0c;2D追踪&#xff0c;2D检测&#xff0c;3D追踪&#xff0c;3D检测&#xff0c;实时2D检测&#xff0c;实时3D检测&#xff0c;交互…

深入解析Java内存模型

一、背景 并发编程本质问题是&#xff1a;CPU、内存以及IO三者之间的速度差异。CPU速度快于内存、内存访问速度又远远快于IO&#xff0c;根据木桶理论&#xff0c;程序性能取决于最慢的操作&#xff0c;即IO操作。这样会出现CPU和内存交互时&#xff0c;CPU性能无法被充分利用…