【C++】STL——stack OJ练习

这篇具有很好参考价值的文章主要介绍了【C++】STL——stack OJ练习。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


这篇文章我们来做几道stack相关的OJ题,练习一下stack的使用。

1. 最小栈

先来看第一道题——:最小栈

【C++】STL——stack OJ练习

题目要求我们设计一个MinStack 类:
【C++】STL——stack OJ练习
除了提供常见的几个接口之外,还要搞一个int getMin(),使得我们能够在常数时间O(1)内获取到栈中最小的元素。

思路分析

那要怎么做呢?

大家想这样行不行:
我们定义一个变量min来保存最小值,向栈里面入第一个元素时,就让min等于第一个元素,后续入栈新元素时,就和min比较判断是否需要更新min,小于就更新,大于就不动。
最终min的值就是最小元素。
听起来好像可以,但是:
别忘了,元素可以入栈,也可以出栈啊
【C++】STL——stack OJ练习
比如现在栈里面入了这样几个元素,现在min的值更新为1,确实是当前栈中所有元素的最小值。
但是如果我们进行了pop呢?
如果先把8pop掉了:
【C++】STL——stack OJ练习
此时min的值还是1没问题,那继续pop呢?
【C++】STL——stack OJ练习
1也被pop掉了,那min还能等于1 吗?
所以这样不行。

那我们提供这样一种思路:

我们这样做:
实现的MinStack 类里有两个成员:
【C++】STL——stack OJ练习
st就是我们正常定义的要使用的栈,min_st是一个辅助栈,用来帮助我们获取最小值。

那对于这两个栈,我们怎么操作呢?

举个栗子:
当第一个元素入栈的时候,比如入了一个5,那我们让两个栈都push一个5:
【C++】STL——stack OJ练习
那此时栈中的最小值就是5。
然后再入一个4,最小值要更新,那min_stst都push一个4(其实就是保证min_st栈顶的元素一定是最小值,最终我们就可以直接获取):
【C++】STL——stack OJ练习
然后如果再入一个6,那最小值不需要更新:
【C++】STL——stack OJ练习
那min_st要push入元素吗?
🆗,可以入也可以不入,但入得话一定不入6,因为入6的话栈顶元素就不是最小值了,所以如果选择入的话再入一个4:
【C++】STL——stack OJ练习
那这样min_st栈顶的元素还是最小的。
再入的话一样的操作:
【C++】STL——stack OJ练习

那我们在这里选择不入:

那就是这样:
【C++】STL——stack OJ练习
当入栈的新元素小于等于min_st.top()(或第一次min_st为空)时 min_st才入栈这个元素。

那pop的时候怎么处理?

🆗,是不是pop的元素等于当前栈中的最小值即min_st.top()min_st才进行pop,否则min_st就不pop。

AC代码

我们来写一下代码:
【C++】STL——stack OJ练习

这是题目的初始代码模板。

首先问大家一个问题:

【C++】STL——stack OJ练习
这是我们的成员变量嘛。
我们看到题目给的代码模板里面给了构造函数的接口:
【C++】STL——stack OJ练习
但是,对于我们这种方法,还需要些构造函数吗?
其实是不是根本都不需要构造函数啊,因为我们不写编译器默认生成,默认生成的构造函数什么特性:
编译器自动生成的构造函数不会对内置类型成员进行处理,而对于我们这里的stack(自定义类型)会怎么处理?
是不是会去调用stack对应的默认构造函数。

所以这里完全不需要构造函数,另外对于什么拷贝构造、赋值重载是不是一样啊。
但是呢这里给了构造函数的接口,那编译器就不会默认生成了,那如果我们对于这个构造函数啥也不写,就留在这里,会不会出问题?
🆗,是不是也没问题啊,因为它会走初始化列表,对于自定义类型也会去调它的默认构造

那剩下的接口就很好实现了,我们上面已经分析过了,这里就直接上代码了:

