0基础学算法 第三弹 队列

    接触过一点oi的应该都知道,在初赛试题中,总会考一些关于栈,队列,类的知识,而因为队列或栈需要额外的头文件,所以有的同学就不知道这方面的内容,然而这个队列(栈)也是一个非常常用的一个技巧类的东西,你要是会有可能就比别人抢到先机,那么,今天我就教大家抢夺先机。在抢夺先机之前,可不可以先关注我呢,关注我可以持续为你带来多样的算法知识😁

首先我们学队列的话,要先搞清楚他的运行方式,因为他很容易和栈搞混,他和栈的区别就在于,队列是先进先出,栈是先进后出,跟大家解释一下吧,在队列中(或栈)是没有下标的,不像数组里可以定点打击,把对应下标的值取出来,他们只能按照顺序一个一个取,放当然也是顺序放入,给大家看一个图就知道什么意思了

这样就很清晰了,大致了解他工作过程后我们就可以开始看代码了

今天我们主要是讲队列,栈会在以后讲,如果你期待讲栈的话,记得关注我

一,定义一个队列

    队列和string一样是需要额外的头文件,也和他一样是个数据类型,如果你要使用队列,你需要先添加头文件queue,然后再在程序中定义队列,定义方法为queue<数据类型> 队列名; 然后你就可以通过队列名来调用队列了。

二,队列的溢出

    如果还有新元素进行入队列容易造成假溢出。

    假溢出:顺序队列因多次入队列和出队列操作后出现的尚有存储空间但是不能进行入队操作的溢出。

    真溢出:顺序队列的最大存储空间已经存满而又要求进行入队列操作所引起的溢出。    

    事实上你基本不用担心溢出的情况,首先是因为溢出情况并不多见,更重要的是如果你一直想着怎么防止溢出,会阻断你的思考

三,队列的基本操作

    队列在经定义后,就可以进行一些基本操作了,基本操作包括入队,出队,判断是否为空队列,检测有多少元素在其中,当然还有提取队列顶部和底部的元素的操作,给大家综合看一下代码的效果吧

#include<queue>
using namespace std;
int main(){
    queue<int> q;
    q.empty();              //如果队列为空返回true,否则返回false  
    q.size();              //返回队列中元素的个数  
    q.pop();                 //删除队列首元素但不返回其值  
    q.front();               //返回队首元素的值,但不删除该元素  
    q.push();                //在队尾压入新元素  
    q.back();               // 返回队列尾元素的值,但不删除该元素  
    return 0;
}

上面我是定义了一个q,并集合了他的常用的操作,但没有进行输出,当中的队首指的是第一个入队的,队尾是最后一个入队的,上面定义的队列是整型的,你也可以定义长整型,字符型等等,而q.xxx指对队列q调用函数xxx,别忘了在后面打括号,大致熟悉了一下队列的基本操作后就去实战一下吧

洛谷实战题讲解     

          P1996https://www.luogu.com.cn/problem/P1996请独立完成不要看题解,如果不会就继续看我讲解

    我希望你是这的思考过的,不一定要想出来,但是请一定自己尝试一番,不管你会也好,不会也罢,你都继续看这篇博文就对了。

    这道题应该是非常经典的,大家应该不仅在新人时期做过这题,之前数学课也有讲过吧,约瑟夫问题的做法很多样可以用数组做,或者模拟他的过程,但今天这道题,我要告诉你们,可以用队列做!在做之前,确保你打开了约瑟夫问题,手上有笔纸,并编译器没有bug,确定之后,我们就开始吧。

    这道题也是我新人时期做的题,首先,要输入m和n两个数,n决定了一圈有多少人,m决定了数几个数出去一人,那么肯定是要有计数的变量来不断的数人出去啊,然后我们可以通过队列将数到的人弹出去,好了,我们可以先用第一弹讲过的流程图来梳理一下

现在,思路已经很清晰了,那么我们就来代码实现吧

#include <iostream>
#include <queue> 
using namespace std;
int main()
{
    queue<int>q;
    int n,m,s=1;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        q.push(i); 
    }
    while(!q.empty())
    {
        if (s==m)
        {
            cout<<q.front()<<" ";
            q.pop();
            s=1; 
        } 
        else
        {
            q.push(q.front());
            q.pop();
            s++;            
        }
     } 
    return 0; 
}

你看,约瑟夫问题这么容易的写出来了,流程图帮我们梳理了思路后代码实现都不是问题,重点是你思路要清晰,并可以熟练使用算法,这样做题效率就会很高。

今天的0基础学算法系列就到这里吧,最后麻烦你点赞👍,还有关注➕,关注我,会给你带来更多的算法学习,最后如果你想巩固知识,洛谷上有题,最后再强调一遍,如果你喜欢我的博客,请关注我,以后会有更多精彩内容

           

     

0基础学算法 第三弹 队列

全文结束