【C++】stack（一）

文章目录1.stack的介绍和使用1.1 stack的介绍1.2 stack的使用最小栈栈的弹出压入序列逆波兰表达式求值用两个栈实现队列1.stack的介绍和使用1.1 stack的介绍stack的文档介绍1.2 stack的使用函数说明接口说明stack()构造空的栈empty()检测stack是否为空size()返回stack中元素的个数top()返回栈顶元素的引用push()将元素val压入stack中pop()将stack中尾部的元素弹出最小栈1.插入值valminst栈顶数据minst就要插入val。如果valminst栈顶数据时却不插入如果删除st栈顶数据minst栈顶数据因为和st栈顶数据相等也会被删除2.为什么可以没有MinStack空 {} 因为 MinStack 内部通常使用其他容器如 std::stack 或std::vector来存储数据而这些容器自身就有默认构造函数能够正确初始化为空状态。 因此MinStack的构造函数不需要做任何额外工作只需调用成员变量的默认构造即可。而成员变量的默认构造会被编译器自动调用即使构造函数体为空。实际上如果你完全省略 MinStack() {}这个显式定义编译器也会隐式生成一个完全相同的默认构造函数。所以“可以没有”指的是即使你不写这个函数程序也能编译通过。classMinStack{public:MinStack(){}voidpush(intval){_st.push(val);if(_minst.empty()||val_minst.top()){_minst.push(val);}}voidpop(){if(_st.top()_minst.top())_minst.pop();_st.pop();}inttop(){return_st.top();}intgetMin(){return_minst.top();}private:stackint_st;stackint_minst;};栈的弹出压入序列思路入栈序列入栈栈顶数据跟出栈序列比较2.1 相等持续出栈顶数据直到不相等或栈为空2.2 不相等继续1,2直到入栈序列进入完了如果入栈序列进入完了而出数据的栈为空则合法否则不合法class Solution{public:boolIsPopOrder(vectorintpushV,vectorintpopV){size_tpushi0,popi0;stackintst;while(pushipushV.size()){st.push(pushV[pushi]);while(!st.empty()st.top()popV[popi]){st.pop();popi;}pushi;}returnst.empty();}};逆波兰表达式求值逆波兰表达式也称后缀表达式它的运算符优先级已经排好了思路1.运算数入栈2.遇到运算符取栈顶两个数据运算运算结果继续入栈先取到的值是右操作数注意1.这里遍历string时for(auto e:str)中auto要加如果不加 即 for (auto e :str)则每个字符都会被拷贝到循环变量 e 中。虽然拷贝一个 char 开销很小但对于长字符串或频繁遍历累积的拷贝仍有一定成本。使用 auto 直接绑定到原字符串中的字符无需拷贝效率更高。2.tokens 是 vector即字符串向量它的每个元素是 string 类型一个完整的 token例如 “2”、“”、“3”。因此for(auto str : tokens)中的 str 是 string 类型的引用代表一个字符串而不是单个字符。后面使用 str[0] 是取这个字符串的第一个字符用于 switch 判断运算符3.在 C 中switch 语句的 case 标签后面必须跟着整数常量表达式。但这里的 ‘’、‘-’ 等字符字面量属于整数常量因为字符类型 char 是整型的一种每个字符都对应一个整数值例如 ASCII 码。所以 case ‘’ 是合法的编译器会将 ‘’ 转换为它的 ASCII 码43进行比较。换句话说switch (str[0]) 拿到的是字符串的第一个字符比如 ‘’ 对应的整数 43而 case ‘’ 也是整数 43两者匹配。这种写法很常见比直接写数字 case 43 更直观。classSolution{public:intevalRPN(vectorstringtokens){stackintst;for(autostr:tokens){if(str||-str||*str||/str){//运算符intrightst.top();st.pop();intleftst.top();st.pop();switch(str[0]){case:st.push(leftright);break;case-:st.push(left-right);break;case*:st.push(left*right);break;case/:// 题目说明了不存在除数为0的情况st.push(left/right);break;}}else{st.push(stoi(str));}}returnst.top();}};用两个栈实现队列classMyQueue{public:MyQueue(){}voidpush(intx){instack.push(x);}//返回删除元素intpop(){if(outstack.empty())in2out();intxoutstack.top();outstack.pop();returnx;}intpeek(){if(outstack.empty())in2out();returnoutstack.top();}//取队列的队首boolempty(){returninstack.empty()outstack.empty();}private:stackintinstack;stackintoutstack;voidin2out(){while(!instack.empty()){outstack.push(instack.top());instack.pop();}}};