精华内容
下载资源
问答
  • 判断出栈序列是否合法

    千次阅读 2018-08-03 20:11:29
    判断出栈序列是否合法 2012年03月20日 23:32:39 阅读数:10273   【问题描述】对于一个栈,已知元素的进栈序列,判断一个由栈中所有元素组成的排列是否是可能的出栈序列。 比如,进栈序列为1 2 3 4,则可能的...

    转载自https://blog.csdn.net/masibuaa/article/details/7376106

    判断出栈序列是否合法

    2012年03月20日 23:32:39

    阅读数:10273

     

    【问题描述】对于一个栈,已知元素的进栈序列,判断一个由栈中所有元素组成的排列是否是可能的出栈序列。
    比如,进栈序列为1 2 3 4,则可能的出栈序列有4 3 2 1,1 4 3 2等。而1 4 2 3就不是。
    【输入形式】从标准输入读取第一行是一个整数N(3≤N≤10),代表有N个元素,其进栈序列是1 2 3 …… N。
    第二行是空格分隔的1~N的数字的一个排列。
    【输出形式】向标准输出打印结果。如果该排列是可能的出栈序列,则打印“YES”,
    否则打印“NO”。在行末要输出一个回车符。
    【输入样例】 
    3
    3 1 2
    【输出样例】
    NO
    【样例说明】进栈序列为1 2 3的出栈序列里没有3 1 2
    【评分标准】结果完全正确得20分,每个测试点4分。上传c语言源程序为outstack.c。

     

    判断标准:出栈序列中,元素i之后所有比i小的元素间必须是降序排列的。

    #include<stdio.h>
    #include<stdlib.h>
     
    void main()
    {
    	int i,j,k,N;
    	int temp;//存放s[i]之后可能存在的第一个比s[i]小的
    	int flag1;//标识s[i]之后是否存在比s[i]小的
    	int flag2;//标识出栈序列是否非法
    	scanf("%d",&N);
    	int *s=new int[N];//动态开辟长度为N的数组
    	for(i=0;i<N;i++)
    		scanf("%d",&s[i]);
    	for(i=0;i<N;i++)
    	{
    		flag1=0;
    		flag2=0;
    		for(j=i+1;j<N;j++)//寻找s[i]之后第一个比s[i]小的
    			if(s[j]<s[i])//s[i]之后存在比s[i]小的
    			{
    				temp=s[j];//s[j]是s[i]之后第一个比s[i]小的
    				flag1=1;
    				break;
    			}
    		if(flag1==1)
    			for(k=j+1;k<N;k++)
    				if(s[k]<s[i])//s[j]之后如果还有比s[i]小的数
    					if(s[k]<temp)//都必须小于它之前的一个比s[i]小的数
    						temp=s[k];//并更新temp
    					else//否则,出栈序列非法
    					{
    						flag2=1;
    						break;
    					}
    		if(flag2==1)
    		{
    			printf("NO");
    			exit(0);//退出程序
    		}
    	}
    	printf("YES");
    }
    

     

    展开全文
  • 1.判断出栈序列是否合法 模拟入栈过程,为了测试出栈序列是否正确,将元素按顺序入栈进行模拟。如果能够利用栈模拟出出栈次序,说明序列正确。 将序列存在队列中,将元素按顺序入栈,如果和队列首部元素相等,则弹出...

    1.判断出栈序列是否合法

    模拟入栈过程,为了测试出栈序列是否正确,将元素按顺序入栈进行模拟。如果能够利用栈模拟出出栈次序,说明序列正确。

    将序列存在队列中,将元素按顺序入栈,如果和队列首部元素相等,则弹出队列和栈,直到栈为空。
    最后栈不为空的话,说明序列不合法。

    在这里插入图片描述
    举个例子
    入栈:入栈序列ABCDEF 出栈序列FECDBA
    F出栈:入栈序列ABCDE 出栈序列ECDBA
    E出栈:入栈序列ABCD 出栈序列CDBA
    D!=C 所以不合法

    2.n个元素进栈,共有多少种出栈顺序

    https://blog.csdn.net/qq_33882435/article/details/78251149?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-7.control&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-7.control

    https://www.cnblogs.com/fangzheng-nie/p/8976155.html

    展开全文
  • 文章目录LeetCode 946判断出栈序列是否合法解题框架题目分析代码实现解决问题的类:开发main函数测试程序接口: LeetCode 946判断出栈序列是否合法 #mermaid-svg-530ziJJj1FSZtEVQ .label{font-family:'trebuchet ms...

    LeetCode 946判断出栈序列是否合法

    数据结构相关题
    构建解题框架
    题目分析
    代码实现

    解题框架

    在这里插入图片描述

    题目分析

    利用队列思维来进行判断:每次将入栈后的栈顶元素与出栈队列的头部元素进行对比,若相同则两者同时出队和出栈,若不同则继续入栈,到最后若栈为空栈则popped为合法出栈序列,不为空则不合法。

    构建一个栈用于入栈
    将栈顶元素与出栈队列头部进行比较
    相同则同时出队和出栈直到不同为止
    若最后栈为空则为合法出栈序列,否则非法
    不同则继续将入栈序列入栈

    在这里插入图片描述

    代码实现

    解决问题的类:

    在这里插入图片描述

    开发main函数测试程序接口:

    在这里插入图片描述

    展开全文
  • 题目:分别给定入栈序列和出栈序列,然后判断出栈序列是否合法。如入栈序列是[1,3,2,4,5],出栈序列[3,1,2,4,5]是合法的,[3,1,5,2,4]是不合法的。 思路: 判断出栈序列是否合法的标准是:栈顶如果是需要出栈的...

    题目:分别给定入栈序列和出栈序列,然后判断出栈序列是否合法。如入栈序列是[1,3,2,4,5],出栈序列[3,1,2,4,5]是合法的,[3,1,5,2,4]是不合法的。

    思路:
    判断出栈序列是否合法的标准是:栈顶如果是需要出栈的元素,则出栈,如果不是则将未入栈的元素按入栈序列依次入栈,直到栈顶为出栈的元素。如果所有元素都入栈了,仍然没有找到要弹出的元素,那么该出栈序列一定不是合法的。

    参考代码:

    #include <iostream>
    #include <stack>
    using namespace std;
    
    bool isPopOrder(int* pushOrder, int* popOrder, int len){
        if(len<=0)
            return false;
    
        int* pushIndex=pushOrder,*popIndex=popOrder;
        stack<int> s;
        while(popIndex!=popOrder+len){
            if(!s.empty()&&s.top()==*popIndex){   //从栈顶查找
                s.pop();
                ++popIndex;
            }else{                                //从未入栈的序列查找
                while((pushIndex-pushOrder<len)&&(*pushIndex!=*popIndex)){
                    s.push(*pushIndex);
                    ++pushIndex;
                }
                if(pushIndex-pushOrder<len&&(*pushIndex==*popIndex)){   //在未入栈的元素中找到了需要出栈的元素
                    ++popIndex;
                }
                else                            //没有找到
                    return false;
            }
        }
        return true;
    }
    
    int main(){
       int pushOrder[5]={1,3,2,4,5};
       int popOrderRight[5]={5,4,2,3,1};
       int popOrderWrong[5]={3,1,5,2,4};
    
       if(isPopOrder(pushOrder,popOrderRight,5))
           cout<<"popOrderRight is right"<<endl;
       else
           cout<<"popOrderRight is wrong"<<endl;
    
       if(isPopOrder(pushOrder,popOrderWrong,5))
           cout<<"popOrderWrong is right"<<endl;
       else
           cout<<"popOrderWrong is wrong"<<endl;

    实验结果:
    打印输出:

    popOrderRight is right
    popOrderWrong is wrong

    如果代码有bugs,欢迎猿友留言指正。


    参考文献

    [1]剑指Offer.何海涛.电子工业出版社.

    展开全文
  • 一、出栈序列判断 问题:按1、2、3、4、5进栈,出栈是否能得到1、2、3、4、5?是否能得到3、4、5、1、2? 答案:可以得到1、2、3、4、5,只要1进栈,1出栈,2进栈,2出栈以此类推即可得到1、2、3、4、5;但是不...
  • 栈--判断出栈序列是否合法

    千次阅读 2015-01-14 22:04:40
    假设入栈序列A按照1,2,3,4...n 编号。  每次我们可以把序列A中的第一个元素... 也可以是从堆栈顶弹出一个元素放入出栈序列B.  这样,经过n次入栈和出栈操作后,我们可以得到一个出栈序列B。    现在,你的任
  • 题意:给出入栈顺序为1,2,,,n,求出栈顺序是否合法 题解:遍历出栈顺序,对于出栈的第i个元素有3种可能:(此时访问到入栈序列的j位置) ①j=a[i]:i++,j++ ②a[i]在栈顶,直接弹栈即可,j不变 ③a[i]在j位置之后...
  • 这道题主要考察栈的知识,已知入栈序列,判断出栈序列是否合法。 第一行输入获取三个数字分别为栈的容量M,输入序列的元素数量N,输入序列的数量K。然后每一行都为一个出栈序列,如果输入序列有N个值,那么入栈序列...
  • - 若已知从1到n的数字序列按循序入栈,每个数字入栈后即可出栈,也可在栈中停留,等待后面的数字入栈出栈后,该数字再出栈,求该数字序列的出栈序列是否合法? 思路 队列与栈的搭配使用 将出栈序列压入队列 ...
  • 输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均...*思路:依据给定的出栈序列,在每次将入栈序列中的元素压入栈之后尝试进行出栈,若最终所有元...
  • 题目大意:判断一个出栈序列能不能从1,2,3,……,n 经过栈处理后生成。 思路:  Ⅰ:定理:出栈序列合法 <=> 存在k,满足i<j<k,使得S[k]<S[i]<S[j]。(i,j,k是入站顺序,s[i],s[j],s[k]是...
  • 关于栈有一个很有用的性质,对于出栈序列的每一个元素,该元素后 比该元素先入栈的一定按照降序排列。若入栈的是一串数字例如12345,则21435是一个合法的出栈顺序,每一个元素i后比i小的都是降序排列(因为入栈的...
  • 题目描述 输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出...判断标准:出栈序列中第i个元素后面的元素在是入栈序列中的逆序 思路:把给出的入栈序列以此入栈;每次入栈检查
  • 题目 Given a stack which can keep M numbers at most. Push N numbers in the order of 1, 2, 3, …, N and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence ...
  • 相信大家在做和栈相关的题目的时候会遇到判断一个序列是否合法出栈序列这一类题,模拟栈的操作是标准解法,但是基础较差的同学可能模拟的时候容易出错,下面我给大家介绍两个结论和一些小技巧用于快速准确的秒杀...

空空如也

空空如也

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

判断出栈序列是否合法