题解 | #火车进站#

#include<iostream>
#include<stack>
#include<vector>
#include <queue>
#include<algorithm>
using namespace std;
//找出输入数字的全排列，然后用栈来找是不是符合情况。如果出栈序列元素=入栈元素，同时弹出，不等于则入栈，最后看栈中是否为空
bool Checkstack(vector<int>& a,vector<int>& b,int n){
    //分别是入栈队列、出栈队列、队列长度
    queue<int>in;
    queue<int>out;
    stack<int>st;
    for(int i=0;i<n;i++){
        in.push(a[i]);
        out.push(b[i]);
    }
    while(!in.empty()){
        st.push(in.front());
        in.pop();
        while(!st.empty()&&out.front()==st.top()){st.pop();
        //注意while里一定要先判断栈是不是空，判断完再去访问，否则栈中为空后还是会先去找栈顶，造成边界的错误
        out.pop();}
    }
    if(st.empty()) { return true;}
    else {return false;}
}
void Print(vector<int> b,int n){
    for(int i=0;i<n;i++){
        cout<<b[i]<<" ";
    }
    cout<<endl;
}
int main(){
    int n;
    cin>>n;
        vector<int>a(n,0);//a是入栈的顺序
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        vector<int>b(a);//b用来不断循环排序，产生新的出栈序列，再对每一个生成的b用函数判断是否是合法的出栈序列
        sort(b.begin(),b.end());//因为第一个sort排出来的最小字典序的出栈序列也要遍历，所以用do while 先执行后遍历，至少也会执行一次
        do{
            if(Checkstack(a,b,n)){
                Print(b,n); }
        }while(next_permutation(b.begin(), b.end()));

    
    return 0;
}