stack/queue---入门OJ题

20. 有效的括号 - 力扣LeetCode大致的思路就是便利字符串左括号入栈遇到右括号就出栈顶元素与之判断匹配匹配成功就继续往后走匹配失败就直接return false跳出循环之后额外判断一下如果栈为空则说明全部匹配成功如果栈里还有括号就说明没有全部匹配成功。class Solution { public: bool isValid(string s) { stackchar st; for(int i 0;i s.size();i) { if(s[i] ( || s[i] { || s[i] [) { st.push(s[i]); } else { //有可能s里只有右括号 if(!st.empty()) { char tp st.top(); st.pop(); if(tp ( s[i] ! ) || tp { s[i] ! } || tp [ s[i] ! ]) { return false; } } else { return false; } } } if(!st.empty()) { return false; } return true; } };225. 用队列实现栈 - 力扣LeetCode按照下图的逻辑去解决问题就可以了唯一要注意的就是取栈顶元素的时候不能像出栈那样先将size-1个数据挪到另一个队列再去取栈顶元素因为这样的话下一次入栈就不知道该往哪个队列里去入数据了。class MyStack { public: MyStack() {} void push(int x) { if(!q1.empty()) { q1.push(x); } else { q2.push(x); } } int pop() { if(!q1.empty()) { int sz q1.size(); --sz; while(sz--) { q2.push(q1.front()); q1.pop(); } int x q1.front(); q1.pop(); return x; } else { int sz q2.size(); --sz; while(sz--) { q1.push(q2.front()); q2.pop(); } int x q2.front(); q2.pop(); return x; } } int top() { if(!q1.empty()) { return q1.back(); } else { return q2.back(); } } bool empty() { return q1.empty() q2.empty(); } private: queueint q1; queueint q2; };232. 用栈实现队列 - 力扣LeetCode一个栈用来出数据一个用来入数据。class MyQueue { public: MyQueue() {} void push(int x) { stpush.push(x); } int pop() { if(stpop.empty()) { while(!stpush.empty()) { stpop.push(stpush.top()); stpush.pop(); } } int x stpop.top(); stpop.pop(); return x; } int peek() { if(stpop.empty()) { while(!stpush.empty()) { stpop.push(stpush.top()); stpush.pop(); } } return stpop.top(); } bool empty() { return stpush.empty() stpop.empty(); } private: stackint stpush; stackint stpop; };155. 最小栈 - 力扣LeetCode本题的重点是获取栈中的最小元素。下边的pop函数为什么只要判断minst的栈顶就可以了不用考虑minst里其他元素跟st将要删除的元素一样吗不用minst里存的是当前栈里最小的数据比minst.top()大的不会进minst里比minst.top()小的就应该就是minst.top()呀所以不可能出现上述情况。class MinStack { public: MinStack() {} void push(int value) { st.push(value); if(minst.empty() || value minst.top()) { minst.push(value); } } void pop() { if(st.top() minst.top()) minst.pop(); int x st.top(); st.pop(); } int top() { return st.top(); } int getMin() { return minst.top(); } private: stackint st; stackint minst; };栈的压入、弹出序列_牛客题霸_牛客网模拟题。定义两个指针pushi和popi分别指向入栈序列和出栈序列class Solution { public: /** * 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可 * * * param pushV int整型vector * param popV int整型vector * return bool布尔型 */ bool IsPopOrder(vectorint pushV, vectorint popV) { // write code here stackint st; int pushi 0, popi 0; while(pushi pushV.size()) { st.push(pushV[pushi]); while(!st.empty() st.top() popV[popi]) { popi; st.pop(); } pushi; } if(st.empty()) return true; else return false; } };150. 逆波兰表达式求值 - 力扣LeetCode平时我们写的都叫做中缀表达式就比如1(2-3)*45后缀表达式就是运算符按优先级排列且挨着要运算的运算数。1(2-3)*45转后缀就为123-4*5。本题直接给了我们一个后缀表达式让我们计算利用栈来解决便利字符串便利到操作数就入栈便利到操作符就出栈两个数字来配合操作符运算后再入栈以此往复。class Solution { public: int evalRPN(vectorstring tokens) { stackint st; for(auto s : tokens) { // 判断是否是运算符 //由于tokens里的是字符串所以无法判断数字字符串 if(s || s - || s * || s /) { int x st.top(); st.pop(); int y st.top(); st.pop(); int res 0; if(s ) res y x; else if(s -) res y - x; else if(s *) res y * x; else res y / x; st.push(res); } else { // 不是运算符转为数字入栈支持负数-123 st.push(stoi(s)); } } return st.top(); } };