class MinStack {
public:
    // 不需要处理走初始化列表就可以搞定,
    // 直接删掉也可以,因为默认生成的就可以搞定
    MinStack() {
    }
    
    void push(int val) {
        st.push(val);
        if(min_st.empty()||val<=min_st.top())
            min_st.push(val);
    }
    
    void pop() {
        if(st.top()==min_st.top())
            min_st.pop();
        st.pop();
    }
    
    int top() {
        return st.top();
    }
    
    int getMin() {
        return min_st.top();
    }
private:
    stack<int> st;
    stack<int> min_st;

};

【C++】STL——stack OJ练习

可以给大家看一下,直接删掉构造也可以:

【C++】STL——stack OJ练习

拓展思维

现在给大家一个问题,还是上面那道题目:

【C++】STL——stack OJ练习
如果是这种情况,那st有多少元素,minst也得有多少元素。
那能不能想个办法优化一下呢?
🆗,我们可以考虑这样做:
我们的minst里面呢不在存最小值,而去存它的值和个数
【C++】STL——stack OJ练习
这样需要minst进行pop的话,把对应的个数- -就行了,怎么存个数呢,可以定义一个结构体:
【C++】STL——stack OJ练习
那这样如果重复值比较多的话,可以节省一点空间。
就是这样一个思路,那代码我就不写了,大家有兴趣可以尝试写一下。

2. 栈的压入、弹出序列

链接: link
【C++】STL——stack OJ练习

这道题其实就是给我们一个入栈序列,和一个出栈序列,让我们判断该出栈序列是否是可行的。

思路讲解

那怎么判断呢?

🆗,这道题比较简单的一种方法其实就是去模拟这个入栈出栈的过程。
举个栗子,就看题目给的这个测试用例:
【C++】STL——stack OJ练习
入栈序列是1 2 3 4 5,出栈顺序是4 3 5 1 2。
那我们就模拟这个过程去判断啊:
首先上来第一步肯定先入一个数据,根据入栈序列第一个入栈的是1,那1入完之后有没有可能直接出栈啊,当然是有可能的,不过我们要看对应的出栈序列,那我们看到第一个出栈的应该是4,所以怎么办?
【C++】STL——stack OJ练习
我们需要继续入栈数据,接着入栈2 3 4。
【C++】STL——stack OJ练习
这是栈顶的元素和出栈序列第一个元素相等,所以出栈,4,3都顺利的出了
【C++】STL——stack OJ练习
下一个要出栈的是5,但是5还没入栈,所以让5入栈,然后5直接出栈
【C++】STL——stack OJ练习
然后现在栈里只剩1 2了,但是出栈序列是1 2,这显然不能办到,所以应该返回false最终栈不为空)
【C++】STL——stack OJ练习
当然如果是4 3 5 2 1,这样最终2 1也能顺利出栈,那就应该是true最终栈为空)

AC代码

那对应的代码怎么写呢,我们来一起写一下:

【C++】STL——stack OJ练习
给了我们两个vector,存储入栈pushV和出栈popV的序列。
那我们要模拟入栈出栈的过程,所以我们定义一个栈
【C++】STL——stack OJ练习
然后我们要根据入栈序列去push数据,根据出栈序列去pop数据,所以我们要去遍历两个vector。【C++】STL——stack OJ练习
从下标0开始。
首先上来第一步肯定先入一个数据:
【C++】STL——stack OJ练习
然后pushi++,下一次入第二个数据。
那第一个元素入了之后我们就要判断它是否需要出栈了,怎么判断?
如果当前入栈的元素等于popV[popi],是不是就要出栈。
但是每次出栈是不是有可能连续出多个元素啊,所以这应该是一个循环:

