假设栈的输入序列为1、2、3、...、n，求出所有可能的出栈序列 - 开源中国社区
假设栈的输入序列为1、2、3、...、n，设计算法求出所有可能的出栈序列（合法序列）。
比如 n = 4，出栈序列可能有1 2 3 4 ， 1 2 4 3 ， 1 4 3 2 ， 1 3 4 2等等
我使用递归来完成，主要思想：从1到n输入，每一个数只对应两个操作，一个是入栈，一个是出栈（输出），我用一个栈保存入栈元素，一个数组保存出栈元素（这里也可以使用栈，但是输出元素时，需要从反向输出）。
算法虽然简单，但是使用stack的时间代价相当高了，为什么不用数字的位模拟出入栈，用出入栈的顺序推导出数据输出的顺序？
Read full article from 假设栈的输入序列为1、2、3、...、n，求出所有可能的出栈序列 - 开源中国社区
假设栈的输入序列为1、2、3、...、n，设计算法求出所有可能的出栈序列（合法序列）。
比如 n = 4，出栈序列可能有1 2 3 4 ， 1 2 4 3 ， 1 4 3 2 ， 1 3 4 2等等
我使用递归来完成，主要思想：从1到n输入，每一个数只对应两个操作，一个是入栈，一个是出栈（输出），我用一个栈保存入栈元素，一个数组保存出栈元素（这里也可以使用栈，但是输出元素时，需要从反向输出）。
算法虽然简单，但是使用stack的时间代价相当高了，为什么不用数字的位模拟出入栈，用出入栈的顺序推导出数据输出的顺序？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| void print_valid_sequence(int i,const int n ) { static int number = 0;//记录序列的个数 static Stack<int> stack;//保存入栈的元素 static int array[10];//保存输出的元素 int top;//用来取top if(i == n+1)//递归结束条件，输出序列 { ++number; cout<<number<<"---"; for(int j = 0;j < n-stack.length();++j) cout<<array[j];//正序输出 stack.print();//输出 cout<<endl; } else { stack.push(i);//入栈 print_valid_sequence(i+1,n); stack.pop();//为保持stack不变，出栈 if(!stack.empty())//将栈顶元素输出 { stack.getTop(top); array[i-stack.length()-1] = top;//将输出的元素放入array中 stack.pop(); print_valid_sequence(i,n);//i不变 stack.push(top); } }} |
有2n个人排成一队进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票可找零，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？(将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈)。
对于这个例子，剧院要想总有零钱可找，那么目前进入剧院的人数中，揣着10元钞票的人数必须少于等于揣着5元钞票的，不然肯定在某个人那出现没零钱找的情况。
http://www.cnblogs.com/fxplove/articles/2500898.htmlRead full article from 假设栈的输入序列为1、2、3、...、n，求出所有可能的出栈序列 - 开源中国社区
