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

文章目录

  • 1.栈与队列的理论基础
  • 2.232用栈实现队列
    • 2.1.题目
    • 2.2.解答
  • 3.225用队列实现栈
    • 3.1.题目
    • 3.2.解答
      • 3.2.1.使用两个队列
      • 3.2.2.使用一个队列
  • 4.20有效的括号
    • 4.1.题目
    • 4.2.解答
  • 5.1047删除字符串中的所有相邻重复项
    • 5.1.题目
    • 5.2.解答

1.栈与队列的理论基础

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

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

2.232用栈实现队列

参考:代码随想录,232.用栈实现队列

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_;
};

3.225用队列实现栈

参考:代码随想录,225用队列实现栈

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_;
};

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;
    }

4.20有效的括号

参考:代码随想录,20.有效的括号

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();
    }
};

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

参考:代码随想录,1047. 删除字符串中的所有相邻重复项

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;
    }
};
Copyright © 2010-2022 mfbz.cn 版权所有 |关于我们| 联系方式|豫ICP备15888888号