wordpress快站平台,建设网站的流程图,深圳网站建设 工作室,建设装饰网站引言#xff1a;
北京时间#xff1a;2023/3/17/7:18#xff0c;刚刚快乐的早锻炼回来#xff08;不对 #xff0c;应该说回来有一会了#xff09;#xff0c;因为此时我已经吃完早饭#xff0c;洗过澡了#xff1b;现在回想起上学期#xff0c;就算是第二天需要晨跑…引言
北京时间2023/3/17/7:18刚刚快乐的早锻炼回来不对 应该说回来有一会了因为此时我已经吃完早饭洗过澡了现在回想起上学期就算是第二天需要晨跑6点起床但我依然毫不畏惧博客没写完或者视屏没看完我都会硬刚有时到凌晨2-3点但大部分时间都是硬刚都1点左右然后写完博客顺带会发个朋友圈哈哈哈浏览量然后快乐的去睡觉 然后就算6点起床也不怎么当回事但是这样是不好滴长逗严重所以当时我对这个早锻炼活动可以说是万般的厌恶认为这种活动结束后大家不都是直接回到宿舍然后继续睡吗这不是影响我们的作息吗有什么意义呢但是现在我发现我的看法改变了猜我现在在干嘛你答对了我现在在码字哈哈哈所以现在的我再也不熬夜了每天准时在时间范围内睡觉早起虽然依旧难受但是活动完之后我发现我多了一个早上的时间7点-10点进行码字只是把写博客、看视屏的时间给调整了一下而已主要不长逗开心虽然此时我觉得这个活动还是那么不聪明的样子但是起码不厌恶了所以我明白了一个道理可能以前明白过可能只是没有那么深就是当我们无法改变环境的时候我们只能去适应环境通过体验调整出一个更适合自己生存的环境俗话说的好识时务者为俊杰所以适应环境真的非常重要不要逆天改命哦小伙伴们OK充分意识到引言写太长了但是没关系管他那么多呢上天安排的最大嘛曾经有一份真诚的爱情放在我面前我没有珍惜等我失去的时候才后悔莫及人世间最痛苦的事莫过于此。 如果上天能够给我一个再来一次的机会我会对那个女孩子说三个字我爱你哦不不不紫霞完蛋电视看太多了也可能是星爷的电视太过于经典导致一涉及就容易无法自拔哈哈哈OK真的不能搞笑了这篇博客的引言真的已经要不属于引言的范畴了爱怎么写怎么写略略略今天我们就继上篇博客中栈和队列的知识来聊一聊栈和队列的经典适配器双端队列deque和有关优先级队列priority queue的知识当然重点还有一个叫仿函数的东西哦STL六大巨头之一可不是泛泛之辈尔等岂敢小瞧目标明确Here we go Here we go 看到这句我总是会联想到有些美剧中的经典枪战场景不置可否
上篇博客我们学习了STL中的两个容器适配器栈和队列并且发现栈和队列的学习成本不高数据结构和string、vector、list因为我们已经了解了很多有关知识所以轻轻松松就把栈和队列的知识给搞定了并且我们解决了两个经典的有关栈的题目获取最小栈和栈的弹出发现有的题目就是为栈这个数据结构设计的使用栈来解决这种问题非常的合适所以接下来我们再来看两个有关栈的经典题目。
1.计算逆波兰表达式 题目逆波兰表达式 例我们平时算加减乘除时把 12*3-4叫做是中缀表达式但是中缀表达式并不可以通过栈的方式入栈出栈实现4则运算所以需要把中缀表达式给转化成后缀表达式例1 2 3 * 4 -后缀表达式这样就可以很好的利用栈的输入输出来实现四则远算了但此时我们先不探讨如何将一个后缀表达式转换成中缀表达式我们先探讨一下如何使用栈的方式来计算一个后缀表达式逆波兰表达式 解题思路
遇到操作数就入栈 1 2 3 4 5遇到操作符 - * /就取栈顶和栈顶后一个两个操作数进行运算运算结果重新入栈最后栈中的数据就是我们的结果切记此时是使用后缀表达式逆波兰表达式进行的运算不存在运算符优先级问题
注意加和乘由于运算关系不改变所以没事但是减和除会出问题所以在出数据的时候要把栈顶数据放到运算符的右边栈顶后一个数据放到左边
代码实现如下
#includeiostream
#includevector
#includestring
#includequeue
#includestack
using namespace std;class Solution
{
public:int evalRPN(vectorstring tokens){stackint st;for (auto str : tokens){if (str || str - || str * || str /){int right st.top();st.pop();int left st.top();st.pop();switch (str[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(str));}}return st.top();}
};代码细节注意点 因为题目给给我们的是一个后缀表达式以字符串的形式并且因为switch case语句中的case只能针对于整形数据char属于整形一簇强转所以我们在遍历字符串中的字符数据时此时就不可以直接用switch接收所以只能使用if语句进行判断并且由于减和除运算符的特性所以要区别左操作数和有操作数使用stoi函数(string类)可以直接将一个字符类型的数据转换为整形数据不要把case语句中的break给漏掉了case和break是需要匹配使用的作用就是类似于else if语句 2.中缀表达式转后缀表达式题目
搞定了上述的这个题目此时我们就来看一下这个题目的前提就是如何把一个中缀表达式转换成后缀表达式当然前提还是在使用栈通过栈来判断各个运算符的优先级进而构成后缀表达式 例将中缀1 2 * 3 - 4转换成后缀1 2 3 * 4 - 原理 a. 如果是操作数就直接存储到字符串数组中string b. 如果是操作符入栈但是要分成两种情况
栈为空入栈栈不为空重点让这个操作符去和栈顶的操作符进行比较如果这个操作符的优先级高就将该操作符入栈不进行运算的原因是防止还有优先级更高的操作符但是如果这个操作符的优先级低或者相等那么此时就要把栈顶的操作符出栈然后进行运算原因该操作符优先级比上一个栈顶中的操作符高比下一个操作符的优先级也高那么此时它就是三个操作符中优先级最高的那么此时出栈对该运算符进行运算并且此时栈顶的运算符得到运算之后该优先级低的操作符需要和下一个操作符继续比较递归实现同理高就入栈低就出栈顶然后继续递归比较
代码实现如下
#includeiostream
#includevector
#includestring
#includequeue
#includestack
using namespace std;bool IsPra(char c)
{return (c ( || c )) ? true : false;
}
int GetPriority(char c)
{switch (c) {case :case -:return 0; break;case *:case /:return 1; break;case (:case ):return -1; break;default:cout 输入其他运算符\n endl;}
}
void CheckPriority(char c, stackchar operator_s, string suffix)
{if (operator_s.empty()) {operator_s.push(c);return;}if (IsPra(c)) {if (c () {operator_s.push(c);}else {// 弹出所有元素直到遇到左括号while (operator_s.top() ! (){suffix operator_s.top();operator_s.pop();}// 遇到左括号弹出且不加入后缀表达式operator_s.pop();}}else {// 如果不是括号比较当前元素与栈顶元素的优先级if (GetPriority(c) GetPriority(operator_s.top())){operator_s.push(c);}else {suffix operator_s.top();operator_s.pop();//递归方式循环比较check(c, operator_s, suffix);}}
}
string InfixToSuffix(string infix)
{stackchar operator_s; // 运算符栈string suffix; // 后缀表达式for (int i 0; i infix.size(); i) {if (infix[i] 0 infix[i] 9){suffix infix[i];}else {CheckPriority(infix[i], operator_s, suffix);}}// 对中缀表达式的遍历结束将栈中元素加入后缀表达式while (!operator_s.empty()) {suffix operator_s.top();operator_s.pop();}return suffix;
}如上代码分为四个函数实现
第一个函数bool IsPra(char c) 判断中缀表达式中是否有括号第二个函数int GetPriority(char c)固定运算符的优先级第三个函数void CheckPriority(char c, stackchar operator_s, string suffix) 对运算符的优先级进行判断代码核心实现也就是进行数据的比较第四个函数string InfixToSuffix(string infix) 合并操作数和操作符栈中已经排好序了此时就得到了我们想要的后缀表达式可以直接通过栈实现计算的后缀表达式。
并且注意
此时解决括号问题的方法有非常的多如上述代码使用的将左括号和右括号的优先级都设置成最低并且在入栈时不需要进行比较特殊处理直接入栈然后同理将括号之间的操作符进行比较最终当右括号(“)”)遇到左括号(“(”)时将左括号弹出删除栈顶元素继续同理往下走
但是这里也可以使用别的方法例如使用一个flag0如果遇到括号让flag1然后在flag1的前提下遇到的下一个运算符的优先级就是最高的无论加减等一系列的方法都可以只要你控制得住 所以我们的思路是 ()优先级最低 ( 特殊处理不比较直接入栈 ) 参与比较直到遇到左括号弹出左括号 总: 中缀转后缀利用栈的目的就是进行运算符的优先级的比较遍历运算字符串然后通过栈比较出运算符的优先级然后通过入栈和出栈进行操作数和操作符的运算所以栈的用处在这些题目方面是非常的适用的我们应该合理使用栈的特性先进后出。
浅谈双端队列deque
搞定了上述的题目栈和队列的知识也就告一段落了 并且在上篇博客中我们说过栈和队列是使用一个叫deque的容器适配器实现的所以此时我们就来看一看什么是deque首先无论是在以前的迷宫题目还是vector题目我们都学习过类似二维数组的结构或者说是vectorvectorint的结构所以在此类型结构之下我们来学学deque的结构 (listvector) 显然是与我刚刚所说的两个结构类似如下图 如上图可以看出我们是使用了一个指针数组来存放很多的小数组的地址这样我们就可以通过控制指针数组中指针指向的地址的空间来控制小数组中的数据了并且发现如果存储的数据量非常大需要扩容此时就不再需要像vector一样开辟一个扩容之后的空间然后把原来空间的数据拷贝最后将原空间释放掉目的防止数据量太大太小此时按照上图的结构就可以直接对指针数组进行扩容开辟更多的指针出来消耗对于内置类型来说降低了整数倍但是对于自定义类型来说就是降低了n倍例vectorvectorint类型的数据进行扩容
所以此时我们就来谈谈上述结构的优点和缺点deque首先在学习其优缺点之前我们先来复习一下vector和list的优缺点 vector的缺点 1.频繁扩容消耗高 2. 头插头删效率很低 vector的优点 1.使用下标支持随机访问 2.CPU的高速缓存效率高涉及硬件知识原因地址连续 list的缺点不支持随机访问 list的优点任意位置插入删除效率高 复习了vector和list的优缺点之后我们就来看一看它们的结合体deque的优缺点
优点如果使用vector和list实现了deque的话此时deque的优点是相比vector扩容的代价低只需要扩容指针就行指针指向的数组固定头插头删尾插尾删效率都很高删除头指针指向的数组中的第一个数据就行并且也支持随机访问例每一个指针数组中的指针指向的是一个100个数据的vector数组那么此时就以 /100为找行 %100位找列此时就找到下标位置了表示第几个指针数组中的指针中的第几个下标
缺点不支持中间插入删除如果支持中间插入删除缺点就是不支持随机访问 并且如果要支持中间插入和删除的话那么此时它的效率是比vector高但是比list低功能方面不够极致没有vector的随机访问也没有list的插入删除数据的效率
所以综上可以发现deque的优缺点导致它不怎么适合直接用于存储数据而是适合做一些容器适配器的适配器例栈和队列的适配器这也就是为什么栈和队列的适配器是deque
deque的迭代器
搞定了上述的知识我们来看一下deque这个聚集了list和vector优点于一身的家伙它的迭代器是怎样实现的吧如下图 从上图可以看出deque的迭代器是比较复杂的使用了4个原生指针这里各个指针的作用不多做讲解感兴趣的同学点击该链接deque迭代器指针的作用
此时了解了双端队列deque和deque的迭代器下篇博客我们就学习自我实现好吧
什么是优先级队列
搞定了双端队列的基本结构和优缺点此时我们再来学习一下另一个队列优先级队列如下图 从图中可以发现优先级队列建的是一个大堆所以如果我们想要建一个小堆的话此时就可以引入一个叫仿函数的概念也就是STL的六巨头之一greaterint具体是什么东西我们在之后的学习中在深入了解。
浅谈仿函数
templateclass T
struct Less//仿函数
{bool operator()(const T x, const T y){return x y;}
};
templateclass T
struct greater//仿函数
{bool operator()(const T x, const T y){return x y;}
};int main()
{Lessint lessFunction;//此时就是让Less这个类的对象可以像是一个函数一样具有很多的功能本质上是去调用了各种的运算符重载或者是嵌套的函数cout lessFunction(1, 2) endl;//此时这句代码的本质是去调用运算符重载但是看起来像是去调用了一个函数return 0;
}上述的代码就是仿函数greater和less的实现方式本质上是通过我们的运算符重载实现具体的功能这里不深入学习了解即可 总结STL中还有很多的东西需要我们学习无论是迭代器还是仿函数还是map、set容器还是空间配置器内存池任务艰巨
