栈是一种重要的数据结构，其主要的操作包括入栈和出栈。请编写程序，对任意给定的n，输出1，2，…，n的所有出栈顺序及其总数。
我用两种方法写了！第二种方法我写了好几天，自己的编程能力还不行啊！要多锻炼锻炼！还有总数应该用卡特兰数求的，我投机取巧了！各位大侠要是能帮忙改进就好了！
algorithm1:
设计：先求出全排列，再判断是否为正确的出栈顺序！
分析：算法时间复杂度为O(n^3), 效率很低！空间复杂度为O(1);
algorithm1 1 /* 2 * To change this template, choose Tools | Templates 3 * and open the template in the editor. 4 */ 5 6 /** 7 * 8 * @author Administrator 9 */
10 import java.util.*;
11 public class stack_algorithm1 {
12 public static int all;
13 public static void main(String[] args) {
14 int total;
15 int [] stack;
16 Scanner reader = new Scanner(System.in);
17 total = reader.nextInt();
18 stack = new int [total];
19 for (int i = 0; i < stack.length; i++) {
20 stack[i] = i+1;
21 22 }
23 ShowTruePop(stack,0,stack.length-1);
24 System.out.println("Total: "+all);
25 }
26 public static void ShowTruePop(int [] stack,int start,int end){
27 int test [] = new int [stack.length];
28 if(start==end){//当只要求对数组中一个进行全排列时，只要就按该数组输出即可
29 for(int i=0;i<=end;i++){
30 test[i] = stack[i];
31 }
32 if (IsTruePop(test)) {
33 for (int i = 0; i < test.length; i++) {
34 System.out.print(test[i]+" ");
35 36 }
37 System.out.println();
38 all++;
39 }
40 41 }
42 else{//多个字母全排列
43 for(int i=start;i<=end;i++){
44 int temp=stack[start];//交换数组第一个元素与后续的元素
45 stack[start]=stack[i];
46 stack[i]=temp;
47 48 ShowTruePop(stack,start+1,end);//后续元素递归全排列
49 50 temp=stack[start];//将交换后的数组还原
51 stack[start]=stack[i];
52 stack[i]=temp;
53 }
54 55 }
56 }
57 public static boolean IsTruePop(int [] test){//判断是否为正确的出栈
58 for (int i = 0; i < test.length-2; i++) {
59 for (int j = i+1; j < test.length-1; j++) {
60 for (int k = j+1; k < test.length; k++) {
61 if ((test[j] < test[k]) && (test[k] < test[i])) {
62 return false;
63 64 }
65 66 }
67 68 }
69 70 }
71 return true;
72 }
73 }algorithm2：
设计：1、若n=1那么就一种排列方式。2、n>1时先求出n-1的出栈顺序，再分开将n插入n-1之前，n-1之后和每一个n-1之后的每一个数！有点想数学归纳法的思想！
分析： 算法时间复杂度为O(c(n,2n)/（n+1))即为卡特兰数，效率很高。空间复杂度为O(c(n,2n)/（n+1))*n)占用空间比较大，是典型的以空间换时间！
aigorithm2 1 /* 2 * To change this template, choose Tools | Templates 3 * and open the template in the editor. 4 */ 5 6 /** 7 * 8 * @author Administrator 9 */
10 import java.util.*;
11 public class stack_algorithm2 {
12 public static void main(String[] args) {
13 int total = 0;
14 int [][] save = new int [300][];
15 Scanner reader = new Scanner(System.in);
16 int n = reader.nextInt();
17 int stack[] = new int [n];
18 for (int i = 0; i < stack.length; i++) {
19 stack[i]=i+1;
20 21 }
22 for (int i = 0; i < 300; i++) {
23 save[i] = new int [stack.length+1];
24 25 }
26 InnArr(stack,save);
27 System.out.println("The result is: ");
28 for (; save[total][0] != 0; total++) {
29 for (int j = 0; j < save[total].length-2; j++) {
30 System.out.print(save[total][j]+" ");
31 32 }
33 System.out.println(save[total][save[total].length-2]);
34 35 }
36 System.out.println("Total: "+total);
37 }
38 39 40 public static void InnArr(int [] stack,int [][]save){
41 int k = 1;
42 int p = 1;
43 save[0][0] = stack[0];
44 while(k
最新评论