首页 > 其他分享 >浙大数据结构:02-线性结构4 Pop Sequence

浙大数据结构:02-线性结构4 Pop Sequence

时间:2024-09-07 12:49:31浏览次数:13  
标签:02 队列 Sequence int tt squsize Pop stksize front

这道题我们采用数组来模拟堆栈和队列。
简单说一下大致思路,我们用栈来存1234.....,队列来存输入的一组数据,栈与队列进行匹配,相同就pop

1、条件准备

stk是栈,que是队列。
tt指向的是栈中下标,front指向队头,rear指向队尾。
初始化栈顶为0,队头为0,队尾为-1
#include<iostream>
using namespace std;

#define MAXSIZE 1010
#define ERROR -1

int stk[MAXSIZE],tt=0;
int que[MAXSIZE],front=0,rear=-1;
主函数加快cin,cout,将解决问题的步骤用solve()来实现

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);cout.tie(0);
  solve();
    return 0;
}

2、solve函数

先输入栈的最大空间,每组数据个数,有多少组。
将具体解决方法放入judge函数写,该函数会判断并输出yes,no
到下一组前要清空栈和队列。
void  solve()
{
    int stksize,squsize,num;
    cin>>stksize>>squsize>>num;
   
    while(num--)
    { 
      judge(stksize,squsize);
//传栈最大空间,每组数据长度
      tt=0;front=0,rear=-1;
    }
  
}

3、judge函数

flag是判断最后该输出yes还是no
从1到squsize遍历,因为栈是按这个顺序放元素的,每次遍历入栈,并读一个数据到队列。
如果栈空间超过stksize了,则输出NO
如果队头元素与栈顶元素匹配,则pop
遍历完后看看队列还有没有没匹配的,有的话与栈中元素匹配,这时栈顶必须与队头匹配,不匹配则为NO
void judge(int stksize, int squsize)
{
    int flag = 1;//标记是yes还是no
    for (int i = 1; i <= squsize; i++)
    { 
        stk[++tt] = i;   //放入栈中
        cin >> que[++rear];   //读取数据
        if (tt > stksize)   //栈空间超出限制
         flag = 0;
        while (tt && stk[tt] == que[front])
        {   //栈顶与队头元素匹配,pop
            tt--;
            front++;
        }
    }
    while (front <= rear)
    {  //最后剩余栈中的元素进行匹配
        if (stk[tt] != que[front])   flag = 0;
        tt--, front++;
    }
    if (flag)  //输出
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}

4、总结

用数组模拟栈队列在写算法题中也是常用的,因为结构体没数组这样找快。
当然这道题也可以写成栈与队列结构体的形式,只需把其中某些代码改动即可。
完整代码如下:
#include <iostream>
using namespace std;

#define MAXSIZE 1010
#define ERROR -1

int stk[MAXSIZE], tt = 0;
int que[MAXSIZE], front = 0, rear = -1;

void judge(int stksize, int squsize)
{
    int flag = 1;
    for (int i = 1; i <= squsize; i++)
    {
        stk[++tt] = i;
        cin >> que[++rear];
        if (tt > stksize)
         flag = 0;
        while (tt && stk[tt] == que[front])
        {
            tt--;
            front++;
        }
    }
    while (front <= rear)
    {
        if (stk[tt] != que[front])   flag = 0;
        tt--, front++;
    }
    if (flag)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}