【C++】STL——stack OJ练习
但是,我们这里上来直接获取栈顶元素去判断st.top()==popV[popi],如果栈空了再去st.top()是不是就出问题了啊,所以,循环结束的条件是不相等或者栈出空了
【C++】STL——stack OJ练习
内层while循环结束之后如果后面还有元素未入栈,那就继续入栈,继续判断,当外层while循环结束是不是所有数据都判断完了啊。
那此时如果栈为空是不是就表明出栈序列是匹配的,全部出完了,如果不为空,就证明不匹配:
【C++】STL——stack OJ练习
就写完了。

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        stack<int> st;
        int pushi=0;
        int popi=0;
        while(pushi<pushV.size())
        {
            st.push(pushV[pushi++]);
            while(!st.empty()&&st.top()==popV[popi])
            {
                st.pop();
                popi++;
            }
        }
        return st.empty();
    }
};

【C++】STL——stack OJ练习

3. 逆波兰表达式求值

链接: link
【C++】STL——stack OJ练习

这道题目叫做逆波兰表达式求值,那什么是逆波兰表达式呢
我们可以一起来了解一下:
【C++】STL——stack OJ练习
结合题目中给的测试用例给大家解释一下:
【C++】STL——stack OJ练习
我们正常写的表达式,就比如题目中的这个:(2 + 1) * 3
这种写法叫做中缀算术表达式,即运算符写在操作数的中间,但是这种写法计算机是不能直接计算的,因为涉及运算符优先级的问题,比如1+2*3,应该先算*
所以呢,这里就需要我们做一件事情,就是把它变成后缀表达式,其实就是根据优先级对表达式中的运算符排一个序,并且放到对应的操作数后面。
就比如题目中给的这个示例:((2 + 1) * 3)这个表达式对应的后缀表达式就是["2","1","+","3","*"](题中是把它放到一个字符串数组中了)。
即1和2先进行后面的+,得到的结果再和3进行后面的*,得到最终结果。这样就直接从前往后算,不用考虑优先级的问题了。

那现在大家对逆波兰表达式应该有一个大致的了解了。

思路讲解

但是呢,单要解这道题目的话,其实很好搞:

我们只需要借助一个栈就搞定了。
具体怎么做呢?
我们去遍历给的逆波兰表达式对应的字符串数组,如果对应的元素是数字,我们就让该操作数入栈,如果遇到操作符,我们就去取栈顶的前两个元素(并pop掉)进行对应的运算,然后将结果入栈,后续重复上述操作,最终栈里面唯一的那个元素就是要求的结果。
举个栗子:
【C++】STL——stack OJ练习
遍历tokens,2 1入栈,接着遇到+,取出 1 2相加,得到结果3入栈,后面又是一个3入栈,接着遇到* ,取出3 3相乘,结果9入栈。
最终栈里面唯一的元素9就是结果。

AC代码

【C++】STL——stack OJ练习

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for(auto& str:tokens)
        {
            if(str=="+"||str=="-"||str=="*"||str=="/")
            {
                int right=st.top();
                st.pop();
                int left=st.top();
                st.pop();
                switch(str[0])
                {
                    case '+':
                        st.push(left+right);
                        break;
                    case '-':
                        st.push(left-right);
                        break;
                    case '*':
                        st.push(left*right);
                        break;
                    case '/':
                        st.push(left/right);
                        break;
                }
            }
            else
            {
                st.push(stoi(str));
            }
        }
        return st.top();
    }
};

【C++】STL——stack OJ练习

拓展:中缀表达式如何转后缀

那现在大家再来思考一个问题:
如果给我们一个中缀表达式,我们如何把它转换成对应的后缀表达式

中缀转后缀呢,也是需要借助一个栈,具体怎么做呢?
比如现在有这样一个中缀表达式1+2*3-4
怎么把它转成后缀呢?
🆗,我们还是从头去遍历这个表达式,如果遇到的是操作数,就输出
【C++】STL——stack OJ练习
如果遇到的是的是操作符,那这时要分情况进行分析:
如果此时栈为空,就让该操作符进栈;

【C++】STL——stack OJ练习
【C++】STL——stack OJ练习
如果遇到的是操作符,且此时栈不为空,则取栈顶的操作符与当前操作符比较,比较啥呢——优先级:
如果比栈顶操作符优先级高,就让该操作符进栈,为什么是进栈而不是拿它进行运算呢?
因为后面有可能还有优先级更高的,所以先进栈。

