已知入栈顺序求所有的出栈顺序&&已知出栈顺序求所有的入栈顺序

2021年6月20日 2点热度 0条评论 来源: qq_38781075

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

已知入栈顺序是{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}出栈入栈顺序也满足前面红字的条件。

    原文作者:qq_38781075
    原文地址: https://blog.csdn.net/qq_38781075/article/details/103387665
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。