出栈序列相对入栈序列关系
出栈序列相对入栈序列关系
在数据结构的定义里，栈是只允许一端进行插入或删除操作的线性表。人们总结简化为后进先出原则。栈的定义给定以后引出了另一类问题——出栈序列问题。就是在给定一个入栈序列（如a1,a2…a n）的条件下，在进栈操作时，允许出栈操作，来判断一下哪些序列是可能的出栈序列，而哪些必不是出栈序列。当然，前提是要保证要求判断的序列里面的元素要与给定入栈序列里的元素一一映射。否则就没有再往下判断的必要了。
对于这类问题一般的方法是在本子上画表格模拟一个栈然后实际操作一下，看看哪些是可调度实现的，哪些是不可能实现的。这种方法是很不严谨的，而且
n 种工作量很大，对于一个具有n个元素的入栈序列，它的出栈序列有(1/(n+1))*C
2n
可能。如果n稍大一点，工作量会颇具规模。到这来，您也许会有点被忽悠了，其实给定一个如栈序列，a1,a2,……a n ，再给定出要判断的出栈队列a i ,a j , a k,……判断他们是否匹配，很简单，用一个大小为n的数组模拟栈，以a1,a2,……a n 做输入，对照着要判断的序列a i ,a j , a k,…… ，有目的的操作在线性时间内就可以完成。只是这种操作人工来说稍微麻烦一点罢了。
对于人工做判断，研究发现这类问题是具有一般规律的。在此先给出这一定律的定义，然后举几个常见的应用，最后给出证明。
这一定律是：在给定入栈顺序序列的前提下，对于其出栈序列里任意元素a n ，晚于其出栈且先于入栈的元素必须按入栈的逆序排列。
先后几个应用实例：
1.设a,b,c,d,e,f 以所给的次序进栈，若在进栈操作时，允许出栈
操作，则下面得不到的序列为：
A. fedcba
B. bcafed
C. dcefba
D. cabdef
答案是 D .因为 A. B. C 项都满足规律，但 D 项里a,b 晚于c 出栈且先于 c 入栈，它们的排列顺序应是ba。
2.元素a,b,c,d,e 依次进入初始为空的栈中，若元素进栈后可停
留，可出栈，直到所有元素都出栈，则在所有可能出栈序列中，以元素
d开头的序列个数是多少个？
这一问题是可以很方便用上面给的规律来解决。序列以元素d开头说明d
是第一个出栈的。a,b,c要晚于d出栈同时a,b,c对先于d入栈，所以根据上面的规律a,b,c,d的排列顺序只能是dcba。除了元素d 的前面e还可以有4个位置可取，所以答案是4种。
3.给定一个正整数元素序列1,2,3,…,99,100.允许进栈，退栈操
作交替进行，我们根据已给的规律很容易判别。
1,2，…，7,10,3,11,12,6，…，97,98,99,100不是出栈序列，因为7,3,6.不符合规律。
下面给出定律的证明。
假设给定一个元素序列a
1,a
2
,a
3
, …,a
n
（记为Sa）以所给的次序依次
进栈，在进栈操作时，允许出栈操作。则判断另一个已知序列元素一一映射序列记为S
b
可否成为原序列的充分必要条件是：
对于序列S
b 里的任意元素a
k
，相应于S
a
里排在其前面的且在S
b
里排
在其后面的所有元素按与Sa对应相反的顺序排列。
已知序列S
k , x
1
,x
2
…x
i
,x
n
(i∈I且1<=i<=n)
对于任意三个整数1<=i Ni 或xi>xj>xk 假设序列里有一元素xi，其右面的小于其元素值的元素不都严格递减 即存在j,k i X i k 可知这三个元素既不符合xi 必要性证明：对于Sa里的任意三个元素，ai,aj,ak，它们在Sa里的排列顺序是ai,aj,ak,如果在Sb里的排列顺序变为ak,ai,aj，假设序列Sb是Sa的出栈序列。 根据栈的性质，和ai,aj,ak三个元素分别在Sa和Sb里的位置关系克制，为ak在栈顶时，ai,aj一定在栈里，是aj比ai更靠近栈顶。根据Sb里ak,ai,aj的位置关系知Sk是先出栈的如果ak出栈后，ai先于aj 出栈，这与栈只允许在一端进行插入或删除的操作自相矛盾。 充分性证明：对于序列Sa我们只关心其序列里各元素的对应位置关系，不考虑其它属性。为表述方便我们把元素a1,a2,a3…an-1,an,对映抽象为1,2,3，…，n-1,n（数值越大，表示其排列越靠后，即入栈越晚）记为Sd。 对于序列Sb,x1,x2,x3,…,xn,里面的元素与Sd一一映射，且xi的下标值i的大小代表其在Sb的位置情况，数值越大越靠后，即出栈越晚。如果对于任意三个整数1<=i <1>当xi 1）假设xi,xj,xk相邻，即k-j=j-i=1 xi,xj,xk三个元素大小关系全排列有3！=6种，这里符合要求的有四种分别为 xi xi xi xi>xj,xi 因为x的值与Sd里面的整数是一一映射关系，而Sd里面的 整数是Sa里面相对位置上的元素是一一对应的。所以xi,xj,xk的大小关系就是他们所对应的，整数所对应的Sa里面的元素的位置关系。可根据以上分析可求得xi,xj,xk所间接对应到的Sa里元素的位置关系。以xi’,xj’,xk’表示其间接对应元素，可得以上四种情况分别的入栈顺序。而且我们都可以让他们经过栈后实现xi’,xj’,xk’的排列 xi’,xj’xk’对应出栈入栈操作方法Ixi’Oxi’Ixj’Oxj’Ixk’Oxk’ xi’,xk’xj’Ixi’Oxi’Ixk’Ixj’Oxj’Oxk’ xk’,xi’xj’Ixk’Ixi’Oxi’Ixj’Oxj’Oxk’ xj’,xi’xk’Ixj’Ixi’Oxi’Oxj’Ixk’Oxk’ 所以，如果xi 2）假设xi,xj,xk不都相邻 …xi…xj…xk… 在xi xi xi xk xj 它们的间接对应元素为 …xi’…xj’…xk’… …xi’…xk’…xj’… …xk’…xi’…xj’… …xj’…xi’…xk’… 在保证除xi’xj’xk’以外的元素正确调度的前提下，我们依然可以按 …Ixi’…Oxi’…Ixj’…Oxj’…Ixk’…Oxk’… …Ixi’…Oxi’…Ixj’…Oxj’…Ixk’…Oxk’… …Ixk’…Ixi’…Oxi’…Ixj’…Oxk’…Oxk’… …Ixj’…Ixi’…Oxi’…Oxj’…Ixk’…Oxk’… 的调度方法保证其实现…xi’…xj’…xk’的排列。 所以如果xi 2>当xi>xj>xk时（即，xi>max(xj,xk)，则xj>xk） 1）假设xi,xj,xk相邻，即k-1=j-i=1分别以xi’,xj’,xk’表示xi,xj,xk的间接对应元素，由xi>xj>xk可知它们的入栈顺序 是： Xk’xj’,xi’可以由Ixk’Ixj’Ixi’Oxi’Oxj’Oxk’来实现出栈序列按xi’,xj’,xk’排列。 所以知，如果xi>xj>xk且xixjxk相邻，可以调度其间接对应到Sa的元素，以固定顺序入栈得到xi’xj’xk’的出栈序列。 2）当xi,xj,xk不都相邻时 …xi…xj…xk… 在xi>xj>xk的前提下保证其它元素可正确调度，还可以按 …Ixk’…Ixj’…Ixi’…Oxi’…Oxj’…Oxk’… 得到…xi’…xj’…xk’的出栈序列。 所以，如果xi>xj>xi,不论xi,xj,xk相邻与否，都可以调度其间接对应到Sa内的元素，以固定顺序入栈，而得到…xi’… xj’…xk’…的出栈序列。 综合1,2可知对于已知的入栈序列到Sa，a1,a2, …an,序列Sb里面的元素与Sa一一映射如果Sb里的任意元素ak，相应于Sa里排在ak前面，且在Sb里排在ak后面的所有元素，按与在Sa里的相反顺序排列，就可以断定Sb里Sa的入栈序列。 综述可知，这是个充要条件。 出栈序列合法性研究与实现 姜华林;李立新;陈强 【期刊名称】《电脑知识与技术》 【年(卷),期】2013(000)007 【摘要】栈是一种非常重要且特殊的数据结构,任何递归和函数调用都离不开栈.研究n个元素的进栈与出栈性质是栈的主要研究内容.该文在出栈序列深入分析和研究的基础上,针对某一序列是否为合法出栈序列的问题,提出了一种基于三元素出栈序列索引的时间复杂度为O(n2)的新算法.该算法简单易懂并且比其他传统判断方法具有更高的效率.%A stack is a very important and special data structure. Any function call can not be separated from the stack. Research on the in-stack and the out-stack of n elements is a main content. The character of out-stack sequence is analyzed and re?searched in this paper and a new algorithm is proposed for judging a sequence whether it is a rational out-stack sequence. The al?gorithm is based on the three-element-index of out-stack sequence and its time complexity is O(n2). The algorithm is simple and easy to understand and more efficiency than the other traditional method. 【总页数】4页(1578-1581) 【关键词】栈;数据结构;出栈序列;三元素索引;算法 【作者】姜华林;李立新;陈强 【作者单位】遵义职业技术学院,贵州遵义563000;遵义职业技术学院,贵州遵义 563000;遵义职业技术学院,贵州遵义 563000 出栈序列相对入栈序列关系 在数据结构的定义里，栈是只允许一端进行插入或删除操作的线性表。人们总结简化为后进先出原则。栈的定义给定以后引出了另一类问题——出栈序列问题。就是在给定一个入栈序列（如a1,a2…a n）的条件下，在进栈操作时，允许出栈操作，来判断一下哪些序列是可能的出栈序列，而哪些必不是出栈序列。当然，前提是要保证要求判断的序列里面的元素要与给定入栈序列里的元素一一映射。否则就没有再往下判断的必要了。 对于这类问题一般的方法是在本子上画表格模拟一个栈然后实际操作一下，看看哪些是可调度实现的，哪些是不可能实现的。这种方法是很不严谨的，而且 n 种工作量很大，对于一个具有n个元素的入栈序列，它的出栈序列有(1/(n+1))*C 2n 可能。如果n稍大一点，工作量会颇具规模。到这来，您也许会有点被忽悠了，其实给定一个如栈序列，a1,a2,……a n ，再给定出要判断的出栈队列a i ,a j , a k,……判断他们是否匹配，很简单，用一个大小为n的数组模拟栈，以a1,a2,……a n 做输入，对照着要判断的序列a i ,a j , a k,…… ，有目的的操作在线性时间内就可以完成。只是这种操作人工来说稍微麻烦一点罢了。 对于人工做判断，研究发现这类问题是具有一般规律的。在此先给出这一定律的定义，然后举几个常见的应用，最后给出证明。 这一定律是：在给定入栈顺序序列的前提下，对于其出栈序列里任意元素a n ，晚于其出栈且先于入栈的元素必须按入栈的逆序排列。 先后几个应用实例： 1.设a,b,c,d,e,f 以所给的次序进栈，若在进栈操作时，允许出栈 操作，则下面得不到的序列为： A. fedcba B. bcafed C. dcefba D. cabdef 答案是 D .因为 A. B. C 项都满足规律，但 D 项里a,b 晚于c 出栈且先于 c 入栈，它们的排列顺序应是ba。 2.元素a,b,c,d,e 依次进入初始为空的栈中，若元素进栈后可停 留，可出栈，直到所有元素都出栈，则在所有可能出栈序列中，以元素 d开头的序列个数是多少个？ 这一问题是可以很方便用上面给的规律来解决。序列以元素d开头说明d 一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列?[4- ] 常规分析 首先，我们设f（n）=序列个数为n的出栈序列种数。同时，我们假定，从开始到栈第一次出到空为止，这段过程中出栈的序数最大的是k。特别地，如果栈直到整个过程结束时才空，则k=n 首次出空之前第一个出栈的序数k将1~n的序列分成两个序列，其中一个是1~k-1，序列个数为k-1，另外一个是k+1~n，序列个数是n-k。 此时，我们若把k视为确定一个序数，那么根据乘法原理，f（n）的问题就等价于——序列个数为k-1的出栈序列种数乘以序列个数为n - k的出栈序列种数，即选择k这个序数的f（n）=f（k-1）×f（n-k）。而k可以选1到n，所以再根据加法原理，将k取不同值的序列种数相加，得到的总序列种数为：f（n）=f （0）f（n-1）+f（1）f（n-2）+……+f（n-1）f（0）。 看到此处，再看看卡特兰数的递推式，答案不言而喻，即为f（n）=h（n）= C （2n,n）/（n+1）= c（2n,n）-c（2n,n+1）（n=0，1，2，……）。 最后，令f（0）=1，f（1）=1。 非常规分析 对于每一个数来说，必须进栈一次、出栈一次。我们把进栈设为状态‘1’，出栈设为状态‘0’。n个数的所有状态对应n个1和n个0组成的2n位二进制数。由于等待入栈的操作数按照1‥n的顺序排列、入栈的操作数b大于等于出栈的操作数a(a≤b)，因此输出序列的总数目=由左而右扫描由n个1和n个0组成的2n位二进制数，1的累计数不小于0的累计数的方案种数。 在2n位二进制数中填入n个1的方案数为c(2n,n),不填1的其余n位自动填0。从中减去不符合要求（由左而右扫描，0的累计数大于1的累计数）的方案数即为所求。 一种判断合法进出栈序列的方法 问题描述 假设我们有一组数字按从小到大的顺序执行进栈和出栈的操作，比如我们有数字0, 1, 2, 3, 4, 5, 6, 7, 8, 9。它们按照顺序混合执行push, pop操作。其中pop操作返回的数字组成一个序列。那么，当我们给定一个序列的时候，能否判断这个序列是可以通过这么一组push, pop操作形成呢？ 问题分析 对于这个问题，一开始确实有点不太好分析。虽然数字都是按照顺序入栈的，但是它们出栈的顺序却不确定。假设我们以一组数字0，1，2为例来看它们push, pop操作形成的序列。那么它们对应如下的一些情况： 1. push 0, pop 0, push 1, pop 1, push 2, pop 2 (0, 1, 2) 2. push 0, pop 0, push 1, push 2, pop 2, pop 1 (0, 2, 1) 3. push 0, push 1, pop 1, pop 0, push 2, pop 2 (1, 0, 2) 4. push 0, push 1, pop 1, push 2, pop 2, pop 0 (1, 2, 0) 5. push 0, push 1, push 2, pop 2, pop 1, pop 0 (2, 1, 0) 按照这里的分析，至少上面这些序列都是通过入栈出栈操作形成的合法序列。而对于上面这三个数字来说，它们所能够形成了所有排列有6个。针对上面的5个序列来看，有一个排列是不能生成的。这个序列是2, 0, 1。 那么对于这个不能生成的序列，它有什么特点呢？因为在这里，当2出栈的时候，在栈里它下面的元素必然都是比它小的元素。一旦这些比它小的元素压入栈之后并没有马上出栈，它们就只能等到上面这些大的元素出了之后才能出了。 而且这个规律还要一个比较有意思的递归特性。对于任何一个元素来说，当它进栈的时候，它下面的元素必然都比它小。因为我们前面所有元素都是按照从小到大的顺序进栈的。而出栈的时候呢，当这个大的元素出栈的时候，后面接着要出栈的元素里只要是原来它下面的元素，就必然一个比一个小。所以，我们也可以概括成这样，对于栈里任何一个出栈的元素来说，生成的序列里它后面所有比它小的元素必然构成一个递减的序列。所以，按照这个规律，我们可以来判断一个给定的序列是否为通过入栈出栈生成的。 Java代码 1.public static boolean validSequence(int[] a) { 2.for(int i = 0; i < a.length; i++) { 3.int cur = a[i]; 4.for(int j = i + 1; j < a.length; j++) { 5.if(a[j] < a[i]) { 6.if(a[j] > cur) return false; 7.else cur = a[j]; 8. } 9. } 10. } 11.return true; 12.} 这里的代码实现就是从一个序列里遍历每个元素，去看后面所有比它小的元素是否构成一个递减的序列，如果没有就返回false，否则返回true。这种实现比较简单，但是性能方面有一些值得改进的地方。它的时间复杂度为O(N^2)。因为对于某个元素来说，比如3，如果我们判断过后面所有比它小的元素0, 1, 2都是符合条件的。对于序列中3后面的元素，比如4来说，对于0, 1, 2的情况其实都不用再去判断了。同样，对于比3小的元素，我们这么遍历的时候都可以直接跳过去。 数据结构基础练习（栈和队列） 学号姓名蓝礼巍班级 . 一、选择题 1．有5个元素a,b,c,d,e依次进栈，允许任何时候出栈，则可能的出栈序列是 c 。 A．baecd B．dceab C．abedc D．aebcd 2．下列有关递归的叙述，不正确的是 b 。 A．在计算机系统内，执行递归函数是通过自动使用栈来实现的。 B．在时间和空间效率方面，递归算法比非递归算法好。 C．递归函数的求解过程分为递推（进栈）和回推（出栈）两个阶段。 D．在递归函数中必须有终止递归的条件。 3．栈和队列均属于哪一种逻辑结构 A 。 A．线性结构B．顺序结构C．非线性结构D．链表结构4．设输入元素为1、2、3、P和A，输入次序为123PA，元素经过栈后得到各种输出序列，则可以作为高级语言变量名的序列有 d 种。 A．4 B．5 C．6 D．7 5．一个队列的入队序列为a，b，c，d，则该队列的输出序列是 b 。 A．dcba B．abcd C．adcb D．cbda 6．在一个链式队列中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算是b 。 A. f->next=s; f=s; B. r->next=s; r=s; C. s->next=s; r=s; D. s->next=f; f=s; 7．如果5个元素出栈的顺序是1、2、3、4、5，则进栈的顺序可能是 c 。 A．3、5、4、1、2 B．1、4、5、3、2 C．5、4、1、3、2 D．2、4、3、1、5 8．若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为。 A．i B．n-i C．n-i+1 D．不确定 二、填空题 1．栈和队列是一种特殊的线性表，其特殊性体现在是运算受限线性表。设现有元素e1,e2,e3,e4,e5和e6依次进栈，若出栈的序列是e2,e4,e3,e6,e5,e1，则栈S的容量至少是 3 。 2．顺序循环队列中，设队头指针为front，队尾指针为rear，队中最多可有MAX个元素，采用少用一个存储单元的方法区分队满与队空问题，则元素入队列时队尾指针的变化为 Rear=(rear+1)%MAX ；元素出队列时队头指针的变化为fort=(fotr+1)%MAX ；队列中的元素个数为 (rear-fort+MAX)%MAX 。若则可用表示队满的判别条件，队空的判别条件仍然为 rear==fort 。 三、解答题 第3章栈与队列 一、单项选择题 1．元素A、Ｂ、C、D依次进顺序栈后，栈顶元素是，栈底元素是。 A．A B．B C．C D．D 2．经过以下栈运算后，x的值是。 InitStack(s)；Push(s,a)；Push(s,b)；Pop(s,x)；GetTop(s,x); A．a B．b C．1 D．0 3．已知一个栈的进栈序列是ABC，出栈序列为CBA，经过的栈操作是。 A．push,pop,push,pop,push,pop B．push,push,push,pop,pop,pop C．push,push,pop,pop,push,pop D．push,pop,push,push,pop,pop 4．设一个栈的输入序列为A、B、C、D，则借助一个栈所得到的序列是。 A．A,B,C,D B．D,C,B,A C．A,C,D,B D．D,A,B,C 5．一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是。 A．edcba B．decba C．dceab D．abcde 6．已知一个栈的进栈序列是1，2，3，……,n，其输出序列的第一个元素是i，则第j个出栈元素是。 A．i B．n-i C．j-i+1 D．不确定 7．已知一个栈的进栈序列是1，2，3，……，n，其输出序列是p1,p2,…,Pn，若p1=n，则pi的值。 A．i B．n-i C．n-i+1 D．不确定 8．设n个元素进栈序列是1，2，3，……，n，其输出序列是p 1,p 2 ,…,p n ，若p 1 =3, 则p 2 的值。 A．一定是2 B．一定是1 C．不可能是1 D．以上都不对 9．设n个元素进栈序列是p 1,p 2 ,…,p n ，其输出序列是1，2，3，……，n，若p 3 =1, 则p 1 的值。 A．可能是2 B．一定是1 C．不可能是2 D．不可能是3 10．设n个元素进栈序列是p 1,p 2 ,…,p n ，其输出序列是1，2，3，……，n，若 p 3=3,则p 1 的值。 A．可能是2 B．一定是2 C．不可能是1 D．一定是1 11．设n个元素进栈序列是p 1,p 2 ,…,p n ，其输出序列是1，2，3，……，n，若 p n =1,则p i (1≤i≤n-1)的值。 A．n-i+1 B．n-i C．i D．有多种可能 12．判定一个顺序栈S为空的条件为。 A．= = B．!= C．!= + D．= = + 13．判定一个顺序栈S为栈满的条件是。 A． = B．= = C．D．!= 14．链栈与顺序栈相比有一个明显的优点，即。 A．插入操作方便B．通常不会出现栈满的情况C．不会出现栈空的情况D．删除操作更加方便15．最不适合用作链栈的链表是。 A．只有表头指针没有表尾指针的循环双链表 第3章栈和队列 一、选择题 1.栈结构通常采用的两种存储结构是（A ）。 A、顺序存储结构和链表存储结构 B、散列和索引方式 C、链表存储结构和数组 D、线性链表结构和非线性存储结构 2.设栈ST 用顺序存储结构表示，则栈ST 为空的条件是（ B ） A、ST.top-ST.base<>0 B、ST.top-ST.base==0 C、ST.top-ST.base<>n D、ST.top-ST.base==n 3.向一个栈顶指针为HS 的链栈中插入一个s 结点时，则执行（ C ） A、HS->next=s; B、s->next=HS->next；HS->next=s; C、s->next=HS；HS=s; D、s->next=HS；HS=HS->next; 4.从一个栈顶指针为HS 的链栈中删除一个结点，用x 保存被删除结点的值，则执行（ C） A 、x=HS；HS=HS->next; B 、HS=HS->next；x=HS->data; C 、x=HS->data；HS=HS->next; D 、s->next=Hs；Hs=HS->next; 5.表达式a*(b+c)-d 的后缀表达式为（ B ） A、abcdd+- B、abc+*d- C、abc*+d- D、-+*abcd 6.中缀表达式A-（B+C/D）*E 的后缀形式是（ D ） A、AB-C+D/E* B、ABC+D/E* C、ABCD/E*+- D、ABCD/+E*- 7.一个队列的入列序列是1，2，3，4，则队列的输出序列是（ B ） A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，1 8.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队 列为空的条件是（） A、Q.rear-Q.front==n B、Q.rear-Q.front-1==n C、Q.front==Q.rear D、Q.front==Q.rear+1 9.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队 列为满的条件是（） A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 10.若在一个大小为6 的数组上实现循环队列，且当前rear 和front 的值分别为0 和3，当从队列中删除一个元素， 再加入两个元素后，rear 和front 的值分别为（） A、1，5 B、2, 4 C、4，2 D、5，1 11.用单链表表示的链式队列的队头在链表的（）位置 A、链头 B、链尾 C、链中 12.判定一个链队列Q（最多元素为n 个）为空的条件是（） A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 13.在链队列Q 中，插入s 所指结点需顺序执行的指令是（） A 、Q.front->next=s；f=s; B 、Q.rear->next=s；Q.rear=s; C 、s->next=Q.rear；Q.rear=s; D 、s->next=Q.front；Q.front=s; 14.在一个链队列Q 中，删除一个结点需要执行的指令是（） A、Q.rear=Q.front->next; B、Q.rear->next=Q.rear->next->next; C、Q.front->next=Q.front->next->next; D、Q.front=Q.rear->next; 入入入出出出 A B C C B A CBA 入入出入出出 A B B C C A BCA 入入出出入出 A B B A C C BAC 入出入入出出 A A B C C B ACB 入出入出入出 A A B B C C ABC 面对类似的问题,只需要考虑”入”,”出”的问题.每次只需要修改”入”,”出”的相对位置就行了. 用这种方法可以最快的找到每个序列,而且不容易出错. 至于超过4个元素的则比较麻烦,不会考试.当然会有另外一种题型.(4元素的出栈全序列)我们有一下解法: 历史真题: 已知入栈序列为{A,B,C,D,E},请判断下列序列{B,E,C,D,A}和{C,D,E,A,B}为出栈序列的可能性 首先入栈序列已知. (1){B,E,C,D,A} 因为B比A先出栈,所以AB之间没有出栈,B后面必定有一个出栈 可知序列: AB出 观察出栈顺序 可知序列: AB出CDE 因为E在B后出栈,所以CDE之间没有出栈,所以C在D前出栈是不可能的所以这个出栈序列不存在 (2){C,D,E,A,B} 因为C先出栈 可知序列: ABC出 观察出栈顺序: 可知序列: ABC出D出E出 因为AB之间没有出栈,所以AB出栈顺序必定为BA. 所以这个出栈序列不存在 2.编号为1,2,3,4的四辆列车,按照顺序开进一个栈式结构的站台.请问____不可能是列车的出站顺序? A.1,2,3,4 B.3,4,1,2 C.4,3,2,1 D.1,3,4,2 A.1出2出3出4出 B.123出4出出出(3421)故,选B C.1234出出出出 D.1出23出4出出 4元素的出栈全序列 入入入入出出出出 A B C D D C B A DCBA 入入入出入出出出 A B C C D D B A CDBA 入入入出出入出出 A B C C B D D A CBDA 入入入出出出入出 A B C C B A D D CBAD 入入出入入出出出 A B B C D D C A BDCA 入入出出入入出出 A B B A C D D C BADC 入出入入入出出出 A A B C D D C B ADCB 入入出入出入出出 A B B C C D D A BCDA 入入出出入出入出 A B B A C C D D BACD 入入出入出出入出 A B B C C A D D BCAD 入出入出入入出出 A A B B C D D C ABDC 入出入出入出入出 A A B B C C D D ABCD 1 2 3 回专题模式 回学习阶段模式 【题目名称、来源】 【问题背景】栈是计算机中经典的数据结构，简单的说，栈就是限制在一端进行插入删除操作的线性表。 栈有两种最重要的操作，即pop （从栈顶弹出一个元素）和push （将一个元素进栈）。 栈的重要性不言自明，任何一门数据结构的课程都会介绍栈。宁宁同学在复习栈的基本概念时，想到了一个书上没有讲过的问题，而他自己无法给出答案，所以需要你的帮忙。 【问题描述】 输出序列 尾端 头端 操作数序列 头端 栈A 宁宁考虑的是这样一个问题：一个操作数序列，从1，2，一直到n （图示为1到3的情况），栈A 的深度大于n 。 现在可以进行两种操作， 1.将一个数，从操作数序列的头端移到栈的头端（对应数据结构栈的push 操作） 2. 将一个数，从栈的头端移到输出序列的尾端（对应数据结构栈的pop 操作） 使用这两种操作，由一个操作数序列就可以得到一系列的输出序列，下图所示为由1 2 3生成序列2 3 1的过程。（原始状态如上图所示） 你的程序将对给定的n ，计算并输出由操作数序列1，2，…，n 经过操作可能得到的输出序列的总数。 【输入格式】 输入文件只含一个整数n （1≤n ≤18） 【输出格式】 1 2 3 1 2 3 1 3 2 1 1 3 2 2 3 2 3 1 输出文件只有一行，即可能输出序列的总数目 【输入样例】 3 【输出样例】 5 【所属专题】 【适合学习阶段】 【解题思路】 问题分析：方法一、递归模拟出栈顺序。方法二、找递推式，可知出栈序列总数为catalan 数 方法二： 设f(n)表示有n 节车厢的出站的方法数 那么,第1节车厢显然有进栈和不进栈两种方法. 不进栈的方法为f(n-1) 进栈的方法数,可以归结为元素1第i 次出栈的所有可能性。 元素1排列在第i 个位置，那么将整个序列分裂为2~i ，1，i+1~n 两个部分。显然 方法数为两个部分之积，如下： 这种方法可以说是动态规划，但是也可以说是利用了组合数学中的加法原理、程法原理。 方法三：catalan 数 设某个数字i 进栈的为1，出栈为0，不入栈直接到达目标为10，则很明显对于出栈序列所对应的01串中，从左到右扫描的时候，1的个数总是不小于0的个数，所以问题等同于catalan 数。 存储结构： 【测试数据】 【源程序】 递归程序 program StackNumber; var st:array[1..3,0..100] of integer; count,n,i:integer; ∑=--n f i n f i f 21 )0(),(*)1(其中∑∑=--==>=--+-=n n f i n f i f n f f i n f i f n f n f 121 )0(),(*)1()(1 )0(),(*)1()1()(其中其中所以， 回文序列判断实验报告 系别：通信工程 班级： 0905班 学号： 18 号 1．实验目的：熟悉栈的各项操作 2．实验内容： 利用栈的操作完成读入的一个以@结尾的字符序列是否是回文序列的判断. 回文序列即正读与反读都一样的字符序列; 例如:123&321@是; 123&4321@、123&312@不是 算法思想：从键盘上读取一个字符，同时存储在顺序栈与链队列之中，直到字符序列的最后一个字符为@停止输入，因为要满足特定的要求：序列1&序列2，故设置夜歌标记量falg=1,判断输入的元素个数是否为奇数个，若为偶数个则令flag=0，若为奇数个继续判断栈的中间元素是否为&,若不是则令flag=0，若是，将栈和队列中的元素依次出列，判断是否相等，若不相等则令flag=0,最后将flag的值返回给主函数，若flag被修改为0说明不是回文序列，否则反之！！ 判断回文序列的流程图： 3．实验感想与体会 通过本次的上机，对栈的各项基本操作都有了更好的掌握，同时明白了一些小的细节问题可能会影响到整个程序的正确的运行，本次的实验我通过了运用栈和队列，可以说对队列的一些基本的操作也得以了巩固和提高！更加体会到，自己写程序上机操作的重要性，它要比课本上学的要多得多！ 4．附录（源代码及运行图） #include #define MAX 100 typedef struct//栈结构体 { char e[MAX]; int top; }SeqStack; typedef struct NODE//队列结构体 { char d; struct NODE *next; }LinkQN; typedef struct//封装头指针为指针 { LinkQN *front; LinkQN *rear; }LinkQ; InitS(SeqStack *s)//初始化顺序栈 { s->top=-1; } int push(SeqStack *s,char ch)//入栈 { if(s->top==MAX-1) return(0); s->top++; s->e[s->top]=ch; return(1); } int pop(SeqStack *s,char *x)//出栈 { if(s->top==-1) return(0); *x=s->e[s->top]; s->top--; return(1); } void InitQ(LinkQ *q)//链队列初始化 { q->front=(LinkQN *)malloc(sizeof(LinkQN)); if(!q->front) { printf("分配空间失败!"); 第五次实验报告—— 顺序栈、链栈的插入和删除一需求分析 1、在演示程序中，出现的元素以数字出现定义为int型， 2、演示程序在计算机终端上，用户在键盘上输入演示程序中规定的运算命令，相应的输入数据和运算结果显示在终端上 3、顺序栈的程序执行的命令包括如下： （1）定义结构体 （2）顺序栈的初始化及创建 （3）元素的插入 （4）元素的删除 （5）顺序栈的打印结果 3、链栈的程序执行的命令包括如下： （1）定义结构体 （2）链栈的初始化及创建 （3）元素的插入 （4）元素的删除 （5）链栈的打印结果 二概要设计 1、顺序栈可能需要用到有序表的抽象数据类型定义： ADT List{ 数据对象:D={ai|ai∈ElemL, i=1,2,...,n, n≥0} 数据关系:R1={ Status Pop(SqStack &S) 操作结果：删除栈顶元素 }ADT List； 2、链栈可能需要用到有序表的抽象数据类型定义： ADT List{ 数据对象:D={ai|ai∈ElemL, i=1,2,...,n, n≥0} 数据关系:R1={ 栈是一种常见的数据结构，有许多关于栈的问题，其中之一就是统计元素可能的出栈序列。具体说，就是给定n个元素，依次通过一个栈，求可能的出栈序列的个数。 如果我们用直接模拟的方法，当n较大时会很费时间； 例如动态规划。令f[i,j]表示栈内有i个元素且栈外有j个元素还未进栈，那么以进栈还是出栈为决策就马上得到了转移方程f[i,j]=f[i-1,j]+f[i+1,j-1]。如此一来，很多重复的计算得以免去，效率大幅提高（时间复杂度为指数级，大概为N^２级的算法）。 另一种方法是利用组合数学求出栈序列个数，得到公式 下面我们来看一种图形化的方法证明这个等式，很容易理解的。 我们把对n个元素的n次进栈和n次出栈理解为在一个n * n的方格中向右走n次（代表进栈），向上走n次（代表出栈）。由于出栈次数不能大于进栈次数，我们可以得到这样一个方格： 每次沿着实线走，所以，只要求出从方格左下角到右上角路径的个数即可。 我们把表格补全，考虑每一条不合法的路径，如 在这条路径上，必然有一个地方连续两次向上，即从图上蓝点处开始，而且这个点必然在如图所示的绿线上。我们以这个点为起点，把到左上角整条路经取反，也就是对称上去，得到一条新路径，但是超出了表格。我们知道，这条路径包括n + 1次向上和n – 1次向下，也就是在一个(n + 1) * (n - 1)的方格中。由此我们知道，一条不合法路径必然对应一个(n + 1) * (n - 1)方格中的路径。同样地，对于(n + 1) * (n - 1)方格中任意一条路径，以这条路径与绿线的第一个交点为起点到方格的右上方全部取反，即可得到一个在n * n方格中的不合法路径。 若按教科书3.1.1节中图(b)所示铁道进行车厢调度（注意：两侧铁道均为单向行驶道），则请回答： (1) 如果进站的车厢序列为123，则可能得到的出站车厢序列是什么 (2) 如果进站的车厢序列为123456，则能否得到435612和135426的出站序列，并请说明为什么不能得到或者如何得到（即写出以‘S’表示进栈和以‘X’表示出栈的栈操作序列）。 解：(1) 123 231 321 213 132 (2) 可以得到135426的出站序列，但不能得到435612的出站序列。因为4356出站说明12已经在栈中，1不可能先于2出栈。 简述栈和线性表的差别。 解：线性表是具有相同特性的数据元素的一个有限序列。栈是限定仅在表尾进行插入或删除操作的线性表。 写出下列程序段的输出结果（栈的元素类型SElemType为char）。 void main() { Stack S; char x,y; InitStack(S); x= ‘c’; y= ‘k’; Push(S,x); Push(S, ‘a’); Push(S,y); Pop(S,x); Push(S, ‘t’); Push(S,x); Pop(S,x); Push(S, ‘s’); while(!StackEmpty(S)) { Pop(S,y); printf(y); } printf(x); } 解：stack 简述以下算法的功能（栈的元素类型SElemType为int）。 (1) status algo1(Stack S) { int i,n,A[255]; n=0; while(!StackEmpty(S)) { n++; Pop(S,A[n]); } for(i=1;i<=n;i++) Push(S,A[i]); } (2) status algo2(Stack S,int e) { Stack T; int d; InitStack(T); while(!StackEmpty(S)){ Pop(S,d); if(d!=e) Push(T,d); } while(!StackEmpty(T)){ Pop(T,d); 习题3 栈和队列 3.1 单项选择题 1. 一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是__C__。 A. edcba B. decba C. dceab D. abcde 2. 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为__C__。 A. i B. n=i C. n-i+1 D. 不确定 3. 栈结构通常采用的两种存储结构是__A__。 A. 顺序存储结构和链式存储结构 B.散列方式和索引方式 C.链表存储结构和数组 D.线性存储结构和非线性存储结构 4. 判定一个顺序栈ST（最多元素为m0）为空的条件是_B___。 A. top !=0 B. top= =0 C. top !=m0 D. top= =m0-1 5. 判定一个顺序栈ST（最多元素为m0）为栈满的条件是_D___。 A. top！=0 B. top= =0 C. top！=m0 D. top= =m0-1 6. 栈的特点是_B___，队列的特点是__A _。 A. 先进先出 B. 先进后出 7. 向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行__C __。 (不带空的头结点) A.HS—＞next=s; B. s—＞next= HS—＞next; HS—＞next=s; C. s—＞next= HS; HS=s; D. s—＞next= HS; HS= HS—＞next; 8. 从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行_B_ __。(不带空的头结点) A. x=HS; HS= HS—＞next; B. x=HS—＞data; C. HS= HS—＞next; x=HS—＞data; D. x=HS—＞data; HS= HS—＞next; 9. 一个队列的数据入列序列是1，2，3，4，则队列的出队时输出序列是___C_ 。 A. 4，3，2，1 B. 1，2，3，4 C. 1，4，3，2 D. 3，2，4，1 10. 判定一个循环队列QU（最多元素为m0）为空的条件是_C___。 A. rear - front= =m0 B. rear-front-1= =m0 C. front= = rear D. front= = rear+1 11. 判定一个循环队列QU（最多元素为m0, m0= =Maxsize-1）为满队列的条件是__A__。 A. ((rear- front)+ Maxsize)% Maxsize = =m0 B. rear-front-1= =m0 C. front= =rear D. front= = rear+1 12. 循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是_A___。 A. (rear-front+m)%m B. rear-front+1 第三章栈和队列 一选择题 1. 对于栈操作数据的原则是（B ）。 A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 2. 在作进栈运算时,应先判别栈是否( ①B ),在作退栈运算时应先判别栈是否( ②A )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③B )。 为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的( ④ D )分别设在这片内存空间的两端,这样,当( ⑤C )时，才产生上溢。①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 ④: A. 长度 B. 深度 C. 栈顶 D. 栈底 ⑤: A. 两个栈的栈顶同时到达栈空间的中心点. B. 其中一个栈的栈顶到达栈空间的中心点. C. 两个栈的栈顶在栈空间的某一位置相遇. D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底. 3. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ B ）。 A. 不确定 B. n-i+1 C. i D. n-i 4. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（ D ）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的 5. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，p N,若p N是n，则p i是( D )。 A. i B. n-i C. n-i+1 D. 不确定 6. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（C ） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 7. 设栈的输入序列是1，2，3，4,则（D ）不可能是其出栈序列。 A. 1，2，4，3， B. 2，1，3，4， C. 1，4，3，2， D. 4，3，1，2， E. 3，2，1，4， 8. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（B ）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 9. 设一个栈的输入序列是1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（D ）。 A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 4 10. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是（ D ）。 A. a，c，b，d B. b, c，d，a C. c, d，b, a D. d, c，a，b 11. 设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作,则下面得不到的序列为（D ）。 A．fedcba B. bcafed C. dcefba D. cabdef 12. 设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是( C )。 A．XYZ B. YZX C. ZXY D. ZYX 13. 输入序列为ABC，可以变为CBA时，经过的栈操作为（B ） A.push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop C.push,push,pop,pop,push,pop D.push,pop,push,push,pop,pop 15. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（B ）。 A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D.top[1]=top[2] 3.1 若按教科书3.1.1节中图3.1(b)所示铁道进行车厢调度（注意：两侧铁道均为单向行驶道），则请回答： (1) 如果进站的车厢序列为123，则可能得到的出站车厢序列是什么？ (2) 如果进站的车厢序列为123456，则能否得到435612和135426的出站序列，并请说明为什么不能得到或者如何得到（即写出以‘S’表示进栈和以‘X’表示出栈的栈操作序列）。 解：(1) 123 231 321 213 132 (2) 可以得到135426的出站序列，但不能得到435612的出站序列。因为4356出站说明12已经在栈中，1不可能先于2出栈。 3.2 简述栈和线性表的差别。 解：线性表是具有相同特性的数据元素的一个有限序列。栈是限定仅在表尾进行插入或删除操作的线性表。 3.3 写出下列程序段的输出结果（栈的元素类型SElemType为char）。 void main() { Stack S; char x,y; InitStack(S); x= ‘c’; y= ‘k’; Push(S,x); Push(S, ‘a’); Push(S,y); Pop(S,x); Push(S, ‘t’); Push(S,x); Pop(S,x); Push(S, ‘s’); while(!StackEmpty(S)) { Pop(S,y); printf(y); } printf(x); } 解：stack 3.4 简述以下算法的功能（栈的元素类型SElemType为int）。 (1) status algo1(Stack S) { int i,n,A[255]; n=0; while(!StackEmpty(S)) { n++; Pop(S,A[n]); } for(i=1;i<=n;i++) Push(S,A[i]); } (2) status algo2(Stack S,int e) { Stack T; int d; InitStack(T); while(!StackEmpty(S)){ Pop(S,d); if(d!=e) Push(T,d); } while(!StackEmpty(T)){ Pop(T,d); 第三章栈和队列作业 1、若按教材P44页图 3.1（b）所示铁道进行车厢调度（注意： 两侧铁道均为xx道），则请回答： （1）如果进站的车厢序列为123，则可能得到的出站车厢序列是什么？ （2）如果进站的车厢序列为123456，则能否得到435612和135426的出站序列，并请说明为什么不能得到或者如何得到？（写出进栈和出栈的栈操作序列）。 123、132、 213、231、321 输入序列为123456，不能得出435612，其理由是，输出序列最后两元素是12，前面4个元素 （4356）得到后，栈中元素剩12，且2在栈顶，不可能栈底元素1在栈顶元素2之前出栈。 得到135426的过程如下：1入栈并出栈，得到部分输出序列1；然后2和3入栈，3出栈，部分输出序列变为：13；接着4和5入栈，5，4和2依次出栈，部分输出序列变为13542；最后6入栈并退栈，得最终结果135426。 2、试证明： 若借助栈由输入序列 1、2……n得到的输出序列为p 1、p 2……p n(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形： 存在着，i〈j〈k使p j p j的情况，则说明要将p j压到p i之上，也就是在p j出栈之后p i才能出栈。这就说明，对于i出栈序列合法性研究与实现
出栈序列相对入栈序列关系
一个栈进栈序列为1,2,3,…,n,有多少个不同的出栈序列
42.一种判断合法进出栈序列的方法
数据结构基础练习(栈和队列)
数据结构第3章栈与队列习题
(完整版)《数据结构》习题集：第3章栈和队列
出入栈序列问题(简单分析)
出栈序列统计
回文序列判断(运用栈以及队列完成)
数据结构栈的基本操作,进栈,出栈
出栈序列与卡特兰数
栈和队列答案
习题三 栈和队列
第三章 栈和队列
栈和队列答案
第3章栈和队列 作业(参考答案)