10.栈和队列

LeetCode.232.栈实现队列

class MyQueue {

private:
    stack<int> inStack, outStack;

    void in2out(){
        while(!inStack.empty()){
            outStack.push(inStack.top());
            inStack.pop();
        }
    }

public:
    MyQueue() {

    }
    
    void push(int x) {
        inStack.push(x);
    }
    
    int pop() {
        if(outStack.empty()){
            in2out();
        }
        int o = outStack.top();
        outStack.pop();
        return o;
    }
    
    int peek() {
        if(outStack.empty()){
            in2out();
        }
        return outStack.top();
    }
    
    bool empty() {
        return inStack.empty() && outStack.empty();
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

LeetCode.225.队列实现栈

class MyStack {
private:
    queue<int> inQue, outQue;

public:
    MyStack() {

    }
    
    void push(int x) {
        outQue.push(x);
        while(!inQue.empty()){
            outQue.push(inQue.front());
            inQue.pop();
        }
        swap(inQue, outQue);
    }
    
    int pop() {
        int r = inQue.front();
        inQue.pop();
        return r;
    }
    
    int top() {
        return inQue.front();
    }
    
    bool empty() {
        return inQue.empty();
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

LeetCode.20.有效的括号

// 注意特殊判断
// stack中无法匹配的情况
class Solution {
public:
    bool isValid(string s) {
        unordered_map<char, char> pairs = {
            {')', '('},
            {']', '['},
            {'}', '{'}
        };
        stack<char> q;
        for(int i = 0; i < s.size();i++){
            if(s[i] == '(' || s[i] == '{' || s[i] == '['){
                q.push(s[i]);
            }else{
                if(!q.empty()){
                    char t = q.top();
                    q.pop();
                    if(t != pairs[s[i]]) {
                        return false;
                    }
                }else {
                    return false;
                }
            }
        }
        return q.empty();
    }
};

[LeetCode.1047.删除字符串中所有相邻重复项]

// 最后反转
class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> q;
        for(int i = 0;i < s.size();i++){
            if(q.empty()){
                q.push(s[i]);
            }else{
                char t = q.top();
                if(s[i] == t){
                    q.pop();
                }else{
                    q.push(s[i]);
                }
            }
        }
        string anss;
        while(!q.empty()){
            anss += q.top();
            q.pop();
        }
        reverse(anss.begin(),anss.end());
        return anss;
    }
};

LeetCode.150.逆波兰表达式

// atoi()接受一个 char *[]
// c_str()返回一个 char *[]
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        int n1,n2;
        stack<int> s;
        for(int i = 0;i < tokens.size();i++){
            string c = tokens[i];
            if(isNum(c)){
                s.push(atoi(c.c_str()));
            }else{
                n2 = s.top();s.pop();
                n1 = s.top();s.pop();
                switch(c[0]){
                    case '+':
                        s.push(n1+n2);
                        break;
                    case '-':
                        s.push(n1-n2);
                        break;
                    case '*':
                        s.push(n1*n2);
                        break;
                    case '/':
                        s.push(n1/n2);
                        break;
                    default:
                }
            }
        }
        return s.top();
    }

    int isNum(string c){
        return !(c == "+" || c == "-" || c == "*" || c == "/");
    }
};