精华内容
下载资源
问答
  • 所有出栈序列 package ccnu.allTest;import java.util.ArrayList; import java.util.Stack;public class PrintPopSerial { public static void main(String[] args) { ArrayList<String> pops = popSerials(new
    • 所有出栈序列
    package ccnu.allTest;
    
    import java.util.ArrayList;
    import java.util.Stack;
    
    public class PrintPopSerial {
        public static void main(String[] args) {
            ArrayList<String> pops = popSerials(new char[]{'a', 'b', 'c', 'd'}, 0);
            int i = 0;
            for(String pop : pops){
                i++;
                System.out.println("第" + i + "个: " + pop);
            }
        }
    
        // push为指定的入栈字符,并且顺序从前至后依次入栈,begin为入栈序列的开始索引
        // 返回所有可能的出栈序列
        public static ArrayList<String> popSerials(char[] push, int begin){
            return popSerials(push, begin, new Stack<Character>(), new StringBuilder());
        }
    
        private static ArrayList<String> popSerials(char[] push, int begin, Stack<Character> s, StringBuilder sb){
            ArrayList<String> pops = new ArrayList<String>();
            if(push == null){
                return null;
            }
            s.push(push[begin]); // 将还没有入栈的字符序列的第一个字符入栈
            begin++;
            if(begin == push.length){ // 全部字符均已入栈
                while(!s.isEmpty()){
                    sb.append(s.pop());
                }
                pops.add(sb.toString());
            }else{
                // 进栈
                pops.addAll(popSerials(push, begin, (Stack<Character>)s.clone(), new StringBuilder(sb))); // 当前栈中的数据要递交给下一层使用,但要保证其中的数据不会被改变,当前已出栈字符保存在sb中,但要保证下一层调用使用它但不会改变本层的当前值,因此均要复制一份
                while(!s.isEmpty()){
                    sb.append(s.pop()); // 出栈
                    // 进栈
                    pops.addAll(popSerials(push, begin, (Stack<Character>)s.clone(), new StringBuilder(sb)));
                }
            }
            return pops;
        } 
    }
    
    展开全文
  • 已知出栈序列求所有的入栈序列头条实习一面的算法题,当时没有想出来,事后想起来求出栈序列的所有入栈序列和求进栈序列的所有出栈序列其实答案是一样的,所以只要按照求进栈序列的所有出栈序列来算就行了。...

    这题写错了:

    下面是错的
    已知出栈序列求所有的入栈序列头条实习一面的算法题,当时没有想出来,事后想起来求出栈序列的所有入栈序列和求进栈序列的所有出栈序列其实答案是一样的,所以只要按照求进栈序列的所有出栈序列来算就行了。
    why?
    A序列 进栈 -> B序列
    那么
    B序列 进栈必然可以得到 -> A序列
    然后用dfs就可以了,巧妙的很。

    public class AllPopSeq {
        @Test
        public void test() {
            //已知进栈序列,求出栈序列||已知出栈序列求所有的入栈序列
            //典型的卡特兰数
            // C(n) = (2n)!/((n+1)!*n!)  n = 4 C(n) = 14
            LinkedList<LinkedList<Integer>> linkedLists = allPopSeq(new int[]{4, 3, 2, 1});
            System.out.println(linkedLists.size());
            linkedLists.forEach((l) -> {
                System.out.println(l);
            });
        }
    
        public LinkedList<LinkedList<Integer>> allPopSeq(int[] input) {
            LinkedList<LinkedList<Integer>> result = new LinkedList<>();
            if (input == null || input.length == 0) {
                return result;
            }
    
            LinkedList<Integer> in = new LinkedList<>();
            LinkedList<Integer> temp = new LinkedList<>();
            LinkedList<Integer> out = new LinkedList<>();
    
            for (int i : input) {
                in.add(i);
            }
            allPopSeq(result, in, temp, out, input.length);
            return result;
        }
    
        private void allPopSeq(LinkedList<LinkedList<Integer>> result, LinkedList<Integer> in,
                               LinkedList<Integer> temp,
                               LinkedList<Integer> out, int len) {
            if (out.size() == len) {
                result.add(new LinkedList<>(out));
                return;
            }
            //出栈
            if (temp.size() > 0) {
                Integer t = temp.pop();
                out.add(t);
                allPopSeq(result, in, temp, out, len);
                out.pollLast();
                temp.push(t);
            }
            //入栈
            if (in.size() > 0) {
                Integer p = in.poll();
                temp.push(p);
                allPopSeq(result, in, temp, out, len);
                temp.pop();
                in.addFirst(p);
            }
        }
    }
    

    结果:

    //        14
    //        [4, 3, 2, 1]
    //        [4, 3, 1, 2]
    //        [4, 2, 3, 1]
    //        [4, 2, 1, 3]
    //        [4, 1, 2, 3]
    //        [3, 4, 2, 1]
    //        [3, 4, 1, 2]
    //        [3, 2, 4, 1]
    //        [3, 2, 1, 4]
    //        [3, 1, 2, 4]
    //        [2, 3, 4, 1]
    //        [2, 3, 1, 4]
    //        [2, 1, 3, 4]
    //        [1, 2, 3, 4]
    
    展开全文
  • 一、出栈序列判断 问题:按1、2、3、4、5进栈,出栈是否能得到1、2、3、4、5?是否能得到3、4、5、1、2? 答案:可以得到1、2、3、4、5,只要1进栈,1出栈,2进栈,2出栈以此类推即可得到1、2、3、4、5;但是不...

    一、出栈序列判断
    问题:按1、2、3、4、5进栈,出栈是否能得到1、2、3、4、5?是否能得到3、4、5、1、2?
    答案:可以得到1、2、3、4、5,只要1进栈,1出栈,2进栈,2出栈以此类推即可得到1、2、3、4、5;但是不能得到3、4、5、1、2(为什么?)。
    二、算法思想
    如果使用暴力破解的方法,n个数的进栈序列,可以有C(2n,n)/(n+1)个(卡特兰(Catalan)数),然后判断出栈序列是否属于其中,但是复杂度过大。
    利用编译原理中判断表达式是否合法的思路,再利用一个辅助栈即可解决问题。首先用两个指针分别指向进栈序列和出栈序列的初始位置,然后遍历进栈序列,先把每个进栈序列的元素压入辅助栈中,接着遍历栈中元素,条件是出栈序列的指针还未溢出而且辅助栈栈顶元素等于出栈序列的指针所指向的值,辅助栈执行出栈操作并且出栈序列的指针后移(这里说的指针有点合适),最后判断辅助栈是否为空,如果为空,出栈序列合法,如果不为空,不合法。下面用表格来详细解释3、4、5、1、2为什么不合法。
    这里写图片描述
    进栈序列遍历结束,辅助栈中还有元素,说明该出栈序列不合法。(1在2之前进栈,由于栈先进后出的规则,不可能在2之前出栈)
    【注】其中粗体数字表示当前指针指向的位置
    三、代码

    public boolean IsPopOrder(int [] pushA,int [] popA) {
        //入栈序列为空
        if(pushA.length==0)
            return false;
        //设一个辅助栈
        Stack<Integer> stack = new Stack<Integer>();
        int i=0,j=0;
        //遍历入栈队列,i指向入栈队列,j指向出栈队列
        while(i<pushA.length){
            //进栈序列首先进栈,进栈后i后移一位
            stack.push(pushA[i++]);
            //遍历栈中元素
            while(j<popA.length&&stack.peek()==popA[j]){
                stack.pop();
                //j后移一位
                j++;
            }
        }
        //如果栈为空,序列合法,否则不合法
        return stack.empty();
       }
    展开全文
  • 关于出栈序列的个数的计算方法

    千次阅读 2019-10-08 07:01:24
    首先是结论:n个不同元素进栈出栈序列的个数为卡特兰数:1/(n+1)*Cn2n 如a,b,c依次入栈,出栈时有可能: a进栈;b进栈;c进栈;一起出栈,最终为cba a进栈出栈;b进栈出栈;c进栈出栈,最终为abc a进栈...

    首先是结论:n个不同元素进栈,出栈序列的个数为卡特兰数:1/(n+1)*Cn2n

     

    如a,b,c依次入栈,出栈时有可能:

    1. a进栈;b进栈;c进栈;一起出栈,最终为cba
    2. a进栈出栈;b进栈出栈;c进栈出栈,最终为abc
    3. a进栈出栈;b进栈;c进栈出栈;b出栈,最终为acb
    4. a进栈;b进栈出栈;c进栈出栈;a出栈,最终为bca
    5. a进栈;b进栈出栈;a出栈;c进栈出栈,最终为bac

    备注:如果要求列出所有可能,先写出所有情况再挨个分析是最稳妥的方法:

    eg:入栈顺序为1,2,3,4,出栈顺序有哪几种?1234√ 1243√ 1324√ 1342√ 1423× 1432√
    2134√ 2143√ 2314√ 2341√ 2413× 2431√
    3124× 3142× 3214√ 3241√ 3412× 3421√
    4123× 4132× 4213× 4231× 4312× 4321√
    14种可能,10种不可能


    转载于:https://www.cnblogs.com/yueMa/p/9250164.html

    展开全文
  • 1.判断出栈序列是否合法 模拟入栈过程,为了测试出栈序列是否正确,将元素按顺序入栈进行模拟。如果能够利用栈模拟出出栈次序,说明序列正确。 将序列存在队列中,将元素按顺序入栈,如果和队列首部元素相等,则弹出...
  • package ... import java.util.Stack; /** * @Author JH * @CreateDate 18-6-9 * @Description 判断给定出栈序列是否符合 进栈次序的出栈可能 * 利用辅助栈 */ public class IsPopOrde...
  • Catalan应用 输出所有N对合法括号序列 输出所有已知进栈序列的合法出栈序列 http://blog.csdn.net/ssuchange/article/details/17394609
  • 已知进栈序列,求出栈序列

    千次阅读 2016-10-09 20:01:33
    #include #include int count=0; char a[10]; void perm(char a[],int k,int n) { int i,u,v,w,flag; char temp,t[10]; strcpy(t,a);... printf("所有出栈序列为:\n"); perm(a,0,strlen(a)-1); }
  • 栈 - 关于出栈序列,判断合法的出栈序列

    万次阅读 多人点赞 2017-11-09 20:26:36
    (例)设栈的入栈序列是 1 2 3 4,则下列不可能是其出栈序列的是( )。 A. 1 2 4 3 B. 2 1 3 4 C. 1 4 3 2 D. 4 3 1 2 E. 3 2 1 4 一般人看到此类题目,都会拿起草稿纸,将各个选项都模拟一遍选出正确...
  • 关于n个数进栈出栈的出栈序列个数问题 原题来源于洛谷:P1044 [NOIP2003 普及组] 栈 分析:一种解法是使用卡特兰数论知识,另外一种则是用递归。以下是递归做法。用dp[n][m]表示当剩余n个数未进栈,m个数在栈中时...
  • 思路:利用一个辅助栈和一个指向出栈序列第一个元素的下标(int count = 0;),利用一个循环在入栈的同时就判断当前入栈元素是不是当前下标指向出栈元素,是的话移除栈顶元素,并使下标加一,继续入栈,直到完成入栈...
  • 通过算法判断进栈出栈序列是否合法 代码如下: #将序列存入列表 stack = input("将序列存入列表\n") stack = stack.split(' ') print(stack) #建立一个空栈 stack1 = [] #输入序列 i = 0 while i < len(stack)+1:...
  • 判断出栈序列

    2014-10-27 00:50:19
    对于一个栈,已知元素的进栈序列,判断一个由栈中所有元素组成的排列是否是可能的出栈序列。 比如,进栈序列为1 2 3 4,则可能的出栈序列有4 3 2 1,1 4 3 2等。而1 4 2 3就不是。 【输入形式】 从标准输入读取...
  • c++特定序列进栈出栈顺序

    千次阅读 2017-11-04 23:49:25
    给定两个字符串,要求所有的进栈出栈序列(i表示进栈,o表示出栈),使得字符串2在求得的进出栈序列的操作下,变成字符串1。输出结果需满足字典序。例如TROT 到 TORT: [ i i i i o o o o i o i i o o i o ]
  • 这么说吧,网上的解释看着蛋疼,...现在有一个容量为m的栈S,有n个元素在栈S顶端一侧等待进栈,另一侧是出栈序列。现在要使用push和pop这两种操作,由一个操作序列可以得到一系列的输出序列。请你编程求出对于给定的...
  • 卡特兰公式 f(n)=c(2n,n)/n+1 问题:若一序列进栈顺序为e1,e2,e3,e4,e5,问存在多少种可能的出栈序列 答案:42 f(0) = 1 f(5) = 42 f(5)=C(10,5)/6 = (109876)/(54321) / 6 = 42
  • 栈先进后出,就是第一个进来的时候最后一个...因3出栈,后面要么2出栈,要么4进栈出栈,所以3的后面不是2就是3,而选项A后面是1,所以A不是正确的,不符合先进出。 选项B是1先进栈再出栈,然后2、3、4进栈,再4...
  • 出栈序列程序

    2014-12-02 16:53:51
    判断序列是否为合法的出栈序列,利用C语言编写
  • 出栈序列

    2020-03-12 18:22:53
    输出:第一行输出出栈序列个数,接下来每行输出一个序列 分析 深搜,模拟进栈,出栈过程。 void dfs(int index, int n, int l, int o, stack<char> in, queue<char> out) index:第几次过程,从0开始 n...
  • //任务:判断进栈出栈序列是否合法 bool Legical(char* str) { int j=0,i=0; while (str[i]!='\0') { if (str[i] == 'I') j++; else j--; i++; if (j < 0) { //cout << j; return...
  • import java.util.ArrayList;public class Solution { public boolean IsPopOrder(int [] pushA,int [] popA) { for(int i=0;i&lt;popA.length;i++){ if(ofIndex(pushA,popA[i])==-1) return f...
  • 某城市有一个火车站,铁轨铺设如图6-1所示。有n节车厢从A方向驶入车站,...例如,出栈顺序(5 4 1 2 3)是不可能的,但(5 4 3 2 1)是可能的。 #include<cstdio> #include<stack> using namespace...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,964
精华内容 3,985
关键字:

出栈序列与进栈序列