若一个数值为1、2、3、4的序列顺序进栈，另一个数组a[4]存放通过栈而生成的出栈数值。若把进栈操作记为S，出栈操作记录为X，那么进栈和出栈的操作可以（在合法范围内）任意地交叉进行，例如SXSXSXSX操作使得a[0]到a[3]中分别得到1、2、3、4的数值，而SSSSXXXX操作使得a[0]到a[3]中分别得到4、3、2、1的数值。 （1）可能的出栈序列共有多少个？（不需要写具体的序列） （2）列出所有不可能由数值1、2、3、4通过进栈和出栈操作而形成的序列

(1) 由于一个数进栈后只能出栈一次，因此4个数进栈后最多有4!种出栈序列，即24种。

(2) 不可能的出栈序列有以下几种情况：

- 以X开头，但除了最后一个X外，其它X的后面都是S，例如XSSS、XSXSSS等；
- X的个数大于S的个数，例如SSXX、SXSXX等；
- 在X的个数等于S的个数时，出栈序列不以X结尾，例如SSX、SSSX等。

这些序列都不可能由数值1、2、3、4通过进栈和出栈操作而形成。