【C++】STL——stack OJ练习
那进栈之后呢?继续取下一个进行判断是操作数还是操作符。
【C++】STL——stack OJ练习
如果比栈顶操作符优先级低或者相等,则出栈顶的操作符输出(即此时栈顶的这个操作符可以进行运算了)
【C++】STL——stack OJ练习
然后再去判断栈是否为空,不为空再拿当前操作符和栈顶操作符比较,进行相应操作,为空就入栈。
【C++】STL——stack OJ练习
【C++】STL——stack OJ练习
【C++】STL——stack OJ练习
遍历结束后,如果栈不为空,将剩余操作符输出。
【C++】STL——stack OJ练习
此时,就得到对应的后缀表达式了。
【C++】STL——stack OJ练习

但是,如果是带括号的情况呢?

比如1+2*(4-5)+6/7,怎么处理?
🆗,那如果按照上面的分析,1输出,+入栈,2输出,*的优先级比栈顶的+高,*也入栈,接着遇到了括号,怎么办?
【C++】STL——stack OJ练习
如果不加括号的话,后面-比*优先级低,那应该让*先出栈运算,但是现在-在括号里面,所以-应该先运算,所以要认为-的优先级更高。
那我们可以怎么处理呢?当然这里的方法可能不止一种,我们可以这样做:
遇到(,我们认为它的优先级很低,但是我们不拿(做比较,直接让它入栈
【C++】STL——stack OJ练习
然后遇到括号里的-,栈不为空,比较,因为我们说了认为(的优先级很低,所以-也入栈
【C++】STL——stack OJ练习
那继续往后走遇到)怎么办?
🆗,)呢我们也认为它的优先级很低,但是)我们要拿它去比较,因为我们认为)优先级很低,所以此时栈顶的-是不是就被成功弹出了。
【C++】STL——stack OJ练习
然后栈不为空继续跟栈顶比,那此时) 就遇到 (了,拿这时怎么做呢?
这时直接把(pop掉,不输出,然后跳过) 继续看下一个,因为后缀表达式优先级都排好了就不需要括号了。

【C++】STL——stack OJ练习
拿继续往后走遇到+,栈不为空,跟栈顶比,比栈顶优先级低,栈顶操作符*输出,继续栈还不为空,继续比,优先级相等,出栈顶操作符+
【C++】STL——stack OJ练习
然后栈空了,+入栈
【C++】STL——stack OJ练习
然后遇到6入栈,遇到/优先级比+高,入栈,然后7输出
【C++】STL——stack OJ练习
就遍历完了,再把剩余操作符输出
【C++】STL——stack OJ练习
就得出结果后缀表达式了,大家可以验证一下。

【C++】STL——stack OJ练习
当然处理括号可能有很多种方法,我们这里提供的只是其中一种,而且我们这种方法如果遇到有些极端的情况可能也不一定处理的了,可能还需要加一些特殊处理。
另外我们会发现就是遇到(是不是好像去开了一个新栈,在这个新栈里去处理括号里的这个子表达式,所以如果这样的问题也可以考虑递归去搞,每次遇到(就递归去处理这个子表达式,处理完回去递归调用的地方继续处理后面的。

这个问题大家了解一下。
【C++】STL——stack OJ练习文章来源地址https://www.toymoban.com/news/detail-467704.html

到了这里,关于【C++】STL——stack OJ练习的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • [ C++ ] STL---stack与queue

    目录 stack简介 stack的常用接口 queue简介 queue的常用接口 stack的模拟实现 queue的模拟实现 1. stack是具有后进先出操作的一种容器适配器 ,其只能从容器的一端进行元素的插入与删除操作 ; 2. stack是作为容器适配器被实现的,容器适配器即是对特定类封装作为其底层的容器,并

    2024年03月28日
    浏览(42)
  • C++ STL--->stack和queue

    stack文档 stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行 元素的插入与提取操作。 stack是作为容器适配器被实现的,容器适配器即是对特定类封装作为其底层的容器,并提供一组特定 的成员函数来访问其元素,将特定类作为

    2024年01月16日
    浏览(46)
  • 【c++】STL之stack和queue详解

    作者简介:დ旧言~,目前大二,现在学习Java,c,c++,Python等 座右铭:松树千年终是朽,槿花一日自为荣。 目标:掌握stack和queue库,了解deque库 毒鸡汤:小时候,哭是我们解决问题的绝招,长大后,笑是我们面对现实的武器。 望小伙伴们点赞👍收藏✨加关注哟💕💕  今天

    2024年02月19日
    浏览(41)
  • 【C++】学习STL中的stack和queue

            今天这篇博客的内容主要关于STL中的stack、queue和priority_queue三种容器。         stack和queue的使用方式非常简单,我们只要根据之前学习数据结构的经验和文档介绍就可以轻松上手。于是我们直接开始对它们的模拟实现。         stack和queue我们在数据结构阶段就曾经

    2024年02月10日
    浏览(42)
  • C++基础(13)——STL(stack、queue、list)

    本文主要介绍C++中STL中的stack、queue和list容器 栈中只有顶端元素才可以被外界调用,因此栈不允许有遍历的行为,其中string、vector、deque都可以遍历 队列中队头出数据,队尾进数据,且和栈一样不允许有遍历操作 queue容器装入自定义数据类型数据 链表由一系列的结点组成,结

    2024年02月10日
    浏览(40)
  • 【C++】STL——stack和queue使用及模拟实现

    🚀 作者简介:一名在后端领域学习,并渴望能够学有所成的追梦人。 🚁 个人主页:不 良 🔥 系列专栏:🛸C++  🛹Linux 📕 学习格言:博观而约取,厚积而薄发 🌹 欢迎进来的小伙伴,如果小伙伴们在学习的过程中,发现有需要纠正的地方,烦请指正,希望能够与诸君一同

    2024年02月13日
    浏览(50)
  • 【C++ • STL • 力扣】详解string相关OJ

    ヾ(๑╹◡╹)ノ\\\" 人总要为过去的懒惰而付出代价 ヾ(๑╹◡╹)ノ\\\" 力扣链接 代码1展示 :【下标】 代码2展示 :【迭代器】 思路 :快速排序中的单趟排序 知识点 :C++库提供了swap的函数,可以直接调用。 力扣链接 代码展示 : 思路 :计数排序的思想 牛客链接 代码展示 :

    2024年02月09日
    浏览(44)
  • C++:OJ练习(每日练习系列)

    把字符串转换成整数_牛客题霸_牛客网 示例1 输入: 返回值: 思路一: 第一步: it从str的第一个字符开始遍历,定义一个最后输出的值你,以及判断结果正负的flag; 第二步:第一个为正则忽略,为负将flag改为负值; 第三步: 遍历字符串,遇到非字母直接退出,否则记录下

    2024年02月05日
    浏览(32)
  • C++:OJ练习(每日练习系列)

    415. 字符串相加 - 力扣(LeetCode) 思路一: 第一步: 需要 获取字符串的两个尾节点下标 ; 第二步: 创建用于 记录进位数、获得的字符串的变量 ; 第三步: 只要 有进位或还有数没有加完继续循环 : 利用三目运算:有符号+符号,无符号+0 ; 第四步: 最后将得到的 字符串

    2024年02月05日
    浏览(30)
  • [C++] STL_stack && queue接口的模拟实现

    stack的文档介绍 1. stack是一种容器适配器,专门用在具有 后进先出 操作的上下文环境中,其删除只能从容器的一端进行元素的插入与提取操作。 2. stack是作为容器适配器被实现的,容器适配器即是对特定类封装作为其底层的容器,并提供一组特定的成员函数来访问其元素,将

    2024年02月05日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包