精华内容
下载资源
问答
  • 18932 出栈序列合法性判定 时间限制:1000MS 代码长度限制:10KB 提交次数:0 通过次数:0 题型: 编程题 语言: 不限定 Description 每年期末考试必考题目。 一个栈的进栈序列是a、b、c、d、e,则可能的出栈序列是( )。...

    18932 出栈序列合法性判定

    时间限制:1000MS 代码长度限制:10KB
    提交次数:0 通过次数:0

    题型: 编程题 语言: 不限定

    Description

    每年期末考试必考题目。

    一个栈的进栈序列是a、b、c、d、e,则可能的出栈序列是( )。

    A.abecd B.decba C.dceab D.cabde

    输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。

    假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,

    但4,3,5,1,2就不可能是该压栈序列的弹出序列。(注意:这两个序列的长度是相等的)

    输入格式

    第一行一个整数n,表示输入序列的长度。(1<=n<=10000)

    第二行n个整数,表示栈的压入顺序。

    第三行n个整数,表示栈的出栈顺序。

    输出格式

    如果是弹出序列,输出yes,否则输出no。

    输入样例

    5
    1 2 3 8 6
    8 6 3 2 1

    输出样例

    yes

    #define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <iostream>
    using namespace std;
    #include<malloc.h> 
    #define OK 1
    #define ERROR 0
    #define STACK_INIT_SIZE 100 // 存储空间初始分配量
    #define STACKINCREMENT 10 // 存储空间分配增量
    
    typedef int SElemType; // 定义栈元素类型
    typedef int Status; // Status是函数的类型,其值是函数结果状态代码,如OK等
    
    struct SqStack
    {
    	SElemType* base; // 在栈构造之前和销毁之后,base的值为NULL
    	SElemType* top; // 栈顶指针
    	int stacksize; // 当前已分配的存储空间,以元素为单位
    }; // 顺序栈
    
    Status InitStack(SqStack& S)
    {
    	// 构造一个空栈S,该栈预定义大小为STACK_INIT_SIZE
    	// 请补全代码
    
    //该栈栈底无数据,栈顶有数据
    	S.base = new SElemType[STACK_INIT_SIZE];//new一个空栈数组,地址返回到S.base
    	S.top = S.base;//空栈top和base相同
    	S.stacksize = STACK_INIT_SIZE;//栈定义的大小STACK_INIT_SIZE给到stacksize
    	return OK;
    }
    
    Status Push(SqStack& S, SElemType e)
    {
    	// 在栈S中插入元素e为新的栈顶元素
    	// 请补全代码
    	if (S.stacksize <= S.top - S.base) {//栈顶和栈底差值大于等于栈范围则栈满
    		//栈满要先realloc扩大STACKINCREMENT再放入值
    		S.base = (SElemType*)realloc(S.base, sizeof(SElemType) * (S.stacksize + STACKINCREMENT));
    		if (S.base == NULL)return ERROR; else {
    			//要先将新申请的栈S.base赋值给原来的S.top
    			//S.top要在新栈S.base+原S.stacksize处
    			S.top = S.base + S.stacksize;
    			//再更新栈存储大小
    			S.stacksize += STACKINCREMENT;
    			//赋值到新S.top
    			S.top++;
    			*S.top = e;
    		}
    	}
    	else {
    		//栈没有满直接赋值
    		S.top++;
    		*S.top = e;
    	}
    	return OK;
    }
    
    Status Pop(SqStack& S, SElemType& e)
    {
    	// 若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR
    	// 请补全代码
    
    	//判断空栈
    	if (S.top == S.base)return ERROR; else {
    		//此处不用删除,用e存数据,将top移下一格即可
    		e = *S.top;
    		S.top--;
    	}
    	return OK;
    }
    
    Status GetTop(SqStack S, SElemType& e)
    {
    	// 若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR
    	// 请补全代码
    	if (S.top == S.base)return ERROR; else {
    		e = *S.top;
    	}
    	return OK;
    }
    
    int StackLength(SqStack S)
    {
    	// 返回栈S的元素个数
    	// 请补全代码
    	int length = 0;
    	//栈顶指针减栈底指针即为长度
    	length = S.top - S.base;
    	return length;
    }
    
    Status StackTraverse(SqStack S)
    {
    	// 从栈顶到栈底依次输出栈中的每个元素
    	  //请填空
    	if (S.top == S.base)printf("The Stack is Empty!"); //请填空
    	else
    	{
    		printf("The Stack is: ");
    		//找到顺序栈长度
    		int length = S.top - S.base;
    		//用栈顶赋值到p
    		SElemType* p = S.top;
    		while (length--)            //请填空
    		{
    			//请填空
    //向下递推
    			printf("%d ", *p--);
    		}
    	}
    	printf("\n");
    	return OK;
    }
    
    int main()
    {
    	int n;
    	cin >> n;
    	SqStack L;
    	//一定要初始化建立栈
    	InitStack(L);
    	int e;
    	//先用两数组把进栈和出栈数存储
    	int* push = new int[n];
    	int* pop = new int[n];
    	for (int i = 0; i < n; i++) {
    		cin >> e;
    		push[i] = e;
    	}
    	for (int i = 0; i < n; i++) {
    		cin >> pop[i];
    	}
    
    
    	int k = 0;
    	for (int i = 0; i < n; i++) {
    		//边入栈push[i]边和出栈数组数判断
    		Push(L, push[i]);
    		//这里要用while,直到出栈数和顶部数不同为止
    		while (*L.top == pop[k])Pop(L, e),k++;
    	}
    	//最后  如果L.top和L.base相同则说明全部出栈
    	//否则说明无法出栈
    	if (L.top == L.base)cout << "yes"; else cout << "no";
    
    	return 0;
    }
    
    展开全文
  • 判断出栈序列合法性描述格式样例题解及注释 描述 有1、2、3、4、5、6、7这7个数字依次全部入栈后再出栈,在入栈的过程中栈中的数据也可以随时出栈,一直到整个栈为空。将出栈得到的数字依次排列,就可以得到一个...

    判断出栈序列合法性

    描述

    有1、2、3、4、5、6、7这7个数字依次全部入栈后再出栈,在入栈的过程中栈中的数据也可以随时出栈,一直到整个栈为空。将出栈得到的数字依次排列,就可以得到一个“合法”的序列;对应的,有些形式的排列是无论如何调整入栈和出栈顺序也无法得到的,被称为“非法”序列。

    比如:“1 2 3 4 6 7 5” 和“1 2 5 6 4 3 7”都是合法的序列,而“1 2 5 7 3 4 6”和“1 2 6 3 4 5 7”以及“1 2 6 3 5 4 7”都是非法的序列。

    请编写程序,判断给定的由7个数字组成的序列是合法的还是非法的,如果是合法的输出“Y”,否则输出“N”。

    格式

    输入格式
    第1行是一个整数n,表示要判断的序列的数目。
    从第2行到第n+1行,每行一个序列,由1~7组成

    输出格式
    输出为一行,一个由“Y”和“N”组成的长度为n的字符串,中间不要空格

    样例

    输入样例
    5
    1 2 6 3 5 7 4
    1 2 6 5 3 7 4
    1 2 7 4 5 6 3
    1 2 7 6 3 4 5
    1 3 2 4 5 7 6
    输出样例
    NNNNY

    题解及注释

    数据集保证输入的是1~7个不同的数字组成的长度为7的序列。请注意输出的字母均为大写。n≤100。

    #include <stdio.h>  
    #include <stdlib.h>
    #define maxn 1000
    int stack[maxn];  
    int out[maxn];//全局变量,所有函数都可以使用
    
    int check(int n) 
    {  
        int po=0,top=0;  
        for(int i=1;i<=n;i++)//循环七轮
        {
            for(int j=po+1;j<=out[i];j++)//这里不好描述啊。这样,你把样例的第五个给带进去实验一下。
            {
                po=j;
                stack[top++]=j;//入栈
            }
            if(stack[--top]!=out[i])//出栈。与out比较
    			return 0;
        }
        return 1;
    }
    int main()  
    {  
    
        int n=7,k;  
        scanf("%d",&k);
    	while(k--)
        {
    		for(int i=1;i<=n;i++)//遍历输入
            {
    			scanf("%d",&out[i]);
    		} 
    		if(check(n))//函数返回1,则输出Y
    			printf("Y");  
    		else//返回其他值,输出N
    			printf("N"); 	
    	}
    }
    

    在这里插入图片描述

    写于2021年7月21日19:42分。

    展开全文
  • /*18932 出栈序列合法性判定 时间限制:1000MS 代码长度限制:10KB 提交次数:0 通过次数:0 题型: 编程题 语言: 不限定 Description 每年期末考试必考题目。 一个栈的进栈序列是a、b、c、d、e,则可能的出栈序列是( ...
    /*18932 出栈序列合法性判定
    时间限制:1000MS  代码长度限制:10KB
    提交次数:0 通过次数:0
    
    题型: 编程题   语言: 不限定
    Description
    每年期末考试必考题目。
    
    一个栈的进栈序列是a、b、c、d、e,则可能的出栈序列是(  )。
    
    A.abecd         B.decba         C.dceab        D.cabde
    
    输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。
    
    假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,
    
    但4,3,5,1,2就不可能是该压栈序列的弹出序列。(注意:这两个序列的长度是相等的)
    
    
    
    输入格式
    第一行一个整数n,表示输入序列的长度。(1<=n<=10000)
    
    第二行n个整数,表示栈的压入顺序。
    
    第三行n个整数,表示栈的出栈顺序。
    
    
    输出格式
    如果是弹出序列,输出yes,否则输出no。
    
    
    输入样例
    5
    1 2 3 8 6
    8 6 3 2 1
    
    
    输出样例
    yes
    
    
    输入:1234
    
    输出可能是:y是可能,x是不可能
    
    1234 y    1243 y    1324 y    1342 y    1423 x    1432 y
    2134 y    2143 y    2314 y    2341 y    2413 x    2431 y
    3124 x    3142 x    3214 y    3241 y    3412 x    3421 y
    4123 x    4132 x    4213 x    4231 x    4312 x    4321 y
    
    如果要列出所有可能的次序再去判断不可能的次序是一件成本非常高的事情。
    
    所以这里面一定是有规律的。
    
     试想,如果1是要在第一个出栈要怎么做:那定是1入栈,下一步就得立即出栈;如果2是要在第一出栈怎么做,那定是12一起入栈后立即把2出栈。
    
    所以规律是:答案中出栈的第一个元素是在原来的次序中是第几个,那么他的前面的元素必然都还在栈中。
    
    如4321是可能的,因为4在第一个,4是原序列中的最后一个,那123必在栈中只能按栈规则出,即321。
    
    如3124的顺序是不可能的,因为如果3是首个,那么12必在栈中,无论4在什么时候入栈和出栈,3之后的出栈顺序必有21的大致顺序,可见不会出现这种顺序。
    
    
    【参考思路】借用一个辅助栈,遍历压栈顺序,先将第一个放入栈中,这里是1,然后判断栈顶元素是不是出栈顺序的第一个元素,这里是4,很显然1≠4,所以我们继续压栈,直到相等以后开始出栈。出栈一个元素,则将出栈顺序向后移动一位,直到不相等,这样循环等压栈顺序遍历完成,如果辅助栈还不为空,说明弹出序列不是该栈的弹出顺序。
    
    举例:
    
    入栈1,2,3,4,5
    
    出栈4,5,3,2,1
    
    首先1入辅助栈,此时栈顶1≠4,继续入栈2
    
    此时栈顶2≠4,继续入栈3
    
    此时栈顶3≠4,继续入栈4
    
    此时栈顶4=4,出栈4,弹出序列向后移一位,此时为5,辅助栈里面是1,2,3
    
    此时栈顶3≠5,继续入栈5
    
    此时栈顶5=5,出栈5,弹出序列向后一位,此时为3,,辅助栈里面是1,2,3
    
    */
    #include <stdio.h>
    int stack[10001];
    int sp=-1;
    int main(   )
    {
        int n;
        scanf("%d",&n);
        int a1[n+1];//压栈顺序
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a1[i]);
        }
        int a2[n+1];//出栈顺序
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a2[i]);
        }
    
        int j=1;
        for(int i=1;i<=n;i++){
            stack[++sp]=a1[i];
            while(sp!=-1&&stack[sp]==a2[j]){
                sp--;
                j++;
            }
        }
        if(sp==-1)
        {
            printf("yes");
        }
        else
        {
            printf("no");
        }
    }
    

     

    展开全文
  • //不满足目前出栈的元素 st.pop(); } return true; } int main(void) { while(cin>>n,n) { for(int i=0;i;i++) cin>>a[i]; if(solve()) puts("Yes"); else puts("No"); } return 0; }

    在这里插入图片描述
    https://www.papamelon.com/problem/134
    按照栈的过程模拟即可。

    #include<bits/stdc++.h>
    using namespace std;
    const int N=1e5+10;
    int a[N],n;
    bool solve()
    {
    	stack<int>st;
    	for(int i=0,val=1;i<n;i++)
    	{
    		while(val<=n && (st.empty() || st.top()!=a[i])) st.push(val++);//说明这些都是在栈内
    		if(st.empty() || st.top() != a[i]) return false;//不满足目前出栈的元素
    		st.pop();
    	}
    	return true;
    }
    int main(void)
    {
    	while(cin>>n,n)
    	{
    		for(int i=0;i<n;i++) cin>>a[i];
    		if(solve()) puts("Yes");
    		else puts("No");
    	}
    	return 0;
    }
    
    展开全文
  • #include <iostream> #include <stack> #include <queue> #include <string.h> using namespace std; ...队列order是待校验序列。 */ bool is_valid_order(queue<...
  • //思路参考自LEETCODE@acvv_itdef 即下图231 `#include #include using namespace std; stack s; int a[20000],b[20000]; int main() { int n;cin>>n; int flag =0; for(int i=0;...int i=0,j.
  • 输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。 假设压入栈的所有数字均不相等。...第三行n个整数,表示栈的出栈顺序。 输出格式 如果是弹出序列,输出yes,否则输出
  • 题目分析: 这是一道计算出栈合法序列数目的题目: 方法一: 模拟 1.入栈过程,和出栈的过程 ,即左侧未入栈车辆数减一,站内车的数目加一,和左侧车辆数目不变,右侧数目减一实现了出栈的过程: code: #include ...
  • 例如: 序列 1 2 3 4 5 是某栈的压栈序列序列 4 5 3 2 1是该压栈序列对应的一个弹出序列, 但 4 3 5 1 2就不可能是该压栈序列的弹出序列。 思路: 首先我们来 理解下题意, 有些人可能会这么想, 1 2 3 4 5为...
  • 出栈序列合法性

    2021-03-31 11:30:09
    出栈序列合法性 一、问题简述 给定一个入栈序列,给出一系列出栈顺序,判断出栈序列是否合法。 例如:入栈序列[1,2,3,4], 出栈序列[4,3,2,1]合法, [3,4,2,1]合法, [3,1,2,4]不合法。 二、算法设计 建立...
  • 出栈序列合法性判断 如果栈无限大:出栈序列中的每个数后面的比它小的数,是按递减排列的。 如果栈大小有限制:模拟 基础实验3-2.4出栈序列合法性(25point(s)) 代码:O(n) #include <bits/stdc++.h> ...
  • 依次将入栈序列入栈,每个元素入栈后对栈顶元素进行判断,观察是否等于出栈序列的标记项(标记项初始为出栈序列的第一项),当等于时,该元素出栈,标记项往右移动一位,并重复对出栈后的栈顶元素进行判断,直至不...
  • (java)出栈序列合法性

    千次阅读 2019-04-23 23:01:41
    题目: 输入一个数字n,将1~n数字入栈,给出一个序列判断是否符合出栈的次序,如果符合输出Yes,否则输出No。 样例: 5 5 4 1 2 3 ...public class 出栈序列合法性 { public static void...
  • 3-3-5 堆栈 出栈序列合法性 (25 分) 给定一个最大容量为 M 的堆栈,将 N 个数字按 1, 2, 3, …, N 的顺序入栈,允许按任何顺序出栈,则哪些数字序列是不可能得到的?例如给定 M=5、N=7,则我们有可能得到{ 1, 2, 3...
  • 出栈序列合法性判断
  • PTA 出栈序列合法性

    2021-04-23 20:41:29
    输入第一行给出 3 个不超过 1000 的正整数:M(堆栈最大容量)、N(入栈元素个数)、K(待检查的出栈序列个数)。最后 K 行,每行给出 N 个数字的出栈序列。所有同行数字以空格间隔。 输出格式: 对每一
  • PTA出栈序列合法性

    2020-11-26 22:29:23
    基础实验3-2.4 出栈序列合法性 (25分) 天梯赛模拟赛l2-1 给定一个最大容量为 M 的堆栈,将 N 个数字按 1, 2, 3, …, N 的顺序入栈,允许按任何顺序出栈,则哪些数字序列是不可能得到的?例如给定 M=5、N=7,则我们...
  • 一个栈的进栈序列是a、b、c、d、e,则可能的出栈序列是( )。 A.abecd B.decba C.dceab D.cabde 输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。 假设压入栈的所有...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,648
精华内容 1,859
关键字:

出栈序列的合法性