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

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