输入两个整数序列

题目:输入两个整数序列。其中一个序列表示栈的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序列。

思路

引入一个辅助栈，先将push数组的一个元素入栈，将在栈顶元素与pop数组的当前位置(位置j从0开始)元素比较，相等则将弹栈，并将pop数组前进一位，不等则将push数组的当前位置(i从0开始)的元素入栈，继续重复上述步骤，直到栈空。

如果i大于push数组的大小，且j小于pop数组的长度,则说明不匹配，否则匹配。

代码实现

int isPopOrder(int *push, int *pop, int len)
{
	if(push==NULL || pop==NULL)  //判断参数的有效性
		return 0;
	int i=0, j=0;
	stack<int> s_push;
	s_push.push(push[i++]);   //将push数组的第一个元素入栈
	while(!s_push.empty() && i<=len)
	{
		if(s_push.top()==pop[j])
		{
			s_push.pop();  //弹栈
			j++; //增加pop数组的位置
		}
		else 
		{
			s_push.push(push[i++]);
	  	}
	}
	if(i>len && j<len)
		return 0;
	return 1;
}