【栈和队列刷题】 有效的括号、删除字符串中的所有相邻重复项、用栈实现队列、用队列实现栈

LeetCode20. 有效的括号

来源：力扣（LeetCode）
链接：link
思路：使用一个栈，遍历字符串。如果栈为空就直接将字符加入。如果不为空，判断字符是左字符还是右字符。如果是左字符，直接加入；如果是右字符，判断与栈顶字符是否匹配，若不匹配，直接返回false，若匹配则移除栈顶。循环直到字符串遍历完毕。最后如果栈为空，说明括号有效。

class Solution {
public:
    bool isValid(string s) {
        stack<char> sk;
        if (s.size() % 2 != 0) return false; // 如果s的长度为奇数，一定不符合要求
        for(int i = 0; i < s.size(); i++){
            if(s[i] == '(' || s[i] == '{' || s[i] == '[') sk.push(s[i]);
            else{
                if(!sk.empty() && ((sk.top() == '(' && s[i] == ')') ||
                    (sk.top() == '{' && s[i] == '}') ||
                    (sk.top() == '[' && s[i] == ']'))) sk.pop();
                else return false;
            }
        }
        if(sk.empty()) return true;
        else return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

来源：力扣（LeetCode）
链接：link
思路：借助栈，遍历字符串。如果栈顶字符和当前字符一致，直接pop；否则入栈。

class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> sk;
        string result;
        for(auto e : s){
            if(sk.empty() || sk.top() != e) sk.push(e);
            else sk.pop();
        }
        while(!sk.empty()){
            result += sk.top();
            sk.pop();
        }
        reverse(result.begin(), result.end());
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

LeetCode232.用栈实现队列

来源：力扣（LeetCode）
链接：link
思路：使用栈来模拟队列的行为，如果仅仅用一个栈，是一定不行的，所以需要两个栈一个输入栈，一个输出栈，这里要注意输入栈和输出栈的关系。

class MyQueue {
public:
    stack<int> instack, outstack;
    MyQueue() {}
    
    void push(int x) {
        instack.push(x);
    }
    
    int pop() {
        if(outstack.empty()){
            while(!instack.empty()){
                outstack.push(instack.top());
                instack.pop();
            }
        }
        int res = outstack.top();
        outstack.pop();
        return res;
    }
    
    int peek() {
        int res = pop();
        outstack.push(res);
        return res;
    }
    
    bool empty() {
        return instack.empty() && outstack.empty();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

LeetCode225. 用队列实现栈

来源：力扣（LeetCode）
链接：link
思路：队列是先进先出的规则，把一个队列中的数据导入另一个队列中，数据的顺序并没有变，并没有变成先进后出的顺序。所以用栈实现队列， 和用队列实现栈的思路还是不一样的，这取决于这两个数据结构的性质。但是依然还是要用两个队列来模拟栈，只不过没有输入和输出的关系，而是另一个队列完全用又来备份的！

class MyStack {
public:
    queue<int> inqueue, outqueue;
    //int size;
    MyStack() {
        //size = 0;
    }
    
    void push(int x) {
        inqueue.push(x);
        //size++;
    }
    
    int pop() {
        int size = inqueue.size();
        size--;
        while(size--){
            outqueue.push(inqueue.front());
            inqueue.pop();
        }
        int res = inqueue.front();
        inqueue.pop();
        while(!outqueue.empty()){
            inqueue.push(outqueue.front());
            outqueue.pop();
        }
        
        return res;
    }
    
    int top() {
        //int res = pop();
        //inqueue.push(res);
        //return res;
        return inqueue.back();
    }
    
    bool empty() {
        return inqueue.empty();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41