代码随想录11——栈与队列：理论基础、232.用栈实现队列、225.用队列实现栈、20.有效的括号、1047. 删除字符串中的所有相邻重复项

1.栈与队列的理论基础

参考：代码随想录，栈与队列的理论基础

这个部分内容是比较简单的，但是自己之前从来没用过stl容器中的栈，队列倒是用过但是很少，所以还是要仔细去看看的。

2.232用栈实现队列

参考：代码随想录，232.用栈实现队列； 力扣232: easy

2.1.题目

2.2.解答

这个其实是比较简单的，其中两个栈入栈和出栈的时候的动图如下，看上面代码随想录的讲解，非常好！

class MyQueue
{
public:
    MyQueue()
    {
    }

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

    int pop()
    {
        if(stack_out_.empty())
        {
            // 如果出栈是空，则把入栈中的所有元素都拷贝到出栈中
            while(!stack_in_.empty())
            {
                int num = stack_in_.top();
                stack_in_.pop();
                stack_out_.push(num);
            }
        }
        // 至此stack_out_中肯定有元素了（不管是原来就有，还是原来是空，然后把入栈中的拷贝过来）
        int res = stack_out_.top();
        stack_out_.pop();
        return res;
    }

    int peek()
    {
        int res = this->pop();
        stack_out_.push(res);
        return res;
    }

    bool empty()
    {
        // 如果入栈出站都是空，则队列就是空
        if(stack_out_.empty() && stack_in_.empty())
            return true;

        return false;
    }

private:
    stack<int> stack_in_;
    stack<int> stack_out_;
};
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
42
43
44
45
46
47
48
49
50

3.225用队列实现栈

参考：代码随想录，225用队列实现栈；力扣225: easy

3.1.题目

3.2.解答

3.2.1.使用两个队列

这个还是用两个队列来实现一个栈，但是和前面使用两个栈实现一个队列的原理是不同的。这里是用另一个队列存储要弹出的元素之前的所有元素，然后把当前的元素从队列中弹出，然后再把另一个队列中的元素拷贝回来。动画如下所示，非常简单：

class MyStack
{
public:
    MyStack()
    {
    }

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

    int pop()
    {
        int size = q1_.size();
        size--;
        // 把q1的前面(size-1)个元素都弹出，然后存到q2中
        while(size--)
        {
            q2_.push(q1_.front());
            q1_.pop();
        }
        // 把q1中的最后一个元素弹出，就是目标值
        int res = q1_.front();
        q1_.pop();

        // 再把弹出后的剩余的所有袁术，即q2中的元素存回q1
        q1_ = q2_;

        // 最后把q2清空，留给下次备用
        while(!q2_.empty())
            q2_.pop();
        return res;
    }

    int top()
    {
        // 栈顶的元素，就是队列尾的元素
        return q1_.back();
    }

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

private:
    queue<int> q1_;
    queue<int> q2_;
};
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
42
43
44
45
46
47
48
49
50

3.2.2.使用一个队列

这种方法就是使用一个队列，每次把前面的size-1个元素弹出来，然后再重新加到队列的末尾，这样操作后队列的前面就是要弹出的元素了，更加简单，而且更容易理解。

int pop()
    {
        int size = q1_.size();
        size--;
        while(size--)
        {
            q1_.push(q1_.front());
            q1_.pop();
        }
        int res = q1_.front();
        q1_.pop();
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

4.20有效的括号

参考：代码随想录，20.有效的括号；力扣20: easy

4.1.题目

4.2.解答

由于栈结构的特殊性，非常适合做对称匹配类的题目。

注意题目已经确定了输入的字符串中的字符一定是(){}[]的6个中的一个。所以只需要一边遍历整个字符数组，一遍判断：

• 比如如果遍历的字符是左边的字符({[中的一个，那么就往栈中存储它对应的右边的字符)}]。
• 然后如果这个字符串是对称的话，那么遍历到整个字符串的右半边的时候，也就是字符是)}]的时候，就从栈中弹出对应的元素。
• 如果遍历到最后，栈中是空的，那么就说明这个字符串是对称的。否则有三种不对称的情况：
  （1）遍历到最后栈中不是空，说明原来的字符串中左边的字符个数多了，不是对称的
  （2）遍历过程中，字符串还没遍历完毕，栈就空了。说明右边的字符太多了，左边没有那么多和它匹配的，因此不对称
  （3）遍历过程中，当前的右边的字符和栈中栈顶的右边字符不匹配，说明这就是字符上不对称，因此最终字符串也是不对称的。

三种不对称的情况，见下图：

class Solution
{
public:
    bool isValid(string s)
    {
        stack<char> right;
        for(auto& ss : s)
        {
            // 左边字符的情况
            if(ss == '(')
                right.push(')');
            else if(ss == '{')
                right.push('}');
            else if(ss == '[')
                right.push(']');

            // 右边字符的情况
            // 1.stack为空，说明右边字符太多了
            else if(right.empty())
                return false;
            // 2.stack栈顶的元素不等于当前元素，说明就是字符不对称
            else if(right.top() != ss)
                return false;
            // 正常情况：弹出栈顶元素，遍历下一个元素
            else   
                right.pop();
        }

        // 3.stack有剩余元素，说明左边字符太多了。如果遍历完了stack也是空，说明就是对称的字符串
        return right.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

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

参考：代码随想录，1047. 删除字符串中的所有相邻重复项；力扣1047: easy

5.1.题目

5.2.解答

我们在删除相邻重复项的时候，其实就是要知道当前遍历的这个元素，我们在前一位是不是遍历过一样数值的元素，那么如何记录前面遍历过的元素呢？

就是用栈来存放，那么栈的目的，就是存放遍历过的元素，当遍历当前的这个元素的时候，去栈里看一下我们是不是遍历过相同数值的相邻元素。然后再去做对应的消除操作。

如动画所示：

从栈中弹出剩余元素，此时是字符串ac，因为从栈里弹出的元素是倒序的，所以在对字符串进行反转一下，就得到了最终的结果。

class Solution
{
public:
    string removeDuplicates(string s)
    {
        stack<char> have;
        for(auto& ss : s)
        {
            // 如果栈是空的，或者当前字符不等于栈顶字符，那么就加入
            if(have.empty() || ss != have.top())
                have.push(ss);
            // 否则当前字符 == 栈顶字符，就要把栈顶字符弹出
            else   
                have.pop();
        }

        // 到这里，栈中剩下的元素就是最后删除了重复元素之后的结果
        string res = "";
        while(!have.empty())
        {
            res += have.top();
            have.pop();
        }
        // 还要把字符串反转一下， 才是最终结果
        reverse(res.begin(), res.end());
        return res;
    }
};
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