232.用栈实现队列

LeetCode题目

注意事项

• 无

class MyQueue {
public:
    stack<int> stk1, stk2;
    MyQueue() {}

    void push(int x) { stk1.push(x); }

    int pop() {
        while (!stk1.empty()) {
            stk2.push(stk1.top());
            stk1.pop();
        }
        int result = stk2.top();
        stk2.pop();
        while (!stk2.empty()) {
            stk1.push(stk2.top());
            stk2.pop();
        }
        return result;
    }

    int peek() {
        while (!stk1.empty()) {
            stk2.push(stk1.top());
            stk1.pop();
        }
        int result = stk2.top();
        while (!stk2.empty()) {
            stk1.push(stk2.top());
            stk2.pop();
        }
        return result;
    }

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

225. 用队列实现栈

LeetCode题目

注意事项

• 队列和栈不同的一点是栈在从一个转移到另一个的时候顺序会反向，而队列则会保持一致；因此需要本体需要多考虑一步，即pop和peak的区别

class MyStack {
public:
    deque<int> que1, que2;

    MyStack() {}

    void push(int x) { que1.push_back(x); }

    int pop() {
        int x = que1.front();
        que1.pop_front();
        while (!que1.empty()) {
            que2.push_back(x);
            x = que1.front();
            que1.pop_front();
        }
        while (!que2.empty()) {
            que1.push_back(que2.front());
            que2.pop_front();
        }
        return x;
    }

    int top() {
        int x;
        while (!que1.empty()) {
            x = que1.front();
            que2.push_back(x);
            que1.pop_front();
        }
        while (!que2.empty()) {
            que1.push_back(que2.front());
            que2.pop_front();
        }
        return x;
    }

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

20. 有效的括号

LeetCode题目

注意事项

• 要考虑的特殊情况很多：
  1.栈为空来左边的情况
  2.栈为空来右边的情况
  3.最后不为空的情况

class Solution {
public:
    bool isValid(string s) {
        stack<char> collect;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(' || s[i] == '{' || s[i] == '[')
                collect.push(s[i]);
            else if (collect.empty())
                return false;
            else {
                if (collect.top() == '(' && s[i] == ')')
                    collect.pop();
                else if (collect.top() == '{' && s[i] == '}')
                    collect.pop();
                else if (collect.top() == '[' && s[i] == ']')
                    collect.pop();
                else
                    return false;
            }
        }
        if (collect.empty())
            return true;
        else
            return false;
    }
};

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

LeetCode题目

注意事项

• 可以使用string来作为队列和栈，但是当打印的时候顺序和栈是相反的

class Solution {
public:
    string removeDuplicates(string s) {
        string collect;
        for (int i = 0; i < s.size(); i++) {
            if (collect.empty())
                collect.push_back(s[i]);
            else if (collect.back() == s[i])
                collect.pop_back();
            else
                collect.push_back(s[i]);
        }
        return collect;
    }
};