问题：元素出栈，入栈顺序的合法性。如入栈的序列（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
using namespace std;
#include
#include
template
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
OutStack::OutStack()
:_str1[NULL]
, _str2[NULL]
, sp(NULL)
{}
template
OutStack::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
OutStack::~OutStack()
{
if (_str1 || _str2)
{
delete[] _str1;
delete[] _str2;
}
}
template
bool OutStack::Legality()
{
T* str1 = _str1;//入栈序列
T* str2 = _str2;//出栈序列
stack 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 s1(arr1, str1, 5, 5);
cout << s1.Legality() << endl;
char* arr2 = "abcdef";//入栈序列
//char* str2 = "bafdce";//出栈序列
char* str2 = "baefdc";//出栈序列
OutStack s2(arr2, str2, 6, 6);
cout << s2.Legality() << endl;
}创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。
网页标题：判断元素出栈，入栈顺序的合法性-创新互联
当前地址：
http://cdkjz.cn/article/diegho.html
