看似简单，实则很绕人的堆栈问题

Question

把1，2，3，4这四个数字分别放到栈里面，问有多少种放法，请用程序打印出来。
每个数字最多放进去2次拿出来1次。上面的那个问题我已经想了3天了。还是没有头绪，越绕越郁闷了！！
那个大哥能帮帮一下，最好能有个思路，小弟感激不尽啊

Answer 1

有点想法，请大家参考下：
请问是否可以看成 1，1，2，2，3，3，4，4的排列呢1.所有的排列（a1,a2,a3,a4,a5,a6,a7,a8）应该按位置顺序满足有1，2，3，4的
例如：1，2，3，1，4，2，3，4
2.现在问题变为对于1，2，3，4中间插入（1，2，3，4），
即：   现在把不动的1，2，3，4用A1，A2，A3，A4表示（A1=1,A2=2,A3=3,A4=4），
       要插入的用b1,b2,b3,b4表示(值是1，2，3，4的不同排列)。
      A4肯定要放到最后
      A1   A2   A3   A4
先只看每个数都拿2次的情况：
1.（b1,b2,b3,b4）分别插入到A1   A2   A3的前面或后面
2. （b1,b2）（b3,b4）分别插入到A1   A2   A3的前面或后面
3.（b1,b2,b3）（b4）分别插入到A1   A2   A3的前面或后面
说明一下：
这里面肯定有相同的排列，我们把上面3步中的（b1,b2,b3,b4），（b1,b2）（b3,b4），（b1,b2,b3）（b4）
理解为要拿出的数，虽然相同的排列，但是拿出数的顺序不一样，也应该不一样的
再看只拿3个数，2个数，1个数的情况，所有满足上述条件的应该就是了初步理解，请大家指导？？
  

Answer 2

6楼的，你说的“所以直接把1放进栈里,然后把1拿出来,再放进栈里,接着放2,3,4”，可是1拿出来之后不一定就再马上放进去，它可以等2放进去后再放，等3放进去后再放。这样看来远远不止你说的8种，注意：是“每个数字”都可以“2出1进”我现在有个思路大家看看：前面不管你怎么放，只要是到栈的最顶层的那个数，它已经是“2出1进”，我们可以看成他是一次“OVER”，下面的思路还在整理中。。

Answer 3

我理解成：最终在栈上有4个数字（即可以有24种结果），需要求解的是达到这个目标的方法数。
不知这种做法是否可行：不从数学上考虑，让程序做递归模拟。class StackProblem{
   private ArrayList<StackEvent> actions; //操作序列
   private StackEvent[] arrEvent; //当前状态可接受的事件
   private byte[] digitStates; //记录每个数字的状态
   /** 默认初始化,只要考虑第一步操作 */
   StackProblem(){
      //0,1,2,3分别表示未进栈,在栈中,已出栈,二次进栈
      digitStates = new byte[]{0,0,0,0};//所有数字未进栈
      //第一步操作,允许分别对数字1,2,3,4进栈
      arrEvent = new StackEvent[]{new PushDigit(1), ... };
   }
   /** 将event作用在问题last上,创建新的问题(状态) */
   private StackProblem(StackProblem last, StackEvent event) {
      this(last);//类似拷贝构造,复制操作序列、状态等
      applyEvent(event);//处理event,改变digitStates,actions
      arrEvent=getAvailableEvents();//获取当前状态下可操作步骤
   }
   /** 针对事件列表中的每个事件，递归处理 */
   void resolve() {
      for each event in arrEvent {
         problem = new StackProblem(this, event);
         problem.resolve();
      }
   }
}对于问题来说，StackEvent可以是push或pop，getAvailableEvents需要做的是判断下一步可以怎么操作；例如，第一步是数字3进栈，则第二步可以是3出栈或者1,2,4进栈4种方案；判断中，如果没有数字可进栈了，也就找到了一个解。