一个栈的输入序列为a,b,c,d，若在入栈的过程中允许出栈，则或许得到的出栈序列是什么

一个栈的输入序列为a,b,c,d，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？
一个栈的输入序列为a,b,c,d，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？

请大虾们帮忙分析一下,给出结果和注解... 小弟非常感谢!!
------解决方案--------------------
所有可能的出栈次序如下:
abcd  abdc  acbd  acdb
adcb  bacd  badc  bcad
bcda  bdca  cbad  cbda
cdba  dcba
------解决方案--------------------
卡特兰数
------解决方案--------------------
栈的问题就是先进后出，且进栈后即可立即出栈，我举个不可能的列子，你更容易理解些：
------解决方案--------------------

cadb；如果c在第一位，那么说明栈里边已经存在a、b（都在c前边进栈），则a先进，那么a就不可能先出