20 有效的括号
class Solution {
public:
bool isValid(string s) {
stack<char> stk;
for (auto c : s)
{
if (c == '(' || c == '{' || c == '[') stk.push(c);
else {
if (stk.size() && abs(c - stk.top()) <= 2) stk.pop();
else return false;
}
}
return stk.empty();
}
};
225 用队列实现栈
队列：进[ ] 出
栈：[ ]进出
用先进先出的逻辑实现后进先出的逻辑
队列1： 进[5 4 3 2 1]出
队列2： 进[4 3 2 1]出
如果不弹出5的话就是 [4 3 2 1 5]
队列1：用来推数据。队列2：用来备份数据，缓存
注意：完成之后要保持队列1中数据原有的顺序
class MyStack {
public:
queue<int> p, q;
MyStack() {
}
void push(int x) {
p.push(x);
}
int pop() {
while (p.size() > 1) q.push(p.front()), p.pop();
int t = p.front();
p.pop();
while (q.size()) p.push(q.front()), q.pop();
return t;
}
int top() {
while (p.size() > 1) q.push(p.front()), p.pop();
int t = p.front();
p.pop();
q.push(t);
while (q.size()) p.push(q.front()), q.pop();
return t;
}
bool empty() {
return p.empty();
}
};
232 用栈实现队列
用先进后出的逻辑实现先进先出的逻辑
[1 2 3 4 5] 进出 进出[2 3 4 5]
栈1：用来操作数据。栈2：用来备份
class MyQueue {
public:
stack<int> a, b;
MyQueue() {
}
void push(int x) {
a.push(x);
}
int pop() {
while (a.size() > 1) b.push(a.top()), a.pop();
int t = a.top();
a.pop();
while (b.size()) a.push(b.top()), b.pop();
return t;
}
int peek() {
while (a.size() > 1) b.push(a.top()), a.pop();
int t = a.top();
while (b.size()) a.push(b.top()), b.pop();
return t;
}
bool empty() {
return a.empty();
}
};
150 逆波兰表达式
是后缀表达式，不需要考虑括号和优先级
不断地遍历，将字符加到栈里面，如果遇到一个操作符的话就把栈顶的两个元素用这个操作符操作一下然后放到栈里，最后栈顶元素就是最终的结果。
注意：取整和下取整只对于负数的不同
-1.2：下取整：-2，取整-1
C++中的除法就是取整
注意：先弹出的是b，后弹出的是a
class Solution {
public:
stack<int> stk;
int evalRPN(vector<string>& tokens) {
for (auto c : tokens)
{
if (c == "+" || c == "-" || c == "*" || c == "/")
{
auto b = stk.top(); stk.pop();
auto a = stk.top(); stk.pop();
if (c == "+") a += b;
else if (c == "-") a -= b;
else if (c == "*") a *= b;
else a /= b;
stk.push(a);
}
else // 注意：要加上
{
stk.push(stoi(c));
}
}
return stk.top();
}
};