void solve()
{
    int stksize, squsize, num;
    cin >> stksize >> squsize >> num;

    while (num--)
    {
        judge(stksize, squsize);
        tt = 0;
        front = 0, rear = -1;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

标签:02,队列,Sequence,int,tt,squsize,Pop,stksize,front
From: https://blog.csdn.net/qq_74924951/article/details/141994045

相关文章

  • 2022真题
    数字放大题目描述给定一个整数序列以及放大倍数x,将序列中每个整数放大x倍后输出。输入格式包含三行:第一行为N,表示整数序列的长度(N≤100);第二行为N个整数(不超过整型范围),整数之间以一个空格分开;第三行包含一个整数(不超过整型范围),为指定的整数x。输出格式N个整数,为......
  • 聚焦2024数博会|与天空卫士一起探索AI与数据安全的融合应用
    中国国际大数据产业博览会(简称数博会),是全球首个以大数据为主题的博览会,自2015年创办以来,经过多年的深厚沉淀,数博会已发展成为国际知名、引领前沿趋势的专业展示合作平台。2024年8月28日至30日,第十届数博会在贵阳举办。天空卫士受邀参加“数据安全产业发展”交流活动。该活动由国家......
  • [HNCTF 2022 WEEK2]easy_include
    开启NSSCTF靶场,打开链接:可以看到过滤了很多常见的利用协议,GET传参是file先随便读取点正常的文件吧,构造payload:/?file=/etc/passwd可以看到是nginx服务器还有日志文件信息apache服务器日志存放文件位置:/var/log/apache/access.lognginx服务器日志存放位置:/var/log/......
  • 2024.9
    9.6来到了北京大学,总之预科生活开始了!宿舍条件很差,我阳台呢?室友是zphqiuly云浅。爸妈陪我来的,帮我买了点生活用品后就走了。哎呀为啥打出上一句话有一种莫名的心悸,果然以后还是要独自面对生活吗。会赢的,一定。吃完晚饭(好吧我没吃)jt和cjz来我宿舍玩,可爱捏。然后和z......
  • 条款02: 尽量以const,enum,inline 替换 #define
    宏实现1.宏定义有可能从未被编译器看到,找不到宏定义2.宏有可能存在多份#defineASPECT_RATIO1.6531.宏实现函数,必须为宏中所有实参加上(),即使加上也会有被多次调用template<typenameT>inlinevoidprint(Tdata){ std::cout<<data<<std::endl;}#define......
  • Base2024
    简单记录了一部分题目(记录的基本就是看了wp的)Aura酱的礼物ssrfdata伪协议格式data://text/plain,xxx能读取出内容data://text/plain;base64,xxxxxx,xxxxxx先base64解码再读取出内容@隔断当要求url开头时,使用@来分隔file=http://[email protected]源码<?phphighlig......
  • 2024.9.6 近期练习
    P5044[IOI2018]meetings会议对于\(h_i\le20\)的数据,我们每个点维护单调栈,其代价为\(x\)的时候,取的位置是一个区间。很显然已经有一个莫队算法,支持区间加,区间查询即可。然而不优。其实单调栈与笛卡尔树是相似的,考虑建出笛卡尔树。我们假设就对\([l,r]\)dp,那么取出最......
  • 【C题已出】2024全国大学生数学建模C题完整论文+每小问解题代码+可视化结果图+最终结
                           2024国赛C题2024数学建模国赛C题word版成品论文【附带完整解题代码+可视化图表】https://www.jdmm.cc/file/2711227/一 、 摘要本文针对一个复杂的农业种植规划问题,建立了一系列优化模型并提出了相......
  • 【计算机毕设选题】2025届计算机专业毕设全新推荐选题指南
    文章目录前言一、2025计算机毕设推荐选题(1)javaWeb以及管理系统类(2)小程序以及安卓系统类(3)Python系统类二、项目结构示例(1)项目代码(2)运行截图三、项目部分代码设计四、数据库代码设计参考五、参考论文示例六、源码获取前言2025届的毕业季已经来到,相信各个高校的毕设......
  • 生成树协议(STP:802.1D、RSTP:802.1w、MSTP:802.1s)
    在二层网络中,如果没有生成树协议,会带来哪些问题:1、广播风暴2、MAC地址表飘移3、重复数据帧接收回顾生成树有哪些术语:1、根桥为了破除环路,生成树网络首先要选举出一个首脑,头脑,首领。叫做根桥,也叫作根交换机2、桥IDbridge-id:由桥优先级(默认取值为32768,必须为4096......