出栈序列
写作本文的原因有二，其一是此前在网上找到的题解大多使用容器，而刚开始学习数据结构还没有很好掌握stl的同学会感到头疼；其二是苯人终于理解了栈的实现，一改过去只会pop, push的困顿面貌。
- 想要知道出栈序列，首先要搞明白出栈序列里的每一个元素是怎么产生的。按照栈的基本原理，出栈先放入一定的东西在栈中，然后把栈顶的元素弹出来。
- 所以倒推每一个出栈序列元素，我们需要知道栈数组中栈顶的元素。
- 而为了出栈序列的完整性，我们需要知道栈顶被弹出后，栈数组中新的栈顶元素是什么，方便下一次弹出。
- 为了知道新的栈顶元素，我们需要知道整个栈数组中的元素的顺序，还有一个可以指明栈顶的指针。
- 必须要指出一点，栈数组到底会弹出什么，是在弹出的时刻决定的。因此对栈数组的变化要及时记录。
- 从第4步我们了解到要知道栈数组中的元素顺序，这个只要按照栈的压入规律放入栈中就可以了。再结合第5步，我们在压入和弹出的时候都要及时更新栈数组和栈顶指针。
结合以上六点，我们可以看到，出栈的每一个元素都由出栈前的栈数组决定，因此我们想要得到出栈顺序，至少应该有一个数组来记录栈中元素，且有一个栈顶指针。
同时想要得到栈数组，我们需要知道在栈数组产生变化的前一刻将要发生的操作——压入或者弹出。
对于弹出操作，栈顶指针只要减一就可以了，但是对于压入操作，我们还需要知道入栈数组此时的末尾元素。
所以我们可以看到，每一次变化都是和变化前三个数组的状态息息相关的，三个数组的变化都要及时记录。
请注意，本文是为得出出栈序列而使用的叙述方式，且是最为暴力的模拟方法，实际在使用时可以先找找规律看看有没有其他更简洁的方式可以解决。
栈数组的变化过程表征的是对各个元素的操作顺序，直接影响出栈顺序的是入栈顺序和操作顺序，此处以固定1 到 n的入栈顺序，遍历所有操作可能。
为了产生字典序，能出栈的我们出栈，不能出栈了再入栈。完成一次完整操作（到n）后，返回上一个决定要出栈的节点，如果可以入栈选择入栈，不能再回到上一个决定要出栈的节点，再看能不能入栈，直到可以入栈，重新能出栈就出栈，这样就进入了一个新的出栈方式。
当再次完成完整操作后，重复上一次完整操作的过程，以此类推，直到返回到第一个入栈的节点。因为在这个节点之前没有节点了，所以所有可能的出栈序列打印完毕。
注意：在返回的过程中三个数组的变化都要记录。
这份代码并没有显示的提及三个数组，但是都用或者数组或者指针标志标注了。
本文所提到的指针都是标记，意义是标记位置。
贴上代码
#include<bits/stdc++.h>
using namespace std;
int n;
int sig[14];
int a[14];
int cnt = 0;
bool sg = true;
int cntt;
void dfs(int x, int y){
if(x == n && y == n){
for(int i = 1; i <=n; i++)
printf("%d ", a[i]);
printf("\n");
return;
}
if(y < x){
if(!sg){
cntt = cnt;
sg = true;
}
a[y + 1] = cntt;
int z = y;
cntt--;
for(int i = z; i > 0; i--){
if(a[i] == cntt){
cntt--;
i = z + 1;
}
}
dfs(x, y + 1);//优先向上走
}
if(x < n){
++cnt;
sg = false;
dfs(x + 1, y);
--cnt;
}
}
int main(){
scanf("%d", &n);
dfs(0, 0);
}