题解 | #火车进站#

/*hj77火车进站
思路：全排列，再判断全排列顺序是否可以由入栈顺序构成
*/
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;
int checkstack(int in[],int out[],int n)//参数为入栈序列和待检查序列   长度 
{
    queue<int>qin;
    queue<int>qout;
    stack<int>st;
    for(int i=0;i<n;i++)//入栈顺序队列 
    {
    	qin.push(in[i]);
	}
    for(int i=0;i<n;i++)//出栈顺序队列 
    {
    	qout.push(out[i]);
	}
	while(!qin.empty())
	{
		st.push(qin.front());//进入检测栈 
		qin.pop();
		while(!st.empty()&&st.top()==qout.front())
		{
			st.pop();
			qout.pop();
		}
	}
	if(st.empty()) return 1;
	else return 0;
}
int main()
{
    int n;
    cin>>n;
    int a[10];
    for(int i=0;i<n;i++) cin>>a[i];    
    int b[10];
    for(int i=0;i<n;i++) b[i]=a[i]; 
    sort(b,b+n);
    do
    {
    	if(checkstack(a,b,n))//出栈顺序合法 
    	{
    		for(int i=0;i<n;i++) cout<<b[i]<<" ";
        	cout<<endl;
		}        
    }while(next_permutation(b,b+n));
}