输出出栈序列研究

王文龙

(喀什师范学院 信息工程技术系 新疆 喀什 844000)



输出出栈序列研究

王文龙

(喀什师范学院 信息工程技术系 新疆 喀什 844000)

在栈大小不受限制和受限制两种情况下，给定入栈序列(1, 2, …,n)，分析出栈序列应满足的性质，并据此给出基于穷举法和直接后续法的输出出栈序列的算法及程序实现.算法较直观且易于理解，程序均经过测试，输出正确.

栈； 出栈序列； 直接后续法； 算法； 程序

0 引言

栈是限定仅在表尾端进行插入或删除操作的特殊线性表，具有后进先出的特性，这种特性使得栈有着十分广泛的应用.在文献[1-9]中，对给定一个入栈序列，求出栈序列数量以及如何输出全部出栈序列等问题进行了研究，得出了相应的研究结果.然而，以上研究结果均基于一个前提：栈的大小是不受限制的，即栈的大小大于等于入栈序列的长度.而在某些情况下，栈的大小会受到限制，即栈的大小小于入栈序列的长度，此时有关栈的入栈、出栈问题会发生变化.因此，本文在栈大小不受限制和受限制两种情况下，对输出全部出栈序列的问题进行分析研究，并给出了相应的算法和程序实现.

1 出栈序列性质

为方便分析，将研究的问题描述为给定入栈序列(1,2, …,n)，输出全部出栈序列.当栈大小不受限制时，依据栈的特点，较容易得出出栈序列应该满足的性质.

性质1当栈大小不受限制时，序列a1a2…an是(1,2, …,n)的一个全排列, 则a1a2…an为出栈序列的充要条件是对于任意的ai, 在它后面的且比它小的数是降序排列的.

当栈的大小受限制时，即栈的大小k小于入栈序列长度n时，出栈序列首先需要满足性质1，然后考虑栈大小受限对出栈序列的要求.例如有长度n=6的入栈序列123456，栈的大小k=4，此时出栈序列的第一位不能超过元素4，即出栈序列第一位小于等于4，不能大于4，第二位小于等于5，不能大于5.一般情况下，第一位小于等于k，第二位小于等于k+1，依次类推，直到出栈序列第n-k位小于等于n-1.

性质2当栈的大小受限制时，即栈的大小k小于入栈序列长度n时，序列a1a2…an是(1,2, …,n)的一个全排列, 则a1a2…an为出栈序列的充要条件是满足性质1并且序列的第j位小于等于k+j-1.

2 栈大小不受限制时输出全部出栈序列

要输出全部出栈序列，可采用穷举法将入栈序列进行全排列，然后根据出栈序列需要满足的性质，将不满足的序列排除，剩余的即为出栈序列.此方法需要给出入栈序列的全排列，较为普遍的方法是采用字典序法.

算法1初始序列12…n，当前序列a1a2…an.

(1) 从a1a2…an的右端开始，找出第一个比右边数字小的数字的序号i.若无法找到这样的i，则结束.

(2) 在ai的右边的数字中，从右端开始，找出第一个比ai大的数的序号j.

(3) 交换ai和aj.

(4) 将ai以后的所有数倒置，得到一个新的序列.

(5) 判断该序列是否满足出栈序列的性质1，若满足则输出该序列，转(1).

程序如下：#include "iostream.h"

#include "string.h"

void fx(char a[],int i,int j)

{ int k; char tem;

for(k=i;k<=(i+j)/2;k++)

{ tem=a[k]; a[k]=a[i+j-k]; a[i+j-k]=tem; } }

int pd(char a[],int n)

