精华内容
下载资源
问答
  • 出栈顺序

    2017-06-15 17:18:00
    之前参加过华北计算机研究所和优酷土豆的笔试,都考到出栈顺序,之前数据结构学的不到位,遇到这类题时,还着实把我愣了一会,现在总结下,省得以后再遇到这类问题,也希望能给遇到同样问题的兄弟们一个参考。...

    之前参加过华北计算机研究所和优酷土豆的笔试,都考到出栈顺序,之前数据结构学的不到位,遇到这类题时,还着实把我愣了一会,现在总结下,省得以后再遇到这类问题,也希望能给遇到同样问题的兄弟们一个参考。

          废话不多说,直接上个例题。

    一个栈的入栈序列是a,b,c,d,e则栈的不可能的输出序列是:()
    
    A edcbd         B decba           C dceab            D abcde

           栈之根本——后进先出(Last In First Out , LIFO)初次接触到这个问题的人,或许会认为入栈abcde,所以出栈只能是edcba所以BCD都不对。

          其实是这个问题描述有歧义,应该是分段入栈的顺序,也就是说,可能先入栈a,取出a,入栈b,取出b……,所以D也是可能的。

          知道这个意思了以后,就要明确这个问题的矛盾根本所在:第一次出栈d,说明什么?说明a,b,c一定早已入栈(入栈顺序决定的)。那么在出栈d以后,a,b,c的出栈顺序一定是c,b,a,而不用理会中间穿插着出栈了d后面的字符(因为可以再入栈,再出栈嘛)。所以立即选中C,不用犹豫,理由简单:d出栈了,abc一定已经入栈,那么abc只能以cba的顺序出栈,C不符合,OK!

          举一个更加直观的例子:

    如栈顺序是:1 2 3 4 ,如何正确理解出栈?

         (1)入栈顺序是1 2 3 4,就是指这四个数依次入栈:
    数据4入栈之前,1 2 3肯定已经入栈了;
    数据3入栈之前,1 2肯定已经入栈了,而4还没入栈;
    数据2入栈之前,1肯定已经入栈了,而2 3 4还没入栈;
    数据1最先入栈,2 3 4还没入栈。
        (2)既然入栈顺序是1 2 3 4,3 4入栈的时候,1 2 肯定已经入栈了,怎么会在后面再入栈。
        (3)先拿4 3 1 2这个出栈序列来说,4最先出来,说明此时1 2 3(底到顶顺序)还都在栈中;接下来只有3能出栈,3出来后,栈中为1 2(底到顶顺序);再接下来只有2能出栈,所以如果出栈序列前两个是4 3的话,后两个只能是2 1。
    再看个正确的出栈序列:2 4 3 1;2最先出来,说明它出来时,3 4还没入栈,而1已入栈且还在栈中;接着是4出来,说明此时3也在栈中(3要比4先入栈),此时栈中有1 3(底到顶顺序);然后只能3出栈,最后是1出栈。
         

    总之,挨个看出栈序列的数据,根据入栈顺序,分析它出来时,栈中应该还有谁,而有谁还没入栈,然后分析此时可不可能是它出栈。

     

    下面针对具体问题,编程来进行分析。

    输入一个压栈序列,判断第二个序列是否为其出栈序列。
    
    例如:入栈序列:1 2 3 4 5 6,出栈序列,4,3,5,2,6,1

    算法思想,1:根据出栈序列,入栈,直到其栈顶等于出栈元素,栈s:4,3,2,1

                     2:栈顶与出栈序列相同出栈,否则break

    根据入栈序列入栈:(左为栈顶)

                   栈:1 2 3 4            1 2 3                1 2 5             1 2                   1 6                1                      |空

     出栈元素: 4 3 5 2 6 1 , 4 3 5 2 6 1 ,4 35 2 6 1,4 3 5 2 6 1 ,4 3 5 26 1 ,4 3 5 2 61 ,完

    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
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    #include <iostream> 
    #include <stack> 
    using  namespace  std; 
    bool  IsStackPopOrder( int  *pushorder, int  *poporder, int  len) 
    {    
         bool  isorder =  false
         if (pushorder!=NULL && poporder != NULL && len > 0) 
        
             stack< int > s; 
             int  *pnextpush = pushorder; 
             int  *pnextpop = poporder; 
             while ((pnextpop - poporder) < len) 
            
                 while (s.empty()||s.top()!=*pnextpop) 
                
                     if ((pnextpush - pushorder)==len)
                         break
                     s.push(*pnextpush); 
                     pnextpush++; 
                
                 if  (s.top() == *pnextpop) 
                
                     s.pop(); 
                     pnextpop++; 
                
                 else
                     break
            
             if  ((pnextpop - poporder)==len && s.empty())
                 isorder =  true
        
         return  isorder; 
    void  main() 
         int  array1[7] = {1,2,3,4,5,6,7}; 
         int  array2[7] = {4,3,5,6,7,1,2}; 
         if (IsStackPopOrder(array1,array2,7))
             cout<< "是" <<endl; 
         else
             cout<< "否" <<endl; 
         system ( "pause" ); 




    本文转自夏雪冬日博客园博客,原文链接:http://www.cnblogs.com/heyonggang/p/3360037.html,如需转载请自行联系原作者
    展开全文
  • 一、已知入栈顺序求所有的出栈顺序 已知入栈顺序是{1,2,3,4,5},求所有的出栈顺序? 我的思路: 既然入栈顺序固定,我觉得可以使用递归来做。 先定义一个函数,比如说叫做help。 //伪代码 void help(vetcor<...

    一、已知入栈顺序求所有的出栈顺序

    已知入栈顺序是{1,2,3,4,5},求所有的出栈顺序?

    我的思路:

    既然入栈顺序固定,我觉得可以使用递归来做。

    先定义一个函数,比如说叫做help。

    //伪代码
    void help(vetcor<int> &v,int i,stack<int> s,vetcor<int> vv)
    {
      //v是入栈顺序v={1,2,3,4,5}
      //i用来记录下标的位置
      //s用来存储入栈的情况
      //vv中记录一次出栈的顺序
      //i一开始等于0,代表即将用v的第一个元素1入栈
      //接下来将会发生两种情况
      //要么(当i等于0的时候,即v[i])1入栈,s中push一个1进去,代表入栈,i++,递归
      //(假设s中有元素,当然没有元素就跳过这一步)要么s中的元素出栈,vv中记录出栈的顺序,递归
      //当vv的size与v的size相等时,代表已经存储完一次出栈的顺序了,接下来就不用递归了。
    }

    二、已知出栈顺序求所有的入栈顺序

    已知出栈顺序是{1,2,3,4,5},求所有的入栈顺序?

    我的思路:

    首先要明白一点,先看末尾元素5,5要么是第一个入栈的,要么是最后一个入栈的

    所以入栈顺序是{5,(1,2,3,4)}或者{(1,2,3,4),5},5的顺序确定了,而1234的顺序位置不知道,但是我们可以使用跟上面同样的思路做,4要么是第二个入栈的,要么是倒数第二个入栈的,不能中途入栈,按照这个思路递归求解。

    更新:后来发现了第三种情况,5可以中途入栈,比如入栈顺序{1,2}{5,4,3},首先{1,2}以任意顺序入栈出栈,其实就是当做{1,2}不存在,入栈就出去了,之后再{5,3,4}入栈,就是我们现在只看{3,4,5}这三个元素,仍然是满足我前面说的条件,即5要么是第一个入栈的,要么是最后一个入栈的。并且{1,2}出栈入栈顺序也满足前面红字的条件。

    展开全文
  • 入栈出栈顺序

    千次阅读 2019-04-09 15:35:09
    入栈出栈顺序

    转自:https://blog.csdn.net/qq_1932568757/article/details/82752325

    问题:已知入栈顺序,找出不可能得出栈顺序。

    已知一个栈得入栈顺序为ABCDEF,则不可能得出栈序列是( D )
    A:DEFCBA
    B:DCEFBA
    C:FEDCBA
    D:FECDBA
    E:ABCDEF
    F:ADCBFE
    

    规律:任何出栈的元素后面出栈的元素必须满足以下两点:

    • 在原序列中相对位置比它小的,必须是逆序;
    • 在原序列中相对位置比它大的,顺序没有要求;

    分析:选项D的出栈顺序FECDBA,出栈元素F后面的元素C和D不满足上面规律1,所以选项D错误,其它答案都是满足的。

    展开全文
  • 已知入栈顺序,总结出栈顺序的规律

    万次阅读 多人点赞 2019-01-23 09:33:12
    规律: 出栈的每一个元素的后面,其中比该元素先入栈的一定按照入栈逆顺序排列。 举例说明: 已知入栈顺序: 1 2 3 4 5 判断出栈顺序: 4 3 5 1 2 结果:不合理,原因是出栈元素3之后有 5 1 2 这三...判断出栈顺序:...

    规律:

    出栈的每一个元素的后面,其中比该元素先入栈的一定按照入栈逆顺序排列。

    举例说明:
    已知入栈顺序: 1 2 3 4 5
    判断出栈顺序: 4 3 5 1 2
    结果:不合理,原因是出栈元素3之后有 5 1 2 这三个元素,其中1 2 是比3先入栈的,根据规律,这两个出栈的顺序必须和入栈顺序相反,也就是 2 1 出栈,不可能按照1 2 顺序出栈。

    已知入栈顺序: 1 2 3 4 5
    判断出栈顺序: 2 1 3 5 4
    结果:合理,逐个判断,2后面比它先入栈的是“1”,单个元素当然可以;1后面无比它先入栈的,故不需要比较;3后面无比它先入栈的,故不需要比较;5后面比它先入栈的是“4”,单个元素当然可以,4后面没有元素,不需要比较。

    展开全文
  • 入栈,出栈顺序

    2021-08-11 14:39:57
    入栈,出栈顺序 在刚开始做到栈的出栈入栈时还是蛮有疑惑的,搞不清楚出入栈的排序重新整理之后终于明白,具体如下所示: 例如有一个为A B C D E的顺序排列,要问该排列的出栈的情况,实际上在进行出入栈时并不要求...
  • 栈的出栈顺序问题

    2013-06-02 19:57:41
    对于栈,大家并不陌生,先进后出的嘛。但是它到底有多少种出栈顺序呢?以及具体是怎么出栈的呢?具体每一种出栈顺序呢?本实验代码给出了答案和思路。还望参考。
  • 判断出栈顺序是否正确

    千次阅读 2016-04-23 15:35:13
    给定压栈顺序和出栈顺序,判断出栈顺序是否正确
  • 我们知道栈是一种先进后出的数据容器。当一个栈的输入序列是递增...在输入序列为递增序列的假设下,请编写一个算法判断输入的字符串表示的出栈序列是否为正确的出栈序列。例如:输入的字符序列为dcba,则返回值为tru...
  • java判断出栈顺序是否正确我们知道栈是一种先进后出的数据容器。当一个栈的输入序列是递增序列(例如a,b,c,d),并且在进栈操作时,允许退栈操作,则输出的序列可能有多种形式(例如:d,c,b,a或a,c,b,d等)。但是却肯定...
  • 本文分析了无重复入栈序列对应的出栈顺序的个数,给出解决出栈顺序的算法,并编程打印出所有出栈顺序
  • 出栈顺序问题讲解 蓝桥杯

    千次阅读 多人点赞 2019-03-14 20:41:19
    引言:最近刷数据结构的题,刷到一组元素入栈,他的出栈顺序有可能是哪些时卡住,之前没有关注此类问题,便写下总结 先通过几个例题讲解下出栈顺序问题 1. 一个栈的入栈序列是a,b,c,d,e则栈的不可能的输出序列是...
  • C++判断出栈顺序

    千次阅读 2017-10-08 15:49:17
    C++判断出栈顺序
  • 出栈顺序问题

    2018-08-12 00:01:00
    规律是:答案中出栈的第一个元素是在原来的次序中是第几个...如DCEAB的顺序是不可能的,因为如果D是首个,那么ABC必在栈中,无论E在什么时候入栈和出栈,D之后的出栈顺序必有CBA的大致顺序,可见不会出现这种顺序。...
  • 不可能的出栈顺序

    千次阅读 2018-09-27 10:49:31
    思路:入栈为ABCDE,出栈就不可能是DCEAB,因为D第一个出栈说明ABC仍在栈中,无论E什么时候入栈都会保持C B A的出栈顺序 题目:一个栈的输入顺序是a,b,c,d,e则下列序列中不可能是出栈顺序是() A:e,d,a,c,b B:a,e,d,c,...
  • 根据入栈顺序求出栈顺序

    千次阅读 2016-09-18 20:05:54
    题目描述:给定一个序列B表示入栈的顺序,求所有的不可能出栈顺序和可能的出栈顺序 题目分析:当一个元素入栈后,紧着接着入栈的元素可以是该元素后面的任意一个元素,或者是该元素前面的离该元素最近的一个未出栈...
  • 给定入栈顺序,求所有可能的出栈顺序

    万次阅读 多人点赞 2017-10-22 08:51:28
    那么怎么样得到所有的具体出栈顺序呢,有两种思路可以解决这个问题。 1.先得到入栈字符串的全排列,然后根据出栈顺序的规律进行筛选。 那么筛选的条件是什么? 举例说明 入栈顺序:1 2 3 4 5  出栈顺序:3...
  • 1. 判断出栈顺序是否正确 给出元素进栈顺序,判断出栈序列是否合法。 例如: 入栈1,2,3,4,5 出栈4,5,3,2,1 可判断其出栈顺序合法。 2. 解法 借用一个辅助的栈,遍历压栈顺序,先将第一个放入栈中,这里是1,...
  • 栈的出栈顺序规律

    2020-08-28 19:35:26
    栈的出栈顺序规律 任何出栈的元素后面出栈的元素必须满足一下两点: 在原序列中相对位置比它小的,必须是逆序 在原序列中相对位置比它大的,顺序没有要求 ** 注:仅用于学习交流**
  • [PTA天梯赛出栈顺序

    2020-12-05 13:17:17
    PTA天梯赛出栈顺序 多种写法,容器,数组
  • 出栈顺序 递归

    2018-03-14 12:10:31
    题目2:出栈顺序:X星球特别讲究秩序,所有道路都是单行线。一个甲壳虫车队,共16辆车,按照编号先后发车,夹在其它车流中,缓缓前行。路边有个死胡同,只能容一辆车通过,是临时的检查站,如图所示。X星球太死板,...
  • 序列所有可能的出栈顺序

    千次阅读 2017-10-30 09:47:09
    序列所有可能的出栈顺序,思路如下: 先找到该序列的全排列,然后再检查全排列中每一个序列的出栈合法性,合法则输出。
  • 判断出栈顺序是否合理

    千次阅读 2018-04-14 23:05:21
    题目描述:给出一组入栈顺序,再给出出栈序列,判断出栈顺序是否合理算法思路:比如 入栈顺序 a b c d;下列出栈顺序:a b c d 正确 d c a b 错误算法描述:设置一个中间栈,将输入输出放入两个数组,设置一个索引...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 80,089
精华内容 32,035
关键字:

出栈顺序