LeetCode-栈和队列专题

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]出
如果不d出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++中的除法就是取整
注意：先d出的是b，后d出的是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();
    }
};