学步园

参考网址：http://blog.csdn.net/v_JULY_v/article/details/6126444

问题描述：

输入两个整数序列。其中一个序列表示栈的push顺序，判断另一个序列有没有可能是对应的pop顺序。
为了简单起见，我们假设push序列的任意两个整数都是不相等的。 
比如输入的push序列是1、2、3、4、5，那么4、5、3、2、1就有可能是一个pop系列。
因为可以有如下的push和pop序列：
push 1，push 2，push 3，push 4，pop，push 5，pop，pop，pop，pop，
这样得到的pop序列就是4、5、3、2、1。
但序列4、3、5、1、2就不可能是push序列1、2、3、4、5的pop序列。

代码实现：

#include <iostream>
#include <stack>

using namespace std;

bool isPopSeries(int push[], int pop[], int n)
{
	stack<int> stk;
	int i = 0, j = 0;
	while (j < n)
	{
		if (!stk.empty() && pop[j] == stk.top())
		{
			stk.pop();
			j++;
		}
		else
		{
			while (i < n && push[i] != pop[j])
			{
				stk.push(push[i]);
				i++;
			}

			if (i == n)
				return false;
			i++;
			j++;
		}
	}

	return true;
}

int main()
{
	int push[] = {1, 2, 3, 4, 5};
	int pop[] = {5, 4, 3, 2, 1};

	cout << boolalpha << isPopSeries(push, pop, 5) << endl;

	system("pause");
	return 0;
}