【刷题篇】栈和队列

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

【刷题篇】栈和队列

目录

一.前言🌈

二.有效的括号✨

a.题目

b.题解分析

c.AC代码 

三. 用队列实现栈📏

a.题目

b.题解分析(辅助队列法)

c.AC代码(辅助队列法)

d.题解分析(就地存储法)

c.AC代码(就地存储法)

四. 用栈实现队列🍀

a.题目

b.题解分析

c.AC代码


一.前言🌈

        各位小友们好久不见,甚是想念!前段时间我们学习了两个重要的数据结构---栈和队列。那么我们的刷题篇也就该提上日程了,本期将带来三道与栈和队列有关的OJ题,它们分别是:

🚀本期的题目有: 有效的括号用队列实现栈用栈实现队列

注:为了实现方便,本期我们将使用C++来编写代码,利用STL中现有的栈和队列进行实现。

二.有效的括号✨

a.题目

【刷题篇】栈和队列

b.题解分析

        我们知道,在我们编写的C程序中,会存在着小括号( )、中括号[ ]以及大括号{ },它们总是成对出现且匹配的,满足这个特点的一组括号我们就称它有效。例如{ ( ) [ ] }就是一组匹配的括号,而{ ( [ ) } ] 就不是一组匹配的括号。我们可以发现一个现象,从左往右开始第一个右括号 其前一个括号 必须是与之对应的左括号,否则这组括号就不匹配

【刷题篇】栈和队列

        而如果本对括号匹配,我们就可以将本对括号移除,进行下一对括号的判断,直到所有括号都成功匹配,说明本组括号是有效的。如果在这个过程中出现一次不匹配,那就说明本组括号无效。 

【刷题篇】栈和队列

【刷题篇】栈和队列

有了以上思路,那究竟要选择什么合适的数据结构来存放我们的括号呢? 

我们自然而然的会想到,因为无论是判断是否匹配,移除匹配的括号,我们都只是在其中一端进行操作的。


    当我们的指针遇到左括号的时候,我们进行入栈操作。当遇到右括号时,我们就和栈顶的左括号进行比较,如果匹配,则pop出栈,移除匹配的括号;如果不匹配,则直接返回false。依次反复直到遍历完整个字符串。

  c.AC代码 

class Solution {
    //存放括号的栈
    stack<char> sta;
public:
	bool isValid(string s)
	{
        //遍历字符串
		for (int i = 0; i < s.size(); i++)
		{
			char c = s.at(i);
			switch (c)
			{
			case '(':
			case '[':
			case '{':
				sta.push(c);//左括号入栈
				break;
			case ')':
            case ']':
            case '}':
                if(sta.empty()) //括号栈为空,匹配失败
                {
                    return false;
                }
				if ((c==')' && sta.top() != '(')||
                    (c==']' && sta.top() != '[')||
                    (c=='}' && sta.top() != '{'))
				{
					return false; //匹配失败
				}
				else
				{
					sta.pop();//成功,将匹配成功的左括号出栈
				}
				break;
			default:
				//cout << "输入的字符串有误" << endl;
				return false;
				break;
			}
		}
        //遍历完毕,判断括号栈中还有没有剩余的括号
		if (sta.empty())//为空
		{
			return true;
		}
		else//不为空,说明左括号多了,匹配失败
		{
			return false;
		}
	}

};

三. 用队列实现栈📏

a.题目

【刷题篇】栈和队列

b.题解分析(辅助队列法)

        本题要求我们用队列来模拟栈。由于队列的特性是先进先出,栈的特性是后进先出,因此我们需要模拟的栈的栈顶实际上是队尾,我们需要在队尾进行一系列操作。特别是出栈,要先将队列前面的元素全部出队后才能执行。

【刷题篇】栈和队列

显然前面的元素我们不能直接无视,在它们出队的同时我们要将他们存放起来,以供下次使用。那么我们要怎样存储呢?这里有两个方案:辅助空间存储就地存储


我们先来看看辅助空间存储,我们可以再使用一个辅助的队列来存放队尾前面的元素,由于队列先进先出的特性,每个元素的顺序都将保持一致。当我们进行入栈时就入到不为空的队列进行出栈时将不为空的队列的前n-1个元素移到为空的队列中,然后将剩下的一个元素pop掉。动态演示如下:

【刷题篇】栈和队列

c.AC代码(辅助队列法)

