1,2,3,4按顺序入栈，出栈顺序随意，列出所有可能情况，这个算法如何写

1,2,3,4按顺序入栈，出栈顺序随意，列出所有可能情况，这个算法怎么写
这个问题大家应该都知道吧，我想了一节课也没想出来，求助呀
------解决方案--------------------
这就是那什么阿里的面试题是吧？
说实话刚看这题我也搞不懂，进栈1234，出栈不就4321嘛
后来看到有人问才知道，原来它的题意是：
1,2,3,4按顺序入栈，出栈顺序随意，并且在进栈的过程中可以出栈，列出所有可能情况
 这就是简单的逻辑题了。。
所以我讨厌这些SB的面试题
------解决方案--------------------
计算机考研经常出现的题目。其实题目意思是这样的：1,2,3,4,顺序入站，并不要求一次性全部入站，比如1入站，再出站；2,3,入站，3出战；4入站；最后4,2出战，这时候就是：1,3,4,2
情况还有比较多，貌似有个公式的，可以算出各种情况的总数

至于要用算法写出来，模拟入站出站就行啦

------解决方案--------------------
组合数学中什么多项式，好像能解决这个问题
------解决方案--------------------
用递归写的

template <typename T>

void StackInOut<T>::simulateStack(std::vector<T>& originData, std::stack<T>& stackData, std::vector<T>& tempData)

{

	if (originData.size() == 0 && stackData.size() == 0)

	{

		this->out_data.push_back(tempData);

		return;

	}

	else if (originData.size() != 0 && stackData.size() == 0)

	{

		T tempT = originData.back();

		originData.pop_back();

		stackData.push(tempT);

		simulateStack(originData, stackData, tempData);

	}

	else if (originData.size() ==0 && stackData.size() != 0)

	{

		tempData.push_back(stackData.top());

		stackData.pop();

		simulateStack(originData, stackData, tempData);

	}

	else

	{

		std::vector<T> tempBranchData = tempData;

		std::vector<T> origionBranchData = originData;

		std::stack<T> stackBranchData = stackData;


		//出栈

		tempData.push_back(stackData.top());

		stackData.pop();

		simulateStack(originData, stackData, tempData);


		//入栈

		T tempT = origionBranchData.back();

		origionBranchData.pop_back();

		stackBranchData.push(tempT);

		simulateStack(origionBranchData, stackBranchData, tempBranchData);

	}

}

------解决方案--------------------
Catalan式，能求出所有出栈情况的个数，但是不能求出具体情况。用动态规划