首页 > 其他 > 详细

递归输出出栈所有可能

时间:2014-03-06 22:22:43      阅读:585      评论:0      收藏:0      [点我收藏+]
bubuko.com,布布扣
 1      private static void DFS(Deque<String> in,Stack<String> stack,Deque<String> out) {
 2          if(0==in.size())          //输入队列空了
 3          {
 4              if(0==stack.size())      //栈也空了 输出结果
 5              {
 6                  for(Object obj:out.toArray())
 7                      System.out.print(obj);
 8                  System.out.println();
 9              }
10              else                //此时 输入队列空了,栈非空 则出栈处理
11              {
12                  out.addLast(stack.pop());
13                  DFS(in,stack,out);
14              }
15          }
16          else
17          {
18              if(0==stack.size())          //栈空就入栈
19              {
20                  stack.push(in.removeFirst());
21                  DFS(in,stack,out);
22              }
23              else
24              {                            //复制栈当前的状况,因为接下来有两种情况
25                  Deque inOld=new ArrayDeque<String> (in);    //1.栈的元素出栈
26                  Stack stackOld=new Stack();            //2.新的元素入栈
27                  Deque outOld=new ArrayDeque<String>(out);
28                             
29 //                 inOld=new ArrayDeque<String>(in);
30                 // Collections. ;
31 //                 for(Object obj:in.toArray())
32 //                     inOld.add(new String((String)obj));
33                  stackOld=(Stack) stack.clone();
34 //                 for(Object obj:out.toArray())
35 //                     outOld.add(new String((String)obj));
36                                                //在当前情况下 in inOld 这些都是相同的内容 所以以下朝两个方向发展


37                  out.addLast(stack.pop());              //栈的元素出栈的情况进行下去
38                  DFS(in,stack,out);
39                  
40                  stackOld.push(inOld.removeFirst());        //新的元素入栈的情况进行下去
41                  DFS(inOld,stackOld,outOld);
42                  
43              }
44          }
45     }
bubuko.com,布布扣

递归输出出栈所有可能,布布扣,bubuko.com

递归输出出栈所有可能

原文:http://www.cnblogs.com/friends-wf/p/3583919.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!