栈的压入弹出序列

题目描述：

判断一个栈的输出序列是否是正确的，时间复杂度要求O(N)

示例：

输入栈：1 2 3 4 5

(1)输出栈： 4 5 3 2 1

(2)输出栈： 4 3 5 1 2

分析步骤：

(1)首先需要一个辅助栈来模拟整个过程；

(2)如果栈为空或者栈顶元素不等于输出栈的值，就将输入栈的当前元素入栈，并且将输入栈的当前索引++；

(3)否则弹出栈顶元素，并且将输入栈的索引++；

(4)如果输入栈的索引小于输出栈的元素个数，重复上述操作；

(5)如果输入栈的索引小于输出栈的元素个数，但输入栈的索引等于输入栈的元素个数，返回false，否则返回true；

代码实现：

template<class T>
bool CheckStack(vector<T>& in, vector<T>& out)
{
	if (in.size() != out.size())
		return false;

	int idx_in = 0, idx_out = 0;
	stack<T> s;
	while (idx_out != out.size())
	{
		if (s.empty() || s.top() != out[idx_out])
		{
			if (idx_in == in.size())
				return false;
			s.push(in[idx_in++]);
		}
		else
		{
			++idx_out;
			s.pop();
		}
	}
	return true;
}


int main()
{
	vector<int> in;
	in.push_back(1);
	in.push_back(2);
	in.push_back(3);
	in.push_back(4);
	in.push_back(5);

	vector<int> out;
	out.push_back(4);
	out.push_back(5);
	out.push_back(3);
	out.push_back(2);
	out.push_back(1);

	vector<int> out1;
	out1.push_back(4);
	out1.push_back(5);
	out1.push_back(3);
	out1.push_back(1);
	out1.push_back(2);

	bool ret = CheckStack(in, out);
	cout << ret << endl;

	bool ret1 = CheckStack(in, out1);
	cout << ret1 << endl;

	system("pause");
	return 0;
}