问题：元素出栈，入栈顺序的合法性。如入栈的序列（1,2,3,4,5），出栈序列为（4,5,3,1,2）

定义一个栈sp，入栈序列为str1，出栈序列为str2，长度分别为size1和size2。如果两个序列为空或长度不等，则不合法，针对长度相等且不为空的两个序列进行判断。

先将str1中第一个元素入栈，然后通过循环使str1后移。

1、如果当前栈为空且入栈序列不为空，则入栈序列str1后移，sp入栈。

2、如果栈顶元素不等于出栈序列且入栈序列不为空，则入栈序列str1后移，sp入栈。

3、如果栈顶元素等于出栈序列，sp出栈，出栈序列str2后移。

循环比较后，如果栈为空，则出栈序列是合法的。

下面以入栈的序列（1,2,3,4,5），出栈序列为（4,5,3,1,2）为例进行说明。

利用模板实现对象OutStack，可以判断不同类型元素出栈，入栈顺序的合法性，具体实现如下：

#include<iostream>usingnamespacestd;#include<stack>#include<string>template<classT>classOutStack{public:OutStack();OutStack(constT*str1,constT*str2,size_tsize1,size_tsize2);~OutStack();boolOutStack::Legality();private:T*_str1;T*_str2;size_t_size1;size_t_size2;};template<classT>OutStack<T>::OutStack():_str1[NULL],_str2[NULL],sp(NULL){}template<classT>OutStack<T>::OutStack(constT*str1,constT*str2,size_tsize1,size_tsize2):_str1(newT[size1]),_str2(newT[size2]),_size1(size1),_size2(size2){memcpy(_str1,str1,(sizeof(T)*_size1));//memcpy按照字节数进行复制的memcpy(_str2,str2,(sizeof(T)*_size2));}template<classT>OutStack<T>::~OutStack(){if(_str1||_str2){delete[]_str1;delete[]_str2;}}template<classT>boolOutStack<T>::Legality(){T*str1=_str1;//入栈序列T*str2=_str2;//出栈序列stack<T>sp;if(str1&&str2&&_size1!=_size2)return0;sp.push(*str1);//先将str1中第一个元素入栈for(size_ti=0;i<_size1;)//将出栈序列比较完{if(*str1!=NULL&&sp.empty()){str1++;sp.push(*str1);i++;//i和str1同步进行,直到str1进行完}if(*str1!=NULL&&sp.top()!=*str2)//栈顶元素与出栈元素比较{str1++;sp.push(*str1);i++;//i和str1同步进行，直到str1进行完}if(sp.top()==*str2){sp.pop();str2++;}}if(sp.empty())//如果栈为空，则出栈序列是合法的{return1;}return0;}

测试用例如下：

voidTest1(){intarr1[]={1,2,3,4,5};//入栈序列intstr1[]={4,5,3,1,2};//出栈序列//intstr1[]={3,2,1,5,4};//出栈序列OutStack<int>s1(arr1,str1,5,5);cout<<s1.Legality()<<endl;char*arr2="abcdef";//入栈序列//char*str2="bafdce";//出栈序列char*str2="baefdc";//出栈序列OutStack<char>s2(arr2,str2,6,6);cout<<s2.Legality()<<endl;}