精华内容
下载资源
问答
  • 快速判断的正确输出序列
    千次阅读
    2020-04-02 09:56:05

    一句话,先入后出必逆序,违反这个规则的都是错误序列。

    例一:
    设一个栈的输入序列是 1,2,3,4,5,则下列序列中,是栈的合法输出序列的是( )。

    A 5 1 2 3 4
    B 4 5 1 3 2
    C 4 3 1 2 5
    D 3 2 1 5 4
    分析:
    A 1234 比5先入 后出但没有逆序 错误
    B 123比45先入 后出没有逆序 变成了132 错误
    C 12先入 后出没有逆序 错误
    D 正确
    D
    例二:
    有六个元素6,5,4,3,2,1的顺序进栈,问下列( )不是合法的出栈序列?
    A 543612

    B453126

    C 346521

    D 234156
    分析:
    C 65比34先入 后出没有逆序 错误
    C

    更多相关内容
  • 判断合法输出序列方法:对于相邻的两个数a1,a2,如果为升序,则记录下顺序小于a2而等于a1,a2的数,压栈;如果为降序,则将a2与栈顶数进行比较,如果相等,则该部分正确;如果相等,则整个序列错误。 代码 #...

    题目

    设计算法以判断对输入序列1,2,3,…,n,序列 a1,a2,…,an 是否是该栈的合法输出序列。

    思路

    这里的“顺序”指输入序列的顺序。
    判断合法栈的输出序列方法:对于相邻的两个数a1,a2,如果为升序,则记录下顺序小于a2而不等于a1,a2的数,压栈;如果为降序,则将a2与栈顶数进行比较,如果相等,则该部分正确;如果不相等,则整个序列错误。

    代码

    #include <iostream>
    using namespace std;
    
    const int maxlen = 100;
    class Stack {
    public:
    	Stack();
    	bool full() const;
    	bool empty() const;
    	void push(int x);
    	int top()const;
    	void pop();
    private:
    	int count;
    	int data[maxlen];
    };
    Stack::Stack() {
    	count = 0;
    }
    bool Stack::full()const {
    	return count == maxlen-1;
    }
    bool Stack::empty()const {
    	return count == 0;
    }
    void Stack::push(int x) {
    	if ( full()) cout<<"Overflow";
    	else {
    		data[count] = x;
    		count++;
    	}
    }
    int Stack::top()const {
    	if (empty())return UNDERFLOW;
    	else return data[count - 1];
    }
    void Stack::pop() {
    	if (empty())cout<<"Underflow";
    	else count -= 1;
    }
    
    int main() {
    	int size;
    	cin >> size;
    	int a[maxlen];
    	int x;
    	for (int i = 0; i < size; i++) {
    		cin >> x;
    		a[i] = x;
    	}
    	Stack q;
    	int c=0;
    	int flag = 0;
    	for (int i = 1; i < size+1; i++) {
    		if (i == a[c]) {
    			c++;
    			if (a[c] < a[c -1]) {
    				c++;
    				int top = q.top();
    				if (a[c-1] == top) {
    					q.pop();
    					continue;
    				}
    				else {
    					cout << "wrong sequence";
    					flag = 1;
    					break;
    				}
    			}
    			else continue;
    		}
    		q.push(i);
    	}
    	if (flag == 0)cout << "correct sequence";
    	return 0;
    }
    

    如果有错误请大佬指出!感谢!

    展开全文
  • 序列个数太多,以123为例:123进栈,出栈321;1进栈,1出栈,2进栈,2出栈,3进栈,3出栈,所以是123,以此类推。则(n,m)的排列问题可以转化为(n,m-1)+(n-1,m+1)此时m>=1, 因为必须中有元素才可以出栈当m=0则(n,0)的...

    序列个数太多,以123为例:123进栈,出栈321;1进栈,1出栈,2进栈,2出栈,3进栈,3出栈,所以是123,以此类推。

    则(n,m)的排列问题可以转化为(n,m-1)+(n-1,m+1)

    此时m>=1, 因为必须栈中有元素才可以出栈

    当m=0则(n,0)的问题只能转化为(n-1,1)

    当问题为(0, m)时得到递归边界,这个问题的解是只有一种排列

    最终推导的结果是:P2n = C(n 2n)— C(n+1 2n)=C(n 2n)/(n+1)

    这个结果是一个“卡塔兰数”Catalan,在组合数学中有介绍,可以参阅有关资料

    结果=C(5,10)/6= 42

    95f2f4f7dcc427f1d228bf3829871f9c.png

    扩展资料:

    1、进栈(PUSH)算法

    ①若TOP≥n时,则给出溢出信息,作出错处理(进栈前首先检查栈是否已满,满则溢出;不满则作②);

    ②置TOP=TOP+1(栈指针加1,指向进栈地址);

    ③S(TOP)=X,结束(X为新进栈的元素);

    2、退栈(POP)算法

    ①若TOP≤0,则给出下溢信息,作出错处理(退栈前先检查是否已为空栈, 空则下溢;不空则作②);

    ②X=S(TOP),(退栈后的元素赋给X):

    ③TOP=TOP-1,结束(栈指针减1,指向栈顶)。

    参考资料来源:百度百科-栈

    展开全文
  • 的合法输出序列

    万次阅读 多人点赞 2017-11-29 16:27:10
    的合法输出序列 最近写的实验题,附加题中涉及合法输出序列。 假设的输入序列为1、2、3、…、n,设计算法实现对给定的一个序列,判定其是否是此合法的输出序列。 假设的输入序列为1、2、3、…、n,...

    栈的合法输出序列

    最近写栈的实验题,附加题中涉及合法输出序列。

    <1>假设栈的输入序列为1、2、3、…、n,设计算法实现对给定的一个序列,判定其是否是此栈合法的输出序列。
    <2>假设栈的输入序列为1、2、3、…、n,设计算法求出所有可能的出栈序列。

    第一问在网上可以找到规律——判断出栈序列是否合法
    它的规律在于出栈序列中,元素i之后所有比i小的元素间必须是降序排列的,元素i从头向后遍历。
    因此在判断是,需要引入两个循环和一个变量表示最小值,然后依次进行比较。

    bool StackArray::JudgeMatchedStackArray(int a[],int len)
    {
        int low=0;//表示一遍遍历中的最小值
        for(int i=0;i<len;++i)//元素i从头向后依次遍历
        {
            low=a[i];
            for(int j=i;j<len;++j)//从元素i开始向后遍历,验证规律
            {
                if(a[j]<a[i])//首先要找之后比元素i小的元素
                {
                    if(a[j]>low)
                        return false;
                    else    //验证这些元素按照降序排列
                        low = a[j];
                }
            }
        }
        return true;
    }

    第二问较为复杂,基本思路是用递归解决。
    这里贴两个提供思路的网址:

    一、
    (1)
    我们之前谈到,合法的出栈序列条件: 对于每个已出栈数之后的且小于此数的数都必须按降序排列。例如1 2 5 3 4。对于5来说,后面的3,4都小于5,可是3,4却是升序的。则肯定不是合法的出栈序列。
    由此可以想到我们可以求出所有的全排列,然后从中剔除掉非法序列。显然,当序列的长度增加时,多余的计算太多,效率太低。
    (2)
    模拟入栈出栈过程,每次都有两种选择,要么入栈要么出栈。显然按照递归方式是可行的。但是又有一个问题,一般递归,很少牵扯到递归层次之间数据传送问题。而模拟这个过程时,栈的信息从上层传到下层,最后回到上层时,必然栈的状态早已被下层改了。解决办法就是,下层返回时,回复栈的原状态。这样递归就不会出错了。
    ——求所有的出栈序列

    伪代码来源

    dostack(输入队列,中间栈,输出队列)  
    
    if(输入队列为空)  
    {  
            if(中间栈为空)  
        {
            输出输出队列中的结果 
        }
        else  
        {
            中间栈出栈,放入输出队列  
    
            dostack(输入队列,中间栈,输出队列)
        }
    }
    else  
    {
            if(中间栈非空) 
        { 
                新建输入队列2、中间栈2、输出队列2 //这种情况下有两个出栈方式,
            //因此需要保存一下原状态,再分别对两个进行处理
    
                中间栈2出栈并放入输出队列2  
    
            dostack(输入队列2,中间栈2,输出队列2)
        }
    
        输入队列出队一个数并压入中间栈  
    
        dostack(输入队列,中间栈,输出队列) 
    }

    而要计算一个栈的出栈序列有多少种可能?
    可以在上述代码1中添加一个技术变量,最后用它来表示可能种数。
    而对于不需要输出所有可能的题目而言,也由相应的计算公式:
    对于I(n)有C(2n,n)-C(2n,n-1)个出栈序列

    代码块

    void StackArray::PopOrderStackArray(StackArray other,QueueArray another)
    //该类为输入栈,other 表示中间栈,another 表示输出队列
    {
        if(EmptyStackArray())
        {
            if(other.EmptyStackArray())
                another.printQueueArray();
            else
            {
                another.insertQueueArray(other.PopStackArray());
                PopOrderStackArray(other,another);
            }
        }
        else
        {
            if(!other.EmptyStackArray())
            {
                StackArray a(*this),b(other);
                QueueArray c(another);
                c.insertQueueArray(b.PopStackArray());
                a.PopOrderStackArray(b,c);
            }
            other.PushStackArray(PopStackArray());
            PopOrderStackArray(other,another);
        }
        return ;
    }

    运行结果如下:

    1 2 3
    1 3 2
    2 1 3
    2 3 1
    3 2 1

    展开全文
  • 输出序列

    千次阅读 2018-02-16 18:47:17
    写在前面: 有很多同学刚开始读题的时候,可能不太理解题意...详细解析如下:Q:如果的输入序列为{A,B,C,D,E},则他的输出序列不可能是:A:(A)输出序列{ A,B,C,D,E }选项(1)的方式为:A入栈,A出栈,B入栈...
  • 的实际应用—判断一个序列是否为的有效输出序列 对于数据结构学科的初学者,的构建是很重要的知识,判断一个是否为有效输出序列是其中重要的题目。笔者整理了三种C++代码,其核心编程思想大致相同,希望对...
  • 以123为例,假如123在一个队列里,输入到中间栈,通过中间栈输出到右边队列中(这里用队列是为了方便输出,用数组储存也行) 我们分析一下中间的过程: 假如1已经入栈,这个时候有两种可能,要么中间栈栈顶的数据...
  • 把可能的输出按最后一个元素分为n类 以k为例 比k小的元素肯定在k之前输出,...对于k来说,总的合法的输出序列个数就是f(k-1)*f(n-k) 双端队列 这人认为这个数据结构很bug。基本就是像一根管子,两端都可以进出 ...
  • 如果,则为有效输出,返回总的出栈次数,如果不能,则为无效输出,返回0。序列的输入及输出都是从左往右。 1、输入输出序列皆为正整数,可能有重复的数字 2、如果一个数字在输入序列中没有出现,但在输出序列中...
  • 一个的入栈序列是 a,b,c,d,e,则可能的输出序列是( ) 。 a) edcba b) decba c)dceab d) abcde 堆栈讲究先进后出,后进先出, 边进边出 选项1是abcde先入栈,然后依次出栈,-----》edcba 选项2是abcd先依次...
  • // 数字按照 1-n的顺序进栈,给定输出序列,判断该序列是否正确 // 个人认为用一个来模拟出栈是比较合适的 //用队列来存储给定的输出序列 //用来模拟 #include<iostream> #include<stdlib.h> #...
  • 理解一个栈的入栈序列 1,2,3,4,5,栈输出序列问题 数据结构——栈问题 如何理解这种序列问题呢?且看下文: 栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被...
  • 的所有可能输出序列

    千次阅读 2019-11-07 09:31:18
    给一些元素,求把它们塞进之后,所有的可能出栈序列 可能序列的种数等于Catlan数 代码如下: #include <iostream> #include <cstring> #include <cstdio> using namespace std; int flag; void...
  • hadoop2面试题 -判断一个序列是不是输出序列.pdf
  • 判断输出序列是否合法问题简述大概需要用的元素代码 、 问题简述 一个最多可以存储M个数的;按1,2,3...顺序入栈并随机出栈 输入一个出栈序列,判断给出 出栈序列是否合理 大概需要用的元素 一个——按序...
  • 【剑指offer】的输入输出序列

    千次阅读 2019-06-04 11:55:59
    例如序列1,2,3,4,5是某的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就可能是该压栈序列的弹出序列。(注意:这两个序列的长度是相等的) 【分析】 这道题考察混洗的判断,选择题...
  • 队列:先进先出判断一个序列不栈输出判断一个序列 题目描述:输入两个整数序列。其中一个序列表示的push顺序,判断另一个序列有没有可能是对应的pop顺序。为了简单起见,我们假设push序列的任意两个整数都是...
  • 判断一个数列是否是输出序列

    千次阅读 2020-10-16 22:07:35
    如果,返回总的出栈次数,如果不能,返回0。序列的输入及输出都是从左往右。(输入输出序列皆为整数且没有重复的数字,如果一个数字在输入序列中没有出现,那么其在输出序列中也不会出现) 1.2 输入形式 第一...
  • 一个的入栈序列是 a,b,c,d,e,则可能的输出序列是( ) 。 a) edcba b) decba c) dceab d) abcde 堆栈讲究先进后出,后进先出 选项1是abcde先入栈,然后依次出栈,正好是edcba 选项2是abcd先依次入栈,然后d...
  • 要求反向输出这个正整数序列。 要求定义一个来实现这个程序的功能。 输入 一个整数序列,每个数之间以空格隔开,非负整数,只含 正整数 和 0 。-1 表示输入结束。 输出 反向输出输入文件中的整数序列。 提示: 在...
  • 一个输入序列为1,2,3,4,5,则下列序列中可能是输出序列是( ) A.1 2 3 4 5 B.5 4 3 2 1 C.2 3 4 5 1 D.4 1 2 3 5 分析:可以根据答案来判定的,像A的话,顺序是1 2 3 4 5 那么当1进来的时候...
  • 输出序列1.连续输入和输出2.非连续输入输出2.1合法出栈序列的个数3.双端队列 1.连续输入和输出 :逆序 队列:顺序 2.非连续输入输出 出栈序列中每一个元素后面所有比它小的元素组成一个递减序列,如下图橙色的...
  • 判断输出序列的合法性

    千次阅读 2019-04-27 19:22:35
    一个的进栈序列是a,b,c,d,e,判断输出序列的合法性: A.edcba B.decba C.dceab D.abcde 思路 先把入栈序列中的元素标定序号1,2,3,… 则出栈序列中的每个元素后面的序号比它小的元素,其序号是...
  • 利用实现逆序输出

    2021-10-02 20:41:33
    【算法代码】 #include <bits/stdc++.h> using namespace std; int n,x; int main() { cin>>n; stack<int> s; while(n--) { cin>>x; s.push(x); } while(!...
  • 设输入序列1、2、3、…、n经过作用后,输出序列中的第一个元素是n,则输出序列中的第i个输出元素是:1+(n-i) 分析过程如图:(这里将 n 值取 5,i值 取2) 倒序的元素i与正序的元素n-1相互对应。 由图分析得出,...
  • 如果,返回总的出栈次数,如果不能,返回0。序列的输入及输出都是从左往右。(输入输出序列皆为整数且没有重复的数字,如果一个数字在输入序列中没有出现,那么其在输出序列中也不会出现) 【输入形式】 第一行为...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 102,925
精华内容 41,170
关键字:

栈不能输出的序列怎么算