题目描述：给定一个入栈序列，给定一个出栈序列，判断该出栈序列是否合法。
分析：假如入栈序列为1 2 3 4 5，判断4 5 3 2 1 是否是合法的出栈顺序。
两个序列均以数组的形式给出
从两个数组的第一个元素开始，如果栈为空，或者，栈顶元素不等于当前出栈数组当前下标对应的元素时，将当前入栈数组中下标所指向的元素进行压栈
初始状态如下：
步骤1：把 1 进行压栈，并将下标后移，如下图所示，
步骤2：依次进行判断并压栈，当4进栈后，此时栈顶元素等于出栈数组下标所指向的元素，将4出栈，如下图所示
步骤3：将 4 出栈，并将出栈数组的下标后移，继续判断栈顶元素是否为当前出栈数组下标对应的元素，是，则出栈，否则继续往后执行
步骤4：重复上述步骤，直到入栈数组中的下标走到尽头
当最后一个元素入栈后，此时只需循环判断栈顶元素是否与出栈数组当前下标对应的元素相等，如果该序列合法，则栈中的元素最终都会出栈，不合法则栈永远不为空
此时，栈为空，则该序列合法。
代码如下：
计算
安全
数据库
网络和加速
企业服务
#include<iostream>
#include<stack>
#include<cassert>
using namespace std;
template<class T>
bool IsSequenceVaild(const T* inSequence, const T* outSequence, size_t n)
{
assert(inSequence && outSequence);
stack<T> sc;
int j = 0; //用来记录出栈数组当前元素的下标
for (int i = 0; i < n; ++i)
{
sc.push(inSequence[i]);
while (!sc.empty() && sc.top() == outSequence[j])
{
sc.pop();
++j;
}
}
return (sc.size() == 0) ? true : false;
}
void Test1()
{
int in[5] = { 1, 2, 3, 4, 5 };
int out1[5] = { 1, 2, 3, 4, 5 };
int out2[5] = { 4, 5, 3, 2, 1 };
int out3[5] = { 3, 5, 4, 2, 1 };
int out4[5] = { 3, 5, 4, 2, 1 };
int out[5] = { 4, 5, 3, 1, 2 };
cout << IsSequenceVaild<int>(in, out1, 5) << endl;
cout << IsSequenceVaild<int>(in, out2, 5) << endl;
cout << IsSequenceVaild<int>(in, out3, 5) << endl;
}
void main()
{
Test1();
system("pause");
}亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