class MyStack {
    queue<int> q1;
    queue<int> q2;
public:
    MyStack() {

    }
    //入栈
    void push(int x) 
    {
        //从不为空的队列放入数据
        if (!q1.empty())
        {
            q1.push(x);
        }
        else
        {
            q2.push(x);
        }

    }
    //出栈
    int pop() 
    {
        if (q1.empty())
        {
            swap(q1, q2);
        }
        //将前几个元素转移到为空的队列中
        while (q1.size() > 1)
        {
            q2.push(q1.front());
            q1.pop();
        }
        int ret = q1.front();
        q1.pop(); //移除栈顶元素
        return ret;
    }
    //求栈顶元素
    int top() 
    {
        //栈顶所在位置即为队尾,直接访问即可
        if(!q1.empty())
        {
            return q1.back();
        }
        else
        {
            return q2.back();
        }
    }
    //判空
    bool empty() 
    {
        //两个队列都为空说明栈为空
        return q1.empty() && q2.empty();
    }
};

d.题解分析(就地存储法)

     上面我们采用了一个辅助队列来进行解题,实际上我们也可以只使用一个队列出栈的时候只需将前n-1个元素同时出队并再次入队,此时队头元素即为我们的栈顶元素,我们再将其pop,这样依然可以保证原有顺序不变。动态演示如下:

【刷题篇】栈和队列

c.AC代码(就地存储法)

class MyStack {
    queue<int> q1;
public:
    MyStack() {

    }
    //入栈
    void push(int x) 
    {
        //放入数据,入队
        q1.push(x);
    }
    //出栈
    int pop() 
    {
        //记录当前共有几个元素
        int count=q1.size();
        //将前面count-1个元素出队并入队
        while(count > 1)
        {
            int val=q1.front();
            q1.pop();
            q1.push(val);
            count--;
        }

        //将此时的队头,即栈顶元素出队
        int ret=q1.front();
        q1.pop();
        return ret;
    }
    //求栈顶元素
    int top() 
    {
        //栈顶元素就是队尾元素
        return q1.back();
    }
    //判空
    bool empty() 
    {
        //队列为空说明栈为空
        return q1.empty();
    }
};

四. 用栈实现队列🍀

a.题目

【刷题篇】栈和队列

b.题解分析

    本题和上一题基本上一样,区别就是我们这次模拟的是队列。由于队列是先进先出栈是后进先出,因此我们在模拟出队时依旧要将前n个元素先进行出栈。

【刷题篇】栈和队列

 那么,我们要怎样将移除的前n-1个元素存放起来呢,可以就地存储吗?


答案是不行的。由于栈是先进先出,出栈和入栈是在同一端进行的,出栈的同时入栈相当于啥也没做。因此我们只能再使用一个栈进行辅助。

【刷题篇】栈和队列

我们可以设计两个栈,一个栈存储入队的元素(input)另一个栈用于出队(output)。当进行入队操作时,则往input入栈;当进行出队操作时,如果ouput为空,则先将input中的元素压入output中,此时output的栈顶元素恰好就是队头元素,然后出栈即可,如果不为空,则直接出栈。动态演示如下:

【刷题篇】栈和队列

c.AC代码

class MyQueue {
    stack<int> input;
    stack<int> output;
public:
    MyQueue() {

    }
    //入队
    void push(int x)
    {
        //往input入栈
        input.push(x);
    }
    //出队
    int pop()
    {
        //output为空,先将input数据移入
        if (output.empty())
        {
            while (!input.empty())
            {
                int val = input.top();
                input.pop();
                output.push(val);
            }
        }
        //此时output栈顶元素即为队头元素,出栈
        int ret = output.top();
        output.pop();
        return ret;
    }
    //求队头元素
    int peek()
    {
        //output为空,先将input数据移入
        if (output.empty())
        {
            while (!input.empty())
            {
                int val = input.top();
                input.pop();
                output.push(val);
            }
        }
        //栈顶元素即为队头元素
        int ret = output.top();
        return ret;
    }
    //判空
    bool empty()
    {
        //两个栈都为空说明队列为空
        return input.empty() && output.empty();
    }
};

以上,就是本期的全部内容啦🌸

制作不易,能否点个赞再走呢🙏文章来源地址https://www.toymoban.com/news/detail-433831.html

