給定入棧順序，判斷出棧順序是否合法

題目描述：給定一個入棧序列，給定一個出棧序列，判斷該出棧序列是否合法。

分析：假如入棧序列為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");
}