题解 | #火车进站#
火车进站
http://www.nowcoder.com/practice/97ba57c35e9f4749826dc3befaeae109
qin非空就把qin.front入栈st并qin.pop
当检测栈非空且st.top==qout.front，就st.pop; qout.pop;
最终检测栈空，则出栈序列合法，不空则出栈序列非法
注意使用next_permutation做排序时要先对原序列进行升序排序
总代码：
/*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));
}
