精华内容
下载资源
问答
  • 堆栈操作合法性
    2019-12-06 20:07:03

    假设以SX分别表示入栈和出栈操作。如果根据一个仅由SX构成的序列,对一个空堆栈进行操作,相应操作均可行(如没有出现删除时栈空)且最后状态也是栈空,则称该序列是合法的堆栈操作序列。请编写程序,输入SX序列,判断该序列是否合法。

    输入格式:

    输入第一行给出两个正整数N和M,其中N是待测序列的个数,M(≤50)是堆栈的最大容量。随后N行,每行中给出一个仅由SX构成的序列。序列保证不为空,且长度不超过100。

    输出格式:

    对每个序列,在一行中输出YES如果该序列是合法的堆栈操作序列,或NO如果不是。

    输入样例:

    4 10
    SSSXXSXXSX
    SSSXXSXXS
    SSSSSSSSSSXSSXXXXXXXXXXX
    SSSXXSXXX
    

    输出样例:

    YES
    NO
    NO
    NO
    #include<iostream> 
    #include<cstdio>
    #include<stack>
    #include<string>
    using namespace std;
    int main()
    {
    	int n,m;
    	cin>>n>>m;
    	getchar();
    	string str;
    	for(int i=0;i<n;i++) {
    		getline(cin,str);
    		int flag = 0;
    		/**
    		  *	堆栈在for循环内部定义,因为遍历一次后需要清空
    		  * 另外stack没有clear方法 ,清空时只能手动来做 
    		  */ 
    		stack<int> s; 
    		for(int j=0;j<str.size();j++){
    			if(str[j]=='S'){
    				if(s.size()>=m){
    					flag = 1;
    					break;
    				}
    				s.push(1);
    			}else{
    				if(s.size()==0){
    					flag = 1;
    					break;
    				}
    				s.pop();
    			}
    		}
    		if(s.size() != 0) flag = 1;
    		if(flag==1) printf("NO\n");
    		else printf("YES\n");
    	}
    	return 0;
    }

     

    更多相关内容
  • 堆栈操作合法性,假设以S和X分别表示入栈和出栈操作。如果根据一个仅由S和X构成的序列,对一个空堆栈进行操作,相应操作均可行(如没有出现删除时栈空)且最后状态也是栈空,则称该序列是合法的堆栈操作序列。请编写...
  • 关于堆栈: 1.它是什么 2.它为什么会出现/它的出现解决了什么问题 3.我们要怎么使用它 堆和栈到底是什么 栈和堆(托管堆)都存在于进程的虚拟内存中。 栈(Stack) 是操作系统在建立某个进程时或者线程(在支持多...

    关于堆栈:
    1.它是什么
    2.它为什么会出现/它的出现解决了什么问题
    3.我们要怎么使用它

    堆和栈到底是什么
    栈和堆(托管堆)都存在于进程的虚拟内存中。
    栈(Stack) 是操作系统在建立某个进程时或者线程(在支持多线程的操作系统中是线程)为这个线程建立的存储区域。

    1. 栈中存储值类型
    2. 栈上是向下填充的,数据只能从栈顶插入和删除(先进后出原则)。把数据放入栈顶是入栈(push),从栈顶删除数据是出栈(pop)
    3. 栈是自行维护的,也就是说内存自动维护栈,当栈顶的盒子不再被使用,它将被抛出
    4. 栈的空间较小,但访问速度快

    堆(Heap) 是应用程序在运行的时候请求操作系统分配给自己内存,一般是申请/给予的过程。由于从操作系统管理的内存分配所以在分配和销毁时都要占用时间,所以用堆的效率低得多。但是堆的好处是可以做的很大。

    1. 堆(也叫托管堆)存储引用类型
    2. 堆受垃圾处理器GC管理
    3. 堆没有访问限制
    4. 堆的空间较大,但访问速度没有栈快

    堆不分先进后出还是先进先出,堆没有任何访问限制,它就像你的书架,所有书都排列在书架上,当你想看某一本书时,可以随时找到一本我们需要的书,把它从书架上拿下来。而栈就像一串糖葫芦,你总是会先吃到最上面的那个山楂

    堆和栈的清理:
    栈是自上往下压入,使用时从上往下依次去拿,所以栈里的数据就像是弹夹里的子弹,打完就没了。(内存会自动清理掉已使用过的数据

    而堆则是由GC进行管理:垃圾收集器的基本算法很简单

    1. 将所有的托管内存标记为垃圾
    2. 寻找正被使用的内存块,并将他们标记为有效
    3. 释放所有没有被使用内存块
    4. 整理堆以减少碎片
      也就是说,当需要清理内存时,GC会去找那些很久没有引用地址指向的内存块,把他们清理掉

    为什么要有堆栈
    栈:为了存放运行时的局部变量,参数,返回数据,返回地址等
    堆:栈的性能非常高,但是对于所有的变量来说还不太灵活,而且变量的生命周期必须嵌套
    通常我们希望使用一种方法分配内存来处理数据,并且方法退出后很长一段时间内数据仍然可以使用。此时就要用到堆(托管堆)

    题目:7-11 堆栈操作合法性 (20 分)
    假设以SX分别表示入栈和出栈操作。如果根据一个仅由S和X构成的序列,对一个空堆栈进行操作,相应操作均可行(如没有出现删除时栈空)且最后状态也是栈空,则称该序列是合法的堆栈操作序列。请编写程序,输入S和X序列,判断该序列是否合法。
    输入格式:

    输入第一行给出两个正整数N和M,其中N是待测序列的个数,M(≤50)是堆栈的最大容量。随后N行,每行中给出一个仅由S和X构成的序列。序列保证不为空,且长度不超过100。
    

    输出格式:

    对每个序列,在一行中输出YES如果该序列是合法的堆栈操作序列,或NO如果不是。
    

    输入样例:

    4 10
    SSSXXSXXSX
    SSSXXSXXS
    SSSSSSSSSSXSSXXXXXXXXXXX
    SSSXXSXXX
    

    输出样例:

    YES
    NO
    NO
    NO
    

    代码:

    #include<stdio.h>
    int main()
    {
    	int n,m,i,length=0,flag=0;
    	scanf("%d %d ",&n,&m);//一定要注意这里有两个空格
    	for(i=0;i<n;i++)
    	{
    		length=0;
    		flag=0;
    		char ch;
    		while((ch=getchar())!='\n')
    		{
    			if(ch=='S')
    			{
    				length++;
    				if(length>m)flag=1; 
    			}
    			if(ch=='X')
    			{
    				length--;
    				if(length<0)flag=1;
    			}
    		}
    		if(length==0&&flag==0) printf("YES\n");
    		else printf("NO\n");
    	}
    	return 0;
    }
    

    错误注意:
    scanf
    scanf()是最常用的接受输入的方法,使用方式:

    scanf(控制串,&var1,&var2,...);
    

    其中控制串由三部分组成:

    1. 格式说明符:前缀为%,用于告诉方法下次要读入何种数据类型的数据,并顺次放到方法后的变量中.
    2. 空白符:由空格(" ")、制表符(“t”)和新行符(“n”)表示,让方法在输入流中忽略一个或多个空白符(只要存在一个就可以忽略多个)。控制串中的空白符使 scanf() 在输入流中读,但不保存结果,直到发现非空白字符为止。
    3. 非空白符:除去格式说明符和空白符以外的其他字符,如逗号,分号,于空白符相同,scanf()在输入流中读,但不保存结果。

    如果格式符之间添加了空格,那么按照规则,会忽略掉全部的空白符直到遇到下一个不是空白符的字符

    int i;
    char k;
    scanf("%d %c",&i,&k);//这个时候输入"1na"和"1a"的效果是一样的,因为无论怎么换行,都属于空白符,会被忽略
    scanf("%d%c",&i,&c);//这个时候输入"1na",运行后k会接收到换行符,而不是"a",因为空白符没有被忽略,而%c对所有字符一视同仁。
    
    
    展开全文
  • 堆栈操作合法性题目答案问题总结 题目 答案 #include<stdio.h> int top=0; void pop() { top--; } void push() { top++; } int main() { int n,max,i,j,flag=0; scanf("%d %d",&n,&max); ...

    堆栈操作合法性

    题目

    在这里插入图片描述

    答案

    #include<stdio.h>
    int top=0;
    void pop()
    {
    	top--;
    }
    void push()
    {
    	top++;
    }
    int main()
    {
    	int n,max,i,j,flag=0;
    	scanf("%d %d",&n,&max);
    	getchar();
    	char str[200];
    	for(i=0;i<n;i++)
    	{
    		gets(str);
    		for(j=0;str[j];j++)
    		{
    			if(str[j]=='S') 
    			{
    				if(top==max) flag=1;
    				push();
    			}
    			else if(str[j]=='X')
    			{
    				if(top==0) flag=1;
    				pop();
    			}
    //			printf("%d %d\n",top,flag);
    		}
    		if(flag==0&&top==0) printf("YES\n");
    		else printf("NO\n");
    		flag=0;
    		top=0;
    	}
    }
    

    问题总结

    1. 如果使用gets()函数,那就要在输入两个整数后加上getchar();而如果使用scanf就不需要了
    2. 内外循环的变量要区分开,例如i,j,不要都用i
    3. 注意审题,最后判断时不仅需要没有非法操作,还要堆栈为空(即top==0
    4. 每次循环后要记得将flag以及top变量还原
    展开全文
  • //因题目仅进行操作,无特特定输入值,我们选择输入1 //根据status布尔值判断操作合法性 } else if(str[j]=='X')//出栈操作 { status = pop(S[i], x0);因题目无需输出值,我们用x0仅接收; //根据status布尔值判断操作...
  • 如果根据一个仅由S和X构成的序列,对一个空堆栈进行操作,相应操作均可行(如没有出现删除时栈空)且最后状态也是栈空,则称该序列是合法堆栈操作序列。请编写程序,输入S和X序列,判断该序列是否合法。 输入格式:...
  • 如果根据一个仅由S和X构成的序列,对一个空堆栈进行操作,相应操作均可行(如没有出现删除时栈空)且最后状态也是栈空,则称该序列是合法堆栈操作序列。请编写程序,输入S和X序列,判断该序列是否合法。 输入格式:...
  • 7-1 堆栈操作合法性 (15 分) ** 假设以S和X分别表示入栈和出栈操作。如果根据一个仅由S和X构成的序列,对一个空堆栈进行操作,相应操作均可行(如没有出现删除时栈空)且最后状态也是栈空,则称该序列是合法的堆栈...
  • 倒也不用真的用到栈。 #include<iostream> using namespace std; int main() { int n,m; cin>>n>>m; while(n--) { string a; cin>>a; int s=0,x=0;... if(s-..
  • 如果根据一个仅由S和X构成的序列,对一个空堆栈进行操作,相应操作均可行(如没有出现删除时栈空)且最后状态也是栈空,则称该序列是合法堆栈操作序列。请编写程序,输入S和X序列,判断该序列是否合法。 输入格式:...
  • 7-2 堆栈操作合法性 (20分) PTA

    千次阅读 2020-10-31 17:19:20
    如果根据一个仅由S和X构成的序列,对一个空堆栈进行操作,相应操作均可行(如没有出现删除时栈空)且最后状态也是栈空,则称该序列是合法堆栈操作序列。请编写程序,输入S和X序列,判断该序列是否合法。 输入格式:...
  • 如果根据一个仅由S和X构成的序列,对一个空堆栈进行操作,相应操作均可行(如没有出现删除时栈空)且最后状态也是栈空,则称该序列是合法堆栈操作序列。请编写程序,输入S和X序列,判断该序列是否合法。 输入格式...
  • PTA 堆栈操作合法性 (20 分)

    千次阅读 2021-11-13 19:29:47
    如果根据一个仅由S和X构成的序列,对一个空堆栈进行操作,相应操作均可行(如没有出现删除时栈空)且最后状态也是栈空,则称该序列是合法堆栈操作序列。请编写程序,输入S和X序列,判断该序列是否合法。 输入...
  • 堆栈操作合法性 假设以S和X分别表示入栈和出栈操作。如果根据一个仅由S和X构成的序列,对一个空堆栈进行操作,相应操作均可行(如没有出现删除时栈空)且最后状态也是栈空,则称该序列是合法的堆栈操作序列。请编写...
  • 如果根据一个仅由S和X构成的序列,对一个空堆栈进行操作,相应操作均可行(如没有出现删除时栈空)且最后状态也是栈空,则称该序列是合法堆栈操作序列。请编写程序,输入S和X序列,判断该序列是否合法。 输入格式:...
  • PTA - 堆栈操作合法性

    千次阅读 2019-05-02 08:24:32
    堆栈操作合法性 题目:假设以S和X分别表示入栈和出栈操作。如果根据一个仅由S和X构成的序列,对一个空堆栈进行操作,相应操作均可行(如没有出现删除时栈空)且最后状态也是栈空,则称该序列是合法的堆栈操作序列。...
  • 7-1 堆栈操作合法性(20 分)

    千次阅读 2019-10-21 21:23:54
    7-1 堆栈操作合法性(20 分) 假设以S和X分别表示入栈和出栈操作。如果根据一个仅由S和X构成的序列,对一个空堆栈进行操作,相应操作均可行(如没有出现删除时栈空)且最后状态也是栈空,则称该序列是合法的堆栈操作...
  • 如果根据一个仅由S和X构成的序列,对一个空堆栈进行操作,相应操作均可行(如没有出现删除时栈空)且最后状态也是栈空,则称该序列是合法堆栈操作序列。请编写程序,输入S和X序列,判断该序列是否合法。 输入格式:...
  • 7-2 堆栈操作合法性 (20分)

    千次阅读 2020-09-17 20:27:56
    如果根据一个仅由S和X构成的序列,对一个空堆栈进行操作,相应操作均可行(如没有出现删除时栈空)且最后状态也是栈空,则称该序列是合法堆栈操作序列。请编写程序,输入S和X序列,判断该序列是否合法。 输入格式...
  • S代表入栈,X代表出栈,在这个题目中,堆栈不合理的情况只有两种,(空 或者 溢出)我使用了try帮我检测 空 是否合理,因为只要是栈为空,在进行pop()操作就会抛出异常,然后,如果说它出现异常了,我就可以直接...
  • 堆栈操作合法性 (C语言)

    千次阅读 2020-05-13 13:36:10
    如果根据一个仅由S和X构成的序列,对一个空堆栈进行操作,相应操作均可行(如没有出现删除时栈空)且最后状态也是栈空,则称该序列是合法堆栈操作序列。请编写程序,输入S和X序列,判断该序列是否合法。 输入格式 ...
  • 7-4 堆栈操作合法性 (10分)

    千次阅读 2020-03-28 12:11:38
    7-4 堆栈操作合法性 (10分) 假设以S和X分别表示入栈和出栈操作。如果根据一个仅由S和X构成的序列,对一个空堆栈进行操作,相应操作均可行(如没有出现删除时栈空)且最后状态也是栈空,则称该序列是合法的堆栈操作...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 27,475
精华内容 10,990
关键字:

堆栈操作的合法性