栈的输出序列

那条白线是最大容量标记

当前栈内没有元素 所以所消耗的最大容量是0 白线画在栈的底部

有写题会刷点小聪明

给一个出队序列
队的先进先出原则
出队序列 就是 出栈序列

栈的先进后出原则
所得到的出栈序列 是我们上一个栈的出栈序列 的 逆序序列

e可以出现在四个位置

若p1 = n 时 则出栈元素固定（即n为第一个出栈）

当pi = n ，pi之后出栈是的降序 因为入栈是升序
pi之后的 是在pi出栈之后才逐个出栈
这个很重要

出栈顺序是Pi, Pj, Pk

第四个黄色标记的入栈序列 是不存在 出栈顺序是Pi, Pj, Pk的 ，其余的入栈序列均存在
因为Pi 若为第一个出栈 则接下来会是Pk出栈 而不是Pj 不满足

入栈顺序是1，2，3 则出栈顺序无3，1，2！！！

这个结论是核心 关于输出序列这部分 有太多的题可以根据这一条排除选项

入栈顺序是1，2，3 则出栈顺序可以有
1，2，3
2，1，3
3，2，1
1，3，2
2，3，1

右边的图
1入 2入 2出 3入 3出
此时p1 为2 ，p2 为3，p3 可以取4~n的任意数
再结合左边的1，2两种情况
唯一不能取得数是3 是因为题目中说的p2为3

百度词条-卡特兰数

左子树个数从0~4 是五种 之间不重复，也不遗漏，没有交际的 用加法
左子树已知 得到右子树个数 是分步骤 是用乘法

其实这算的是构成排序二叉树的个数

f（0）是不画 也是一种画法 ， 不画和不能画是两回事