精华内容
下载资源
问答
  • 堆栈操作合法性,假设以S和X分别表示入栈和出栈操作。如果根据一个仅由S和X构成的序列,对一个空堆栈进行操作,相应操作均可行(如没有出现删除时栈空)且最后状态也是栈空,则称该序列是合法的堆栈操作序列。请编写...
  • 堆栈操作合法性

    2021-01-26 21:58:25
    堆栈操作合法性 题目 假设以S和X分别表示入栈和出栈操作。如果根据一个仅由S和X构成的序列,对一个空堆栈进行操作,相应操作均可行(如没有出现删除时栈空)且最后状态也是栈空,则称该序列是合法的堆栈操作序列。请...

    堆栈操作合法性

    题目

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

    输入格式:

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

    输出格式:

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

    输入样例:

    4 10
    SSSXXSXXSX
    SSSXXSXXS
    SSSSSSSSSSXSSXXXXXXXXXXX

    输出样例:

    YES
    NO
    NO

    解析

    这个题目比较简单,主要就是考察对于栈的理解以及认清题目要求。题目中不合法的情况有三种:

    1. 栈满,做入栈操作,栈溢出
    2. 栈为空,做出栈操作
    3. 操作结束后,栈中仍然有元素存在

    所以我们可以直接使用一个标志位和计数值来实现。标志位表示当前的操作是否合法,遇到非法操作就置否。计数值表示栈中元素的个数,进栈时计数值加一,出栈时计数值减一

    #include <cstdio>
    #include <cstring>
    #define MAX 100
    
    int main(){
        int n, m, oLength;
        scanf("%d%d\n", &n, &m);
    
        while(n--){
            int temp = 0; // 记录当前栈已经有多少个元素
            bool flag = true; // 针对错误情况进行判断
            char operate[MAX];
            scanf("%s", operate);
            oLength = strlen(operate);
            for(int index = 0; index < oLength; index++){
                if(operate[index] == 'S'){
                    temp++;
                }else if(operate[index] == 'X'){
                    temp--;
                }
                //错误条件,栈溢出或者栈空时出栈操作。
                if(temp > m || temp < 0){
                    flag = false;
                    break;
                }
            }
            // 判断是否栈内是否有元素,如果有的话就置否
            if(temp != 0){ flag = false; }
            printf(flag?"YES\n":"NO\n");
    
        }
        return 0;
    }
    
    
    展开全文
  • 关于堆栈: 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对所有字符一视同仁。
    
    
    展开全文
  • 如果根据一个仅由S和X构成的序列,对一个空堆栈进行操作,相应操作均可行(如没有出现删除时栈空)且最后状态也是栈空,则称该序列是合法堆栈操作序列。请编写程序,输入S和X序列,判断该序列是否合法。 输入格式:...

    假设以S和X分别表示入栈和出栈操作。如果根据一个仅由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<iostream>
    #include<string>
    #include<stack>
    using namespace std;
    int main()
    {
        string ch;
        stack<int> chr;
        int n,m;
        cin>>n>>m;
        while(n--)
        {
            if(m==0)
            {
                if(n!=0) cout<<"NO"<<endl;
                else cout<<"NO";
            }
            else
            {
                while(!empty(chr))
                {
                    chr.pop();
                }
                int flag=0;
                cin>>ch;
                for(int i=0;i<size(ch);i++)
                {
                    if(ch[i]=='X'&&empty(chr))
                    {
                        flag=1;
                        break;
                    }
                    else if(ch[i]=='S'&&size(chr)<m)
                    {
                        chr.push(1);
                    }
                    else if(ch[i]=='S'&&size(chr)>=m)
                    {
                        flag=1;
                        break;
                    }
                    else if(ch[i]=='X'&&!empty(chr))
                    {
                        chr.pop();
                    }
                }
                if(!empty(chr)||flag==1)
                {
                    if(n!=0)
                        cout<<"NO"<<endl;
                    else cout<<"NO";
                }
                else if(empty(chr)&&flag==0){
                    if(n!=0)
                        cout<<"YES"<<endl;
                    else cout<<"YES";
                }
            }
        }
    }
    
    展开全文
  • PTA - 堆栈操作合法性

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

    堆栈操作合法性

    题目:假设以S和X分别表示入栈和出栈操作。如果根据一个仅由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 <iostream>
    #include <stack>
    
    using namespace std;
    
    bool is_right(string line, int stack_max_size);   // stack_max_size:堆栈的最大容量
    
    int main()
    {
    	int n, m;       
    	cin >> n >> m;
    	cin.ignore();   // 跳过换行符  
    	                // 等同于getchar(); 
        // 输入n行字符串                
    	for (int i = 0; i < n; i++)
    	{
    		string line;
    		getline(cin, line); 
    		
    		// 调用函数 
    		if (is_right(line, m))
    			cout << "YES" << endl;
    		else
    			cout << " NO" << endl;
    	}	 
    }
    
    bool is_right(string line, int stack_max_size)
    { 
    	stack<int> INT_STACK;
    	
    	for (int i = 0; i < line.size(); i++)
    	{
    		if (line[i] == 'S')
    		{
    			// 若当前堆栈长度的大于或等于堆栈的最大容量,return false;否则,压栈 
    			if (INT_STACK.size() >= stack_max_size)
    				return false;
    			INT_STACK.push(i); 
    		}
    		else if (line[i] == 'X')
    		{
    			// 若当前堆栈为空,return false;否则,弹栈 
    			if (INT_STACK.empty())  
    				return false;
    			INT_STACK.pop();
    		}
    	}
    	return INT_STACK.empty();
    }	
    

    解法二:stack法

    #include <iostream>
    #include <stack>
    
    using namespace;
    
    int main()
    {
    	int n, m;
    	cin >> n >> m;  
    	getchar();       
    	
    	string s;
    	while (n--)
    	{
    	    stack<char> c_stack;   // 将堆栈定义在内部,可实现每轮循环字符串的清空
    		//s.clear();           // 若堆栈定义在外部,即可用s.clear()实现每轮字符串的清空 
    		getline(cin, s);
    		
    		int count = 0;   
    		for (int i = 0; i < s.size(); i++)
    		{
    			if (s[i] == 'S')  
    			{
    				c_stack.push(s[i]);   // 压栈     
    				count++; 
    				if(count > m)  
    				{
    					cout << "NO" << endl;
    					break;
    				}         
    			}
    			else if (s[i] == 'X')   
    			{
    				c_stack.pop();   // 弹栈 
    				count--;    
    				if(count < 0)
    				{
    					cout << "NO" << endl;
    					break;
    				}      
    			}
    		}
    		
    		if (c_stack.empty() && count == 0)
    			cout << "YES" << endl; 
    		else
    			cout << "NO"<< endl;
    	}
    	return 0;
     } 
    

    解法三:string法

    #include <iostream>
    #include <string>
    
    using namespace std;
    
    int main()
    {
    	int n, m;     //  输入4 10 
    	cin >> n >> m;
    	getchar();
    	
    	string str;
    	while (n--)
    	{
    		int count = 0;
    		str.clear();        // 清空字符串
    		getline(cin, str);  // 输入一行字符串 
    		
    		for (int i = 0; i < str.length(); i++)
    		{
    			if (str[i] == 'S' && count < m)   // S:入栈 
    				count++;
    	
    			else if (str[i] == 'X' && count > 0)   // X:出栈
    				count--;
    			
    			else
    				break; 
    		}
    		
    		if (i == str.length() && count == 0) 
    			cout << "YES" << endl;
    		else
    			cout << "NO" << endl;
    	}
    	return 0; 
    	 
    }
    

    小结

    堆栈

    一.是什么?

    1.堆栈:是一种模板容器适配器,以“先进后出”的方式访问容器内的元素。(简称:LIFO线性表)

    在这里插入图片描述

    二.定义及操作

    1.头文件

    #include <stack>
    

    2.定义

    stack <int> s;
    

    3.操作:(成员函数)【重点】

    s.push();          //  在栈顶压入新元素
    s.top();           //  返回栈顶元素
    s.pop();           //  移除栈顶元素
    s.size();          //  返回栈中元素的数目
    s.empty();         //  堆栈为空返回true
    

    在这里插入图片描述

    三.应用时机及实例

    1.应用时机

    1.1.存储一批数
    1.2.以“先进后出”的顺序访问这批数

    2.实例 【掌握】

    2.1.回文判断
    2.2.括号匹配

    四.大小比较(了解即可)

    1.两个堆栈之间的大小关系基于首对不相等元素之间的比较。
    2.如果两个堆栈具有元素数目相同对应元素具有相同的值,则两个列表相等

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

    2019-03-30 17:00:49
    7-1 堆栈操作合法性 (20 分) 假设以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序列,判断该序列是否合法。 输入格式:...
  • 习题3.9 堆栈操作合法性 (20分) 假设以S和X分别表示入栈和出栈操作。如果根据一个仅由S和X构成的序列,对一个空堆栈进行操作,相应操作均可行(如没有出现删除时栈空)且最后状态也是栈空,则称该序列是合法的堆栈...
  • 如果根据一个仅由S和X构成的序列,对一个空堆栈进行操作,相应操作均可行(如没有出现删除时栈空)且最后状态也是栈空,则称该序列是合法堆栈操作序列。请编写程序,输入S和X序列,判断该序列是否合法。 输入格式:...
  • 如果根据一个仅由S和X构成的序列,对一个空堆栈进行操作,相应操作均可行(如没有出现删除时栈空)且最后状态也是栈空,则称该序列是合法堆栈操作序列。请编写程序,输入S和X序列,判断该序列是否合法。 输入格式...
  • 7-1 堆栈操作合法性 (10分)

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

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

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

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

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 26,724
精华内容 10,689
关键字:

堆栈操作合法性

友情链接: wetransfer-ddd946.zip