day10 栈与队列1

232.用栈实现队列

#include <stack>
using namespace std;

class MyQueue {
public:
    stack<int> stIn;
    stack<int> stOut;
    MyQueue() {

    }
    
    void push(int x) {
        stIn.push(x);
    }
    
    int pop() {
        if (stOut.empty()) {
            while (!stIn.empty()) {
                stOut.push(stIn.top());
                stIn.pop();
            }
        }
        int res = stOut.top();
        stOut.pop();
        return res;
    }
    
    int peek() {
        int res = this->pop();
        stOut.push(res);
        return res;
    }
    
    bool empty() {
        return stIn.empty() && stOut.empty();
    }
};

225. 用队列实现栈

class MyStack {
public:
    queue<int> q1;
    queue<int> q2;
    //q1->q2
    MyStack() {

    }
    
    void push(int x) {
        q1.push(x);
    }
    
    int pop() {
        int size = q1.size() - 1;
        while (size --) {
            q2.push(q1.front());
            q1.pop();
            
        }
        int res = q1.front();
        q1 = q2;
        clear(q2);
        return res;
    }
    
    int top() {
        int size = q1.size();
        int res;
        while (size --) {
            res = q1.front();
            q2.push(res);
            q1.pop();
        }
        q1 = q2;
        clear(q2);
        return res;
    }

    void clear(queue<int> &q) {
        while (!q.empty()) {
            q.pop();
        }
    }

    bool empty() {
        return q1.empty() && q2.empty();
    }
};

用一个队列也行，pop了再加回队尾就行，优化版：

class MyStack {
public:
    queue<int> q;
    MyStack() {
        //deque 先进先出
        //模拟stack 后进先出
    }
    
    void push(int x) {
        q.push(x);
    }
    
    int pop() {
        int size = q.size() - 1;
        while (size --) {
            q.push(q.front());
            q.pop();
        }
        int res = q.front();
        q.pop();
        return res;
    }
    
    int top() {
        int res = this->pop();
        q.push(res);
        return res;
    }

    bool empty() {
        return q.empty();
    }
};

20. 有效的括号

class Solution {
public:
    bool isValid(string s) {
        if (s.size() % 2 == 1) {
            return false;
        }
        stack<char> st;
        unordered_map<char, char> umap{{')', '('}, {']', '['}, {'}', '{'}};
        for (char ch: s) {
            if (ch == '(' || ch == '[' || ch == '{') {
                st.push(ch);
            }
            else {
                if (st.empty()) {
                    return false;
                }
                if (st.top() == umap[ch]) {
                    st.pop();
                }
                else {
                    st.push(ch);
                }
            }
        }
        return st.empty();
    }
};

1047. 删除字符串中的所有相邻重复项

class Solution {
public:
    string removeDuplicates(string s) {
        string res;
        for (char ch: s) {
            if (res.empty() || res.back() != ch) {
                res.push_back(ch);
                continue;
            }
            res.pop_back();
        }
        return res;
    }
};