到了这里,关于【刷题篇】栈和队列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【刷题篇】贪心算法

    假设1元、2元、5元、10元、20元、50元、100元的纸币分别由c0,c1,c2,c3,c4,c5,c6张。现在要用这些钱来支付K元,至少要用多少张纸币?

    2024年02月09日
    浏览(37)
  • 【刷题篇】链表(下)

    各位读者们好,本期我们来填填之前留下的坑,继续来讲解几道和链表相关的OJ题。但和上期单向链表不一样的是,我们今天的题目主要是于环形链表有关,下面让我们一起看看吧。 💻本期的题目有: 环形链表 、 环形链表II 、 求环形链表环长 a.题目 b.题解分析 第一种方法

    2024年01月25日
    浏览(43)
  • 蓝桥杯刷题篇①

    前言:hello各位童学们好呀!许久不见!本文为本人的蓝桥杯OJ的刷题笔记!文章隶属于专栏蓝桥杯,该专栏的目的是为了记录自己的刷题记录和学习过程,激励自己不断前行,为明年的ACM、ICPC、蓝桥杯等比赛做足准备,也希望可以帮助到一些同样在刷题道路上的小伙伴们!

    2024年02月09日
    浏览(51)
  • 【刷题篇】链表(上)

    前段时间我们学习了单向链表和双向链表,本期将带来3道与链表相关的OJ题来巩固对链表的理解。话不多说,让我们进入今天的题目吧! 🚀本期的题目有: 反转单链表 、 链表的中间结点 、 合并两个有序链表 a.题目 b.题解分析(迭代) 🍡 三指针法: 我们可以直接在原链表的

    2024年02月02日
    浏览(56)
  • 【刷题篇】抽牌获胜的概率

    谷歌面试题 将面值1-N的牌组成一组 每次从组中等概率的抽出1-N中的一张 下次抽会换一个新的组,有无限组 当抽到的牌累加和a时,将一直抽牌 当累加和=a且b时,你将获胜 当累加和=b时,你将失败 给定的参数N,a,b 返回获胜的概率 核心思想 优化递归函数中的for循环, 因为计算

    2024年02月06日
    浏览(39)
  • 力扣刷题篇之《空白替换》

    ❤️ 铁汁们大家好,欢迎大家来到出小月的博客里,今天小月呢写了一道题目叫替换空格,但是呢,写完之后调试了半天不知道哪里错了,经过小月的坚持不懈,终于成功,来分享给大家小月的错误,希望大家看完我这篇文章都能够“涨芝士”,感觉小月写的还不错的话,记

    2023年04月26日
    浏览(84)
  • 【C语言】字符串---刷题篇

    Hi,C站的小伙伴们大家好呀!😊🥰,欢迎来阅读我的这一篇 【C语言】字符串基础刷题篇! 不知你是否和我一样,在刚刚接触到这块的知识时,总是会和这神圣的知识隔着隔着厚厚的一堵墙,迷茫的眼神中总是会露出不理解不理解😣😣(当时的状态……) 其实后来我就发现其实

    2024年02月03日
    浏览(44)
  • 【蓝桥杯-刷题篇】基础知识运用

    🍓系列专栏:蓝桥杯 🍉个人主页:个人主页 目录 1.查找两个总和为特定值的索引 2.寻找 3 个数的最大乘积 3.字符统计 4.用杂志拼接信件 5.小蓝吃糖果 6.含 2 天数 7.完全日期 8.星期几 9.图书推荐 题目链接:查找两个总和为特定值的索引 - 蓝桥云课 (lanqiao.cn) 题目描述 给定一个数

    2023年04月09日
    浏览(38)
  • [C语言刷题篇]链表运用讲解

    目录 NC25 删除有序链表中重复的元素-I 描述 方法一:遍历删除(推荐使用) 方法二:递归求解 反转链表 描述 解法:迭代 给大家推荐一款神器牛客网以下题型及方法牛客都有,及企业面试高频题   删除给出链表中的重复元素(链表中元素从小到大有序),使链表中的所有元

    2024年02月16日
    浏览(40)
  • 【Java刷题篇】串联所有单词的子串

    力扣链接: 串联所有单词的子串 阅读题目后,可以拿到一个关键信息– words中所有字符串长度相等 ,这后续解题思路的一大关键,还有就是串联字串的字符串顺序可以不同。得到这两个关键信息后,我们就很容易联想到运用 滑动窗口 这个算法来解决问题。 好分析完题目后,

    2024年03月22日
    浏览(43)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包