判断栈的出栈跟入栈序列O(N)时间O(N)空间

判断栈的出栈和入栈序列O(N)时间O(N)空间

给出一个序列式栈的入栈序列，但是在入栈的过程中可能会有元素出栈，问最后的出栈序列是否可能出现

，思路就是你想的那样。不再赘述，实在打字麻烦，看代码页很容易看的。就不写了。

void init_queue(queue<int>& q , const int a[],const int n)
{
	for (unsigned i=0;i<n;i++)
	{
		q.push(a[i]);
	}
}
void check_stack_order(int pushdata[],int checkdata[],int n)
{	
	queue<int> pushqueue;
	init_queue(pushqueue,pushdata,n);
	stack<int> tempstack;
	int i=0;
	while (true)
	{
		if (!tempstack.empty() && tempstack.top()==checkdata[i])
		{
			tempstack.pop();
			++i;
		}
		else 
		{
			if (pushqueue.empty())
			{
				break;
			}
			tempstack.push(pushqueue.front());
			pushqueue.pop();
		}
	}
	if (i==n)
	{
		cout<<"wright order !"<<endl;
	}
	else
	{
		cout<<"wrong order !"<<endl;
	}
}
int main( void ) 
{
	int pushdata[]={1,2,3,4,5};
	//int check[]={5,1,2,4,3};
	int check[]={2,1,4,3,5};
	check_stack_order(pushdata,check,sizeof(pushdata)/sizeof(int));
	return 0;
}