Q22：栈的压入、弹出序列

Q：给定一个入栈序列in和出栈序列out，判断out是否是in的一个可行(合法)的出栈序列。

思路：将入栈序列in入栈，若当前栈顶的元素与当前out的元素相同，那么继续判断out的下一个元素。

            若当前栈顶的元素与当前out的元素不同，且还有未入栈的in元素，那么继续入栈新元素，否则

            就表明，所有的入栈in元素都入栈了，该出栈的元素就是没在栈顶出现，说明被“埋没”了，是个错误的出栈顺序。

bool IsPopOrdder(const int *pPush, const int *pPop, int nlength)
{
	stack<int> stackData;
	bool bPossible = false;
	const int maxvalue = 0x7fffffff;
	stackData.push(maxvalue);
	const int *pcPop = pPop;
	const int *pcPush = pPush;
	if(NULL != pcPop && NULL != pcPush && nlength > 0)
	{
		while (1)
		{
			//相同，则pop
			if(stackData.top() == *pcPop)
			{
				stackData.pop();
				++pcPop;
			}
			//否则判断下一个入栈的值的情况，这里会有两种情况：
			//1）没有元素可以入栈，那么就停止。
			else if(pcPush - pPush == nlength)
				break;
			//2）有元素可以入栈，就继续
			else
			{
				stackData.push(*pcPush);
				++pcPush;
			}
		}
		//表示该入栈的都入了，判断该出的是否都出了。
		if(stackData.top() == maxvalue)
			bPossible = true;
	}
	return bPossible;
}

Q22：栈的压入、弹出序列,布布扣,bubuko.com

Q22：栈的压入、弹出序列

原文：http://blog.csdn.net/shiquxinkong/article/details/22751469