-
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 543612B453126
C 346521
D 234156
分析:
C 65比34先入 后出没有逆序 错误
C更多相关内容 -
数据结构 栈 判断栈的合法输出序列
2021-03-23 00:04:54判断合法栈的输出序列方法:对于相邻的两个数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; }
如果有错误请大佬指出!感谢!
-
一个栈的输入序列是12345,则栈的输出序列有哪几种?
2021-05-23 06:49:51序列个数太多,以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
扩展资料:
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入栈... -
判断一个序列是否为栈的有效输出序列
2020-03-30 21:59:02栈的实际应用—判断一个序列是否为栈的有效输出序列 对于数据结构学科的初学者,栈的构建是很重要的知识,判断一个栈是否为有效输出序列是其中重要的题目。笔者整理了三种C++代码,其核心编程思想大致相同,希望能对... -
【栈的应用】输出栈的所有合法输出序列
2020-03-28 22:38:12以123为例,假如123在一个队列里,输入到中间栈,通过中间栈输出到右边队列中(这里用队列是为了方便输出,用数组储存也行) 我们分析一下中间的过程: 假如1已经入栈,这个时候有两种可能,要么中间栈栈顶的数据... -
数据结构-栈的可能的输出的序列个数
2019-11-06 11:44:18把可能的输出按最后一个元素分为n类 以k为例 比k小的元素肯定在k之前输出,...对于k来说,总的合法的输出序列个数就是f(k-1)*f(n-k) 双端队列 这人认为这个数据结构很bug。基本就是像一根管子,两端都可以进出 ... -
判断一个数列是否是栈的有效输出序列
2020-03-28 21:09:57如果能,则为有效输出,返回总的出栈次数,如果不能,则为无效输出,返回0。序列的输入及输出都是从左往右。 1、输入输出序列皆为正整数,可能有重复的数字 2、如果一个数字在输入序列中没有出现,但在输出序列中... -
一个栈的入栈序列是 a,b,c,d,e,则栈的不可能的输出序列是( ) 。
2021-10-28 20:24:25一个栈的入栈序列是 a,b,c,d,e,则栈的不可能的输出序列是( ) 。 a) edcba b) decba c)dceab d) abcde 堆栈讲究先进后出,后进先出, 边进边出 选项1是abcde先入栈,然后依次出栈,-----》edcba 选项2是abcd先依次... -
判断栈的输出序列是否正确
2020-05-12 11:20:42// 数字按照 1-n的顺序进栈,给定输出序列,判断该序列是否正确 // 个人认为用一个栈来模拟出栈是比较合适的 //用队列来存储给定的输出序列 //用栈来模拟 #include<iostream> #include<stdlib.h> #... -
结合实例理解栈的入栈序列1,2,3,4,5,则栈的输出序列是()问题
2021-10-17 21:34:10理解一个栈的入栈序列 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
2016-08-11 15:30:03hadoop2面试题 -判断一个序列是不是栈的输出序列.pdf -
判断栈的输出序列是否合法
2021-01-18 21:50:30判断栈的输出序列是否合法问题简述大概需要用的元素代码 、 问题简述 一个最多可以存储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就不可能是该压栈序列的弹出序列。(注意:这两个序列的长度是相等的) 【分析】 这道题考察栈混洗的判断,选择题... -
判断一个序列 是不栈的输出判断一个序列
2017-05-29 10:18:07队列:先进先出判断一个序列 是不栈的输出判断一个序列 题目描述:输入两个整数序列。其中一个序列表示栈的push顺序,判断另一个序列有没有可能是对应的pop顺序。为了简单起见,我们假设push序列的任意两个整数都是... -
判断一个数列是否是栈的输出序列
2020-10-16 22:07:35如果能,返回总的出栈次数,如果不能,返回0。序列的输入及输出都是从左往右。(输入输出序列皆为整数且没有重复的数字,如果一个数字在输入序列中没有出现,那么其在输出序列中也不会出现) 1.2 输入形式 第一... -
一个栈的入栈序列是 a,b,c,d,e,则栈的不可能的输出序列是( )
2021-03-12 19:38:54一个栈的入栈序列是 a,b,c,d,e,则栈的不可能的输出序列是( ) 。 a) edcba b) decba c) dceab d) abcde 堆栈讲究先进后出,后进先出 选项1是abcde先入栈,然后依次出栈,正好是edcba 选项2是abcd先依次入栈,然后d... -
一个栈输入序列为1,2,3,4,5,则下列序列中不可能是栈的输出序列是?
2020-02-01 15:09:45 -
关于栈的反向输出整数序列。
2020-03-27 12:43:08要求反向输出这个正整数序列。 要求定义一个栈来实现这个程序的功能。 输入 一个整数序列,每个数之间以空格隔开,非负整数,只含 正整数 和 0 。-1 表示输入结束。 输出 反向输出输入文件中的整数序列。 提示: 在... -
一道栈的输入输出序列问题
2013-08-06 09:39:26一个栈输入序列为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进来的时候... -
数据结构考研笔记之栈和队列(三)输出序列之出栈顺序
2020-10-10 10:34:18输出序列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个输出元素是
2020-03-16 21:22:52设输入序列1、2、3、…、n经过栈作用后,输出序列中的第一个元素是n,则输出序列中的第i个输出元素是:1+(n-i) 分析过程如图:(这里将 n 值取 5,i值 取2) 倒序的元素i与正序的元素n-1相互对应。 由图分析得出,... -
判断一个序列是否是栈的输出序列(原理和源码(C语言))
2022-03-17 19:28:14如果能,返回总的出栈次数,如果不能,返回0。序列的输入及输出都是从左往右。(输入输出序列皆为整数且没有重复的数字,如果一个数字在输入序列中没有出现,那么其在输出序列中也不会出现) 【输入形式】 第一行为...