以出栈序列中数字 $1$ 的位置为基准，将出栈序列分为前后两部分。前半部分可以看成若干个数进行同样过程得到的序列，后半部分同理。

那么，设 $f(i)$ 表示 $i$ 个元素进行题目中描述的出入栈操作可能出现的输出序列总数。有:

$$f(1)=1$$ $$f(i) = f(0)f(i-1) + f(1)f(i-2) + \cdots + f(i-1)f(0) $$

递推计算即可，这是一个卡特兰数列。