题解 | #火车进站#

思路：

        从小到大全排列所有的出栈序列。

        并根据入栈序列判断该出栈序列是否正确；

         如果正确则输出该出栈序列。

    

    根据入栈序列判断该出栈序列是否正确：（图示方法如下）

    

#include <bits/stdc++.h>

using namespace std;
int n,a[15],c[15];

//根据入栈序列判断出栈序列是否正确
bool check(int b[]){
    stack<int> st;//栈
    int j=0;
    for(int i=0;i<n;i++){//遍历入栈序列
       st.push(a[i]);
        while(!st.empty()&&b[j]==st.top()){//如果栈顶元素等于出栈序列元素，则栈顶元素出栈并出栈序列下标加一
            st.pop();
            j++;
        }
    }
    return st.empty();//判断栈是否为空
}

int main(){
    while(cin >> n){
        for(int i=0;i<n;i++){//输入入栈序列
            cin >> a[i];
            c[i]=a[i];
        }
        //排序
        sort(c,c+n);
        //全排列出栈序列
        do{
            if(check(c)){//如果成功，则输出该出栈序列
                for(int i=0;i<n;i++){
                    cout << c[i] << " ";
                }
                cout << endl;
            }
        }while(next_permutation(c,c+n));
        
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;
int n,a[15],c[15],temp[15];
int vis[15];

//根据入栈序列判断出栈序列是否正确
bool check(int b[]){
    stack<int> st;//栈
    int j=0;
    for(int i=0;i<n;i++){//遍历入栈序列
       st.push(a[i]);
        while(!st.empty()&&b[j]==st.top()){//如果栈顶元素等于出栈序列元素，则栈顶元素出栈并出栈序列下标加一
            st.pop();
            j++;
        }
    }
    return st.empty();//判断栈是否为空
}

void dfs(int x){
    if(x==n){
        if(check(temp)){//如果成功，则输出该出栈序列
            for(int i=0;i<n;i++){
                cout << temp[i] << " ";
            }
            cout << endl;
        }
        return;
    }
    for(int i=0;i<n;i++){//遍历数组
        int y=c[i];
        if(vis[y]==0){//如果未访问，则访问
            vis[y]=1;
            temp[x]=y;
            dfs(x+1);
            vis[y]=0;
        }
        
    }
}
int main(){
    while(cin >> n){
        for(int i=0;i<n;i++){//输入入栈序列
            cin >> a[i];
            c[i]=a[i];
        }
        //排序
        sort(c,c+n);
        //dfs全部的出栈序列
        dfs(0);
        
    }
    return 0;
}