摘 要： 在栈大小不受限制和栈大小受限制两种情况下，分析在给定入栈序列（1 2 … n）的情况下，出栈序列应满足的性质，并据此给出基于穷举法和模拟入栈出栈过程的方法判断序列a1a2…an是否是出栈序列的算法及程序实现。算法较直观，易于理解，程序均经过测试，输出正确。
关键词： 栈；出栈序列；降序；算法；程序
0 引言
栈是限定仅在表尾端进行插入或删除操作的特殊线性表。通常称表尾端为栈顶，向栈中插入元素称为进栈，从栈中删除元素称为出栈。由于插入和删除运算仅在栈顶一端进行，因此栈具有后进先出的特性，这种特性使得栈有着十分广泛的应用。在参考文献[1-9]中，对给定一个入栈序列，求出栈序列数量、输出全部出栈序列、判断一个序列是否为出栈序列等问题进行了研究，得出了相应的研究结果。然而，以上研究结果均基于一个前提：栈的大小是不受限制的，即栈的大小大于等于入栈序列的长度。而在某些情况下，栈的大小会受到限制，即栈的大小小于入栈序列的长度，此时有关栈的入栈出栈算法会发生变化。因此，本文对栈大小不受限制和栈大小受限制两种情况下，判断一个序列是否为出栈序列的问题进行分析研究，并给出了相应的算法和程序实现。
为方便分析，将本文研究的有关栈的问题描述如下：给定入栈序列（1 2 … n），判断序列a1a2…an是否是出栈序列。
1 出栈序列性质
当栈大小不受限制时，即栈的大小大于等于入栈序列的长度时，依据栈的特点，较容易得出出栈序列应该满足的性质。
性质1：当栈大小不受限制时，序列a1a2…an是（1 2 … n）的一个全排列, 则a1a2…an为出栈序列的充要条件是：对于任意的ai, 在它后面的且比它小的数是降序排列的。
当栈的大小受限制，即栈的大小k小于入栈序列长度n时，出栈序列首先需要满足性质1，然后考虑栈大小受限对出栈序列的要求。例如有长度n=6的入栈序列123456，栈的大小k=4，此时出栈序列的第1位不能超过元素4，即出栈序列第1位小于等于4，第2位小于等于5。
一般情况下，第1位小于等于k，第2位小于等于k+1，依次类推，直到出栈序列第n-k位小于等于n-1。
性质2：当栈大小受限制，即栈大小k小于入栈序列长度n时，序列a1a2…an是（1 2 … n）的一个全排列, 则a1a2…an为出栈序列的充要条件是满足性质1并且序列的第j位小于等于k+j-1。
2 栈大小不受限制时的判断
给定入栈序列12…n，判断序列a1a2…an是否是出栈序列。此时可以对序列直接判断是否满足性质1。满足则为出栈序列，否则不是出栈序列。
算法1：入栈序列为12…n，待判断序列为a1a2…an。
（1）输入待判断序列，i=1。
（2）若i>n，转（3）；否则判断序列a1a2…an第i位ai后比ai小的元素是否降序排列，若是则i++，转（2）；否则转（3）。
（3）若i>n，则判断该序列为出栈序列；否则，判断该序列不是出栈序列。
程序如下：
#include "iostream.h"
#include "string.h"
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]<a[w])&&(a[w]<a[u]))
flag=0;
return flag;}
void main()
{char a[10];
cout<<"请输入待判断的序列:"<<endl;
cin>>a;
if(pd(a,strlen(a)-1))
cout<<"这是出栈序列"<<endl;
else
cout<<"这不是出栈序列"<<endl;}
不难发现上述算法需要多层循环，效率偏低。可以考虑做改进，此时使用临时栈s模拟入栈出栈过程，用i表示待判断序列第i位，用j表示入栈序列第j位。算法如下：
算法2：入栈序列为12…n，待判断序列为a1a2…an, s为临时栈。
（1）初始情况下i、j的初值为1。
（2）当i或j大于n时，转（4），否则用待判断序列第i位ai与入栈序列第j位比较。
（3）ai大于j时，将j入栈s，j++，转（2）；ai等于j时，i++、j++，转（2）；ai小于j时，比较ai与s栈的栈顶元素，若相等则s栈的栈顶元素出栈，i++，转（2），否则判断该序列不是出栈序列。
（4）判断栈是否为空，若为空，则判断该序列是出栈序列，否则依次判断ai、ai+1、…、an与s栈的出栈序列是否相同，若不同则判断该序列不是出栈序列，若相同则判断该序列为出栈序列。
将上述pd函数改写如下：
int pd(char a[],int n)
{ int i=0,j=0,top=0;
char b[10];
while(i<=n&&j<=n)
{ if(a[i]>('1'+j))
{ b[top++]='1'+j; j++; }
else if(a[i]==('1'+j))
{ i++; j++; }
else
{ if(a[i]==b[--top])
i++; } }
if(top)
while(i<=n)
if(a[i]==b[--top])
i++;
else return 0;
return 1;}
3 栈大小受限制时的判断
当栈的大小受限制，即栈的大小k小于入栈序列长度n时，出栈序列需要满足性质2中所述的性质。此时可以判断待判断序列a1a2…an第i位ai后比ai小的元素是否降序排列以及第j位是否小于等于k+j-1，若满足则为出栈序列，否则不是出栈序列。
此时的判断算法，可以在算法1的基础上，加入对待判断序列第j位是否小于等于k+j-1的判断。
算法3：入栈序列为12…n，待判断序列为a1a2…an。
（1）输入待判断序列，i=1，j=1。
（2）若j>n-k，则转（3）；否则判断序列第j位是否小于等于k+j-1，若是则j++，转（2）；否则转（4）。
（3）若i>n，则转（4）；否则判断序列a1a2…an第i位ai后比ai小的元素是否降序排列，若是则i++，转（3）；否则转（4）。
（4）若i>n，则判断该序列为出栈序列；否则，判断该序列不是出栈序列。
程序如下：
#include "iostream.h"
#include "string.h"
int pd(char a[],int n,int x)
{ int u,v,w,j,flag=1;
for(j=0;j<=n-x;j++)
if((a[j]-'0')>(x+j))
flag=0;
if(flag)
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]<a[w])&&(a[w]<a[u]))
flag=0;
return flag;}
void main()
{ int x;
char a[10];
cout<<"请输入栈大小:"<<endl;
cin>>x;
cout<<"请输入待判断的序列:"<<endl;
cin>>a;
if(pd(a,strlen(a)-1,x)) cout<<"这是出栈序列"<<endl;
else cout<<"这不是出栈序列"<<endl;}
不难看出此算法效率较低，可以做改进。此时需使用临时栈s模拟入栈出栈过程，当待判断序列第i位大于入栈序列第j位时，将入栈序列第j位入栈。由于受原栈大小为k的限制，此时临时栈s的入栈元素不能超过k-1个。算法如下：
算法4：栈大小为k，入栈序列为12…n，待判断序列为a1a2…an，s为临时栈。
（1）初始情况下i、j的初值为1。
（2）当i或j大于n时，转（4）；否则用待判断序列第i位ai与入栈序列第j位比较。
（3）ai大于j时，判断s栈中元素个数是否小于k-1，若是则将j入s栈，j++，转（2），否则判断该序列不是出栈序列；ai等于j时，i++、j++，转（2）；ai小于j时，比较ai与s栈的栈顶元素，若相等则s栈的栈顶元素出栈，i++，转（2），否则判断该序列不是出栈序列。
（4）判断s栈是否为空，若为空，则判断该序列是出栈序列，否则依次判断ai、ai+1、…、an与s栈的出栈序列是否相同，若不同则判断该序列不是出栈序列，若相同则判断该序列为出栈序列。
将上述pd函数改写如下：
int pd(char a[],int n,int k)
{ int i=0,j=0,top=0;
char b[10];
while(i<=n&&j<=n)
{ if(a[i]>('1'+j))
{ if(top==k-1)
return 0;
b[top++]='1'+j; j++; }
else if(a[i]==('1'+j))
{ i++; j++; }
else
{ if(a[i]==b[--top])
i++; } }
if(top)
while(i<=n)
if(a[i]==b[--top])
i++;
else return 0;
return 1; }
上述算法效率依然不是最高的，例如待判断序列为543261时，用待判断序列第1位与入栈序列第1位比较，由于5大于1，且s栈中元素个数为0，小于k-1=3，因此将入栈序列中的1入s栈，继续比较待判断序列第1位与入栈序列第2位。由于5大于2，且s栈中元素个数为1，小于3，因此将入栈序列中的2入s栈，继续比较待判断序列第1位与入栈序列第3位。由于5大于3，且s栈中元素个数为2，小于3，因此将入栈序列中的3入s栈，继续比较待判断序列第1位与入栈序列第4位。由于5大于4，而s栈中元素个数为3，若将4入s栈，则s栈中元素个数大于3，因此待判断序列不是出栈序列。
而此时已经有3个元素入s栈，才判断出该序列不是出栈序列，可以考虑直接在开始时判断该序列是否满足大小受限制栈的出栈序列应该满足的要求，即第j位小于等于k+j-1。上例由于第1位5大于4+1-1=4，因此不用入s栈就可判断出该序列不是出栈序列。改进算法如下：
算法5：栈大小为k，入栈序列为12…n，待判断序列为a1a2…an，s为临时栈
（1）初始情况下i、j的初值为1。
（2）当i或j大于n时，转（4）；否则判断ai是否大于k+i-1，若大于，则判断该序列不是出栈序列，否则用待判断序列第i位ai与入栈序列第j位比较。
（3）ai大于j时，则将j入s栈，j++，转（2）；ai等于j时，i++、j++，转（2）；ai小于j时，比较ai与s栈的栈顶元素，若相等则s栈栈顶元素出栈，i++，转（2），否则判断该序列不是出栈序列。
（4）判断栈是否为空，若为空，则判断该序列是出栈序列，否则依次判断ai、ai+1、…、an与栈的出栈序列是否相同，若不同则判断该序列不是出栈序列，若相同则判断该序列为出栈序列。
改写pd函数如下：
int pd(char a[],int n,int k)
{ int i=0,j=0,top=0;
char b[10];
while(i<=n&&j<=n)
{if(a[i]-'0'>k+i) return 0;
if(a[i]>('1'+j))
{ b[top++]='1'+j; j++; }
else if(a[i]==('1'+j))
{ i++; j++; }
else
{if(a[i]==b[--top])
i++; } }
if(top)
while(i<=n)
if(a[i]==b[--top])
i++;
else return 0;
return 1; }
4 结束语
本文对栈大小不受限制和栈大小受限制两种情况下，给定入栈序列（1 2 … n），对判断序列a1a2…an是否是出栈序列的问题进行分析研究。先给出出栈序列应满足的性质，依据性质，先采用穷举法给出判断的算法及程序
实现，然后模拟入栈出栈过程，给出判断的改进算法及程序实现。本文算法较直观，易于理解，程序均经过测试，输出正确。
参考文献
[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,2287.
[5] 唐保祥. 栈序列及其生成算法[J]. 郑州大学学报, 2001,33(4):33-35.
[6] 李红卫,徐亚平. 出栈序列的研究[J]. 计算机技术与发展, 2007,17(10):127-129,133.
[7] 袁红娟. 基于链表的出栈序列生成算法[J]. 河北北方学院学报(自然科学版), 2006, 22(5):71-75.
[8] 韩静.“数据结构”课程中出栈序列的一种求解算法[J]. 计算机教育, 2008,6(23):68-70.
[9] 吴集林. 用二叉树解决出栈序列问题[J]. 赣南师范学院学报, 2005,26(6):28 -30.