Catlan数之栈的出栈序列-legend



栈的出队顺序问题：

（一）Catlan数：

（1）给出入栈序列，求出所有的出栈的序列个数：
 C（2n,n）/(n+1)；
（2）给出入栈序列，求出所有的出栈序列；
1）举例：
1、2、3这三个数字，入栈并出栈共有5种方式，分别为：321、312、231、213、123。
2）分析：

1.可以用队列（queue）来模拟输入，队列的输出则按照原先序列的顺序。使用一个栈（stack）来模拟入栈和出栈，结果保存在另外一个队列（queue）中。

2.怎么样可以实现所有的出栈入栈操作。首先来看看出栈和入栈是怎么回事，对于123这个序列，1先入栈之后有两种选择，1出栈和2入栈，而若2已经入栈之后，在2出栈之前1则不能先行出栈，故对于1我们只需要考虑其在2入栈之前出栈的情况，若1在栈内时2入栈，则1与2只能看成一个整体。

3。伪代码：
dostack(输入队列，中间栈，输出队列)

if(输入队列为空)

    if(中间栈为空)

        输出输出队列中的结果

    else

中间栈出栈，放入输出队列

dostack(输入队列，中间栈，输出队列)

else

    if(中间栈非空)

        新建输入队列2、中间栈2、输出队列2

        中间栈2出栈并放入输出队列2

dostack(输入队列2，中间栈2，输出队列2)

    输入队列出队一个数并压入中间栈

dostack(输入队列，中间栈，输出队列)

2）思想：
对于中间栈的每一个时刻拍照，都递归其后续的所有可能，由于在递归返回的时候还需要递归前的信息，所以每次递归都是新建数据结构而保存当前时刻的状态。若输入队列已经为空，则中间栈只有一种出栈方式，中间栈也为空时递归结束。

3）代码实现：

/*
 输入为序列的长度n，初始化序列为1,2,3…n，而输出则为所有可能的出栈数列。
 */#include <iostream>
 #include <stack>
 #include <queue>
 using namespace std; 
 int n,i,j;
 int res;//统计出队序列的个数
 stack <int> s;
 queue <int> in,out;//输入队列，输出队列/*将栈中所有元素出栈*/
 void clear(stack <int> &s)
 {
 while(!s.empty())
 s.pop();
 }/*将队列中所有元素出队*/
 void clear(queue <int> &s)
 {
 while(!s.empty())
 s.pop();
 }/*输出队列中所有的元素*/
 void print(queue <int> i)
 {
 while(!i.empty())
 {
 cout<<i.front();
 i.pop();
 }
 cout<<endl;
 } /*递归，给出入栈序列，求出所有的出栈序列，
 in,保存入栈序列；
 out,保存出栈序列；
 stack来模拟入栈还是出栈；
 */ void dostack(queue <int> in,stack <int> s,queue <int> out)
 {
  if(in.empty()){//入队序列为空
   if(s.empty()){//模拟入栈，出栈的栈为空
    res++;
    print(out);
   }
   else{
    out.push(s.top());//中间栈出栈，并放入到输出队列中；
    s.pop();
             dostack(in,s,out);
   }
  }
  else{//入队序列非空  if(!s.empty()){//中间栈非空
    stack <int> ts;//中间栈，输入队列，输出队列的拷贝。
    queue <int> tin,tout;
    tin=in;
    ts=s;
    tout=out;
    tout.push(ts.top());//中间栈的拷贝弹出一个元素到输出队列的拷贝。
    ts.pop();
             dostack(tin,ts,tout);
   }  s.push(in.front());//取输入队列的下一个元素到中间栈中。
   in.pop();
   dostack(in,s,out);
  }
 }/*测试函数*/
 int main()
 {
 while(cin>>n)
 {
 res=0;
 clear(in);
 clear(out);
 clear(s);
 for(i=n;i>=1;i--)
 in.push(i);
 dostack(in,s,out);
 cout<<res<<endl;
 }
 return 0;
 }
  -- --

方法二：
将所有的可能序列都给出，然后排除那些不合法的序列。
（参考，查看一个序列是否为出栈序列）
---
（3）给出入栈序列，判断一个序列是否为出队序列；

1）举例：

入栈序列为1,2,3,4,5 某一序列为 2,3,1,4,5 。首先选择1 入栈，然后查看序列2 是否相同，不同说明没有出栈，继续入栈2，继续查看 相同，说明2出栈，然后继续查看是否相同1和3不同，继续入栈3，查看和序列2中的头元素3一致，出栈，继续查看序列1中的1，和序列2中的1 一致，然后出栈。。。直到最终序列2为空；如果最后发现序列1为空的时候序列2中仍然有元素，则说明不是合法出栈序列；

2）思想：
1.每次入栈一个元素，下一步有两个选择，1.当前栈顶元素出栈，2.继续将下一个入队序列的元素入栈；

2.将入栈序列的i号元素（初始化i=0）入栈；
3.然后取栈顶元素，与测试的出队序列的当前元素j（初始化j=0）比较，如果相等，则说明i号元素出栈了；
如果不相等，则说明i号元素的下一个元素入栈，所以继续将i号元素的下一个元素入栈。

3）步骤：
1.建立一个栈；将入栈序列的当前cur_in号元素(初始化cur_in=0)压栈；
2.栈顶元素与出队序列的当前元素cur_out(初始化cur_out=0)比较 ;
3.如果不等，则cur_in++,将当前元素cur_in入栈；
4.如果相等，则出栈一个元素，同时cur_out++；然后重复2
5.最终判断栈是否为空，如果为空，则表示是出栈序列。

4）代码实现：

测试代码如下：

#include <iostream>
 #include <stack>
 using namespace std;int main(){
     int arr[] = {1,2,3,4,5};//入栈序列
     int arr2[] = {2,1,5,3,4};
     stack<int> stk;
     int j = 0;
     for(int i = 0;i < 5;i++){
         stk.push(arr[i]);    
         if(stk.top()!=arr2[j])continue;
         while(stk.size()>0){
             if(stk.top() == arr2[j]){
                 j++;
                 stk.pop();
             }else break;
         }
     }
     if(stk.size()!=0){
         cout << "no" << endl;    
     }
     else cout << " yes " << endl;
     return 0;
 }

方法二：利用结论
在a之前进栈的元素，出现在出队序列的a之后，则这些元素必定逆序。

------
（二）出队顺序问题：
（1）结论：
在a之前进栈的元素，出现在出队序列的a之后，则这些元素必定逆序。

（2）举例：
如：a,b,c,d,e ,5个元素依次入栈，则如果d先出队，则出队序列可以为：
d,c,b,a的序列已定，e的位置任意。

（三）括号匹配+Catlan数