判断元素出栈，入栈顺序的合法性

问题：元素出栈，入栈顺序的合法性。如入栈的序列（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> using namespace std; #include<stack> #include<string> template<class T> class OutStack { public:	OutStack();	OutStack(const T* str1, const T* str2, size_t size1, size_t size2);	~OutStack();	bool OutStack::Legality(); private:	T* _str1;	T* _str2;	size_t _size1;	size_t _size2; }; template<class T> OutStack<T>::OutStack() :_str1[NULL] , _str2[NULL] , sp(NULL) {} template<class T> OutStack<T>::OutStack(const T* str1, const T* str2, size_t size1, size_t size2) : _str1(new T[size1]) , _str2(new T[size2]) , _size1(size1) , _size2(size2) {	memcpy(_str1, str1,(sizeof(T)*_size1));//memcpy按照字节数进行复制的	memcpy(_str2 ,str2,(sizeof(T)*_size2)); } template<class T> OutStack<T>::~OutStack() {	if (_str1 || _str2)	{	delete[] _str1;	delete[] _str2;	} } template<class T> bool OutStack<T>::Legality() {	T* str1 = _str1;//入栈序列	T* str2 = _str2;//出栈序列	stack<T> sp;	if (str1 && str2 && _size1 != _size2)	return 0;	sp.push(*str1);//先将str1中第一个元素入栈	for (size_t i = 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())//如果栈为空，则出栈序列是合法的	{	return 1;	}	return 0; }

测试用例如下：

void Test1() {	int arr1[] = { 1, 2, 3, 4, 5 };//入栈序列	int str1[] = { 4, 5, 3, 1, 2 };//出栈序列	//int str1[] = { 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; }