{ int u,v,w,flag=1;

for(u=0;u<=n-2;u++)

for(v=u+1;v<=n-1;v++)

for(w=v+1;w<=n;w++)

if((a[v]

return flag; }

void main()

{ int i,j,len,tag=1,count=1;char a[10],tem;

cout<<"please input stack:"<>a; cout<

while(tag)

{ for(i=len;i>0;i--)

if(a[i-1]

if(i-1<0 ) tag=0;

else { for(j=len;j>i;j--)

if(a[i-1]

tem=a[i-1]; a[i-1]=a[j]; a[j]=tem; fx(a,i,len);

if(pd(a,len)) { if(count%5==0) cout<

count++;cout<

不难发现，此算法效率不高，例如当前出栈序列为136542，按算法1，将3和4互换，得到146532，然后将6532倒置，得到下一个序列142356，再判断是否是出栈序列，由于4后面比4小的数有2和3，然而是升序，因此它不是出栈序列.继续算法1，依次可以得到142365，142536，142563，142635，142653，143256，只有143256是出栈序列，142356，142365，142536，142563，142635，142653都不是出栈序列，原因均为4后面比4小的数有2和3，然而都是升序.

为提高效率，可采用直接后续法，做如下考虑：在将136542中的3和4交换后，得到146532，由于3和2均小于4，因此不直接将6532倒置，而将32当作整体再倒置，得到143256.从而从出栈序列136542直接产生后续的出栈序列143256，而避免产生中间的非出栈序列.

算法2初始序列12…n，当前序列a1a2…an.

(1) 从出栈序列a1a2…an的右端开始，找出第一个比右边数字小的数字的序号i.若无法找到这样的i，则结束.

(2) 在ai的右边的数字中，从右端开始，找出第一个比ai大的数的序号j.

(3) 交换ai和aj.

(4) 将ai+1到aj-1的数倒置.

(5) 将ai+1及其后所有数向左环移j-i-1位，得到下一个出栈序列并输出，转(1).

程序如下：#include "iostream.h"

#include "string.h"

void px(char b[],int sl)

{ int i,j,k; char tem;

for(i=0;i

{k=i;

for(j=i+1;j

if(b[j]

if(k!=i) { tem=b[i]; b[i]=b[k]; b[k]=tem; } } }

void main()

{ int i,j,k,len,tag=1,count=1; char a[10],b[10],tem;

cout<<"please input stack:"<>a; cout<

while(tag)

{ for(i=len;i>0;i--)

if(a[i-1]

if(i-1<0) tag=0;

else { for(j=len;j>i;j--)

if(a[i-1]

tem=a[i-1]; a[i-1]=a[j]; a[j]=tem;

for(k=i;k

b[k]=′′;

for(k=0;k<=len-j+1;k++) a[i+k]=a[j+k];

px(b,j-i);

for(k=0;k

a[i+len-j+1+k]=′′;

if(count%5==0) cout<

count++; cout<

3 栈大小受限制时输出全部出栈序列

当栈大小受限制时，要输出全部出栈序列，可以采用穷举法将入栈序列进行全排列，然后根据性质2要求，将不满足的序列排除，剩余的即为出栈序列.此方法可以参考算法1，在算法1的基础上增加对序列第j位是否小于等于k+j-1的判断.

算法3栈大小为k，初始序列为12…n，当前序列为a1a2…an.

(1) 从a1a2…an的右端开始，找出第一个比右边数字小的数字的序号i.若无法找到这样的i，则结束.

(2) 在ai的右边的数字中，从右端开始，找出第一个比ai大的数的序号j.

(3) 交换ai和aj.

(4) 将ai以后的所有数倒置，得到一个新的序列.

(5) 判断该序列是否满足出栈序列的性质1，然后判断序列的第j位是否小于等于k+j-1，若均满足，则输出该序列,转(1).

程序如下：#include "iostream.h"

#include "string.h"

void fx(char a[],int i,int j)

{int k; char tem;

for(k=i;k<=(i+j)/2;k++) { tem=a[k]; a[k]=a[i+j-k];a[i+j-k]=tem; } }

int pd(char a[],int n,int k)

{int u,v,w,j,flag=1;

for(u=0;u<=n-2;u++)

for(v=u+1;v<=n-1;v++)

for(w=v+1;w<=n;w++)

if((a[v]

if(flag)

for(j=0;j<=n-k;j++)

if((a[j]-′0′)>(k+j)) flag=0;

return flag; }

void main()

{int i,j,x,len,tag=1,count=1; char a[10],tem;

cout<<"please input stack:"<>a; cout<<"please input stack length:"<

cin>>x;cout<

while(tag)

{ for(i=len;i>0;i--)

if(a[i-1]

if(i-1<0) tag=0;

else { for(j=len;j>i;j--)

if(a[i-1]

tem=a[i-1]; a[i-1]=a[j]; a[j]=tem; fx(a,i,len);

if(pd(a,len,x)) { if(count%5==0) cout<

count++; cout<

不难发现，此算法效率不高，例如入栈序列为123456，栈大小为4，此时出栈序列既要满足性质1所述出栈序列的降序排列要求，也要满足第j位小于等于k+j-1，即出栈序列第一位需小于等于4，第二位需小于等于5.假设当前序列为256431，不难发现该序列满足上述两个条件，所以256431为出栈序列.按算法3，从256431得到下一序列，先将5和6互换，得到265431，然后将5431倒置，得到下一个序列261345，再判断是否是出栈序列，由于6后面比6小的数没有完全按降序排列，因此它不是出栈序列.继续算法3，依次可以得到261354,261435,…,265341,265413,265431，从261354到265413的序列由于6后面比6小的数没有完全按降序排列，所以都不是出栈序列，而265431满足性质1所述出栈序列的降序排列要求，但265431第二位为6，不满足出栈序列第二位需小于等于5的要求，因此265431也不是出栈序列.继续算法3，依次可以得到312456,312465,…,316542,321456，不难发现从312456到316542的序列不满足性质1所述出栈序列的降序排列要求，而321456既满足性质1所述出栈序列的降序排列要求，也满足第一位需小于等于4，第二位需小于等于5的要求，因此321456是栈大小为4时的一个出栈序列.

为提高效率，可以考虑采用算法2产生序列，然后对序列第j位是否小于等于k+j-1进行判断，满足要求的则为出栈序列.例如，可以采用算法2由256431产生下一序列265431，然后判断第一位是否小于等于4，第二位是否小于等于5，由于不满足要求，所以265431不是出栈序列.继续算法2，可由265431得到下一个序列321456，然后判断第一位是否小于等于4，第二位是否小于等于5，由于满足要求，所以321456是出栈序列.此方法可以显著提高效率，但毕竟产生了不是出栈序列的265431，因此效率不是最高的.

为达到最高效率，采用直接后续法，考虑从出栈序列256431直接产生下一个出栈序列321456.可做如下考虑：先从256431右端寻找第一个比右边数字小的数字的序号i=2，值为5，然后在5之后，从右端开始，找出第一个比5大的数的序号j=3，值为6，此时先不交换5和6的值，而是先判断6是否满足i序号位置元素需要满足的小于等于k+i-1的要求.由于i=2，4+2-1=5，所以6不满足要求，此时无需交换5和6的值，只需将i值减1，寻找下一个比右边数字小的数字的序号.此例中将i值减1后，i=1，由于i位置的2小于其右边的5，则从2之后，从右端开始，找出第一个比2大的数的序号j=5，值为3，然后判断3是否小于等于k+i-1，即4+1-1=4，满足要求，则交换2和3的值，得到356421，然后将i+1位置到j-1位置的元素从小到大排序，本例中为2到4位置的元素564从小到大排序，得到345621，然后将i+1位置之后的元素左环移j-i-1位，本例中为2到6位置的45621左环移5-1-1=3位，得到321456，此序列即为下一个出栈序列.

算法4栈大小为k，初始序列为12…n，当前序列为a1a2…an.

(1) 从出栈序列a1a2…an的右端开始，找出比右边数字小的数字的序号i.若无法找到这样的i，则结束.

(2) 在ai的右边的数字中，从右端开始，找出第一个比ai大的数的序号j.

(3) 判断aj是否小于等于k+i-1，若是则转(4)；否则i=i-1，转(1).

(4) 交换ai和aj.

(5) 将ai+1到aj-1的数从小到大排序.

(6) 将ai+1及其后所有数向左环移j-i-1位，得到下一个出栈序列并输出,转(1).

程序如下：#include"iostream.h"

#include"string.h"

voidpx(charb[],intsl)

{inti,j,k;chartem;

for(i=0;i

{k=i;

for(j=i+1;j

if(b[j]

if(k!=i) {tem=b[i];b[i]=b[k];b[k]=tem; } } }

voidmain()

{inti,j,k,sl,len,tag=1,count=1;chara[10],b[10],tem;

cout<<"pleaseinputstack:"<>a;cout<<"pleaseinputstacklength:"<

cin>>sl;cout<

while(tag)

{for(;i>0;i--)

if(a[i-1]

if(i-1<0)tag=0;

else{for(j=len;j>i;j--)

if(a[i-1]

if((a[j]-′0′)

{tem=a[i-1];a[i-1]=a[j];a[j]=tem;

for(k=i;k

b[k]=′′;

for(k=0;k<=len-j+1;k++)a[i+k]=a[j+k];

px(b,j-i);

for(k=0;k

a[i+len-j+1+k]=′′;

if(count%5==0)cout<

count++;cout<

else{i=i-1; } } } }

4 结束语

在栈大小不受限制和受限制两种情况下，给定入栈序列(1,2, …, n)，对输出全部出栈序列的问题进行分析研究.先给出出栈序列应满足的性质，依据性质，采用穷举法和直接后续法，给出输出全部出栈序列的算法及程序实现.文中算法较直观，易于理解，程序输出正确.

[1] 张先伟,曹雁锋.用插入法解决堆栈输出问题[J].计算机应用与软件,2007,24(11):169-171.

[2] 唐锐. 用后继序列法解决堆栈输出问题[J].小型微型计算机系统,2006,27(12):2314 -2316.

[3] 徐凤生.出栈序列的性质及其求解新算法[J].计算机工程与应用,2006,42(5):66-68.

[4] 何坤金,陈正鸣,杨垠.基于算子的栈序列生成算法与实现[J].计算机工程与设计,2006,27(12):2266-2267.

[5] 唐保祥.栈序列及其生成算法[J] .郑州大学学报：自然科学版,2001,33(4):33-35.

[6] 李红卫,徐亚平.出栈序列的研究[J].计算机技术与发展,2007,17(10):127-129.

[7] 袁红娟.基于链表的出栈序列生成算法[J].河北北方学院学报：自然科学版,2006, 22(5):70-75.

[8] 韩静.“数据结构”课程中出栈序列的一种求解算法[J].计算机教育,2008,6(23):68-70.

[9] 吴集林.用二叉树解决出栈序列问题[J].赣南师范学院学报,2005,26(6):28-30.

(责任编辑：孔 薇)

A Study on Stack-output Sequence

WANG Wen-long

(DepartmentofInformationEngineeringTechnology,KashgarTeachersCollege,Kashgar844000,China)

In two cases of stack that the size was limited and not limited, given stack-input sequence was (1,2, …,n), the nature of stack-output sequence was analyzed. Algorithms and programs, based on the exhaustive method and direct subsequent method, were elaborated. Algorithms were intuitive and easy to understand. Programs were tested, and the outputs were correct.

stack; stack-output sequence; direct subsequent method; algorithm; program

2014-12-10

新疆高校科研计划重点项目，编号XJEDU2014I039;喀什师范学院教研教改重点项目，编号KJDZ1303,KJDZ1202;喀什师范学院重点课题，编号(13)2456.

王文龙(1976-)，男，湖南双峰人，副教授，硕士，主要从事计算机软件及信息安全研究，E-mail: wwl-yx@163.com.

王文龙.输出出栈序列研究[J].郑州大学学报：理学版，2015，47(2)：53-58.

TP311

A

1671-6841(2015)02-0053-06

10.3969/j.issn.1671-6841.2015.02.012