stack/queue---入门OJ题

20. 有效的括号 - 力扣（LeetCode）

大致的思路就是便利字符串，左括号入栈，遇到右括号就出栈顶元素与之判断匹配，匹配成功就继续往后走，匹配失败就直接return false，跳出循环之后额外判断一下如果栈为空则说明全部匹配成功，如果栈里还有括号就说明没有全部匹配成功。

class Solution { public: bool isValid(string s) { stack<char> 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: queue<int> q1; queue<int> 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: stack<int> stpush; stack<int> 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: stack<int> st; stack<int> minst; };

栈的压入、弹出序列_牛客题霸_牛客网

模拟题。定义两个指针pushi和popi分别指向入栈序列和出栈序列，

class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param pushV int整型vector * @param popV int整型vector * @return bool布尔型 */ bool IsPopOrder(vector<int>& pushV, vector<int>& popV) { // write code here stack<int> 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)*4+5，后缀表达式就是运算符按优先级排列且挨着要运算的运算数。1+(2-3)*4+5转后缀就为123-4*+5+。本题直接给了我们一个后缀表达式让我们计算，利用栈来解决，便利字符串，便利到操作数就入栈，便利到操作符就出栈两个数字，来配合操作符运算后再入栈，以此往复。

class Solution { public: int evalRPN(vector<string>& tokens) { stack<int> 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(); } };