给定入栈顺序，判断出栈顺序是否合法-创新互联

题目描述：给定一个入栈序列，给定一个出栈序列，判断该出栈序列是否合法。

成都创新互联公司成都企业网站建设服务，提供成都网站设计、成都做网站网站开发,网站定制,建网站,网站搭建,网站设计,成都响应式网站建设公司,网页设计师打造企业风格网站,提供周到的售前咨询和贴心的售后服务。欢迎咨询做网站需要多少钱:18980820575

分析：假如入栈序列为1 2 3 4 5，判断4 5 3 2 1 是否是合法的出栈顺序。

两个序列均以数组的形式给出

从两个数组的第一个元素开始，如果栈为空，或者，栈顶元素不等于当前出栈数组当前下标对应的元素时，将当前入栈数组中下标所指向的元素进行压栈

初始状态如下：

步骤1：把 1 进行压栈，并将下标后移，如下图所示，

步骤2：依次进行判断并压栈，当4进栈后，此时栈顶元素等于出栈数组下标所指向的元素，将4出栈，如下图所示

步骤3：将 4 出栈，并将出栈数组的下标后移，继续判断栈顶元素是否为当前出栈数组下标对应的元素，是，则出栈，否则继续往后执行

步骤4：重复上述步骤，直到入栈数组中的下标走到尽头

当最后一个元素入栈后，此时只需循环判断栈顶元素是否与出栈数组当前下标对应的元素相等，如果该序列合法，则栈中的元素最终都会出栈，不合法则栈永远不为空

此时，栈为空，则该序列合法。

代码如下：

#include
#include
#include
using namespace std;


template
bool IsSequenceVaild(const T* inSequence, const T* outSequence, size_t n)
{
	assert(inSequence && outSequence);

	stack 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(in, out1, 5) << endl;
	cout << IsSequenceVaild(in, out2, 5) << endl;
	cout << IsSequenceVaild(in, out3, 5) << endl;
}

void main()
{
	Test1();

	system("pause");
}

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。

名称栏目：给定入栈顺序，判断出栈顺序是否合法-创新互联
转载注明：http://mswzjz.cn/article/djodoo.html