判断是否为可能的出栈情况&&打印所有的出栈可能

墨蓝 2022-05-10 07:20 163阅读 0赞

## **题目：** ##

[https://blog.csdn.net/dextrad\_ihacker/article/details/50083845][https_blog.csdn.net_dextrad_ihacker_article_details_50083845]

> PopPush城市有一座著名的火车站。这个国家到处都是丘陵。而这个火车站是建于上一个世纪。不幸的是，那时的资金有限。所以只能建立起一条路面铁轨。而且，这导致这个火车站在同一个时刻只能一个轨道投入使用，因为它缺少空间，两列火车将无路可走。具体看下图。
> 
> 当地的惯例是每一列火车从A方向驶向B方向时候，会用某种方式将车厢重组。假设火车将要到达A方向，拥有N个车厢(N<=1000),这些车厢按照递增顺序标记为1到N。负责从组车厢的领导,必须知道是否能从组车厢让它驶出B，而这个重组的序列就是a1\\a2\\a3…aN.帮组他并且写一个程序来判断是否可能按照所要求的车厢顺序。你可以假设，单个的车厢可以从列车上分离出来，在他们进入站台之前。并且他们可以自由移动，知道它们上了B轨道。你也可以假设在任意时候站台可以放下无数的车厢。但是只要一个车厢进入站台，它就不能返回A轨道，同时如果它离开了站台驶向B轨道，它就不能返回站台。
> 
> \--------------------- 本文来自 唐丶莱布尼茨 的CSDN 博客 ，全文地址请点击：https://blog.csdn.net/dextrad\_ihacker/article/details/50083845?utm\_source=copy

![70][]

##  分析思路： ##

1、B中最左边的数肯定是最先出栈的数。取A中最左边的数，和其比较。如果相等，说明是直接入栈，紧接着再出栈。

如果不相等，只能入栈，取A中下一个数字进行比较。

2、B中的数可能是栈顶元素出栈，也可能是A中的元素直接入栈出栈所得。

代码：

#include<iostream>
    #include<stack>
    using namespace std;
    
    int main()
    {
    	int i,n;
    	int target[30];
    	int A=1,B=1;//AB为A,B的游标 
    	stack<int>s;
    	cin>>n;
    	for(i=1;i<=n;i++)//输入目标 
    		cin>>target[i];
    	while(B<=n)
    	{
    		if(A==target[B])//如果相同直接进入出去 
    		{
    			A++;
    			B++;
    		}
    		else if(!s.empty()&&s.top()==target[B])//和栈顶元素进行比较 
    		{
    			s.pop();
    			B++;
    		}
    		else if(A<=n)//都匹配不成，放入栈中 
    		{
    			s.push(A);
    			A++; 
    		}
    		else //否则，嘿嘿。 
    		{
    			printf("NO\n");
    			return 0;
    		}
    	} 
    	printf("YES\n");
    	return 0;
    }

**上面的问题结束，那问总共有多少种出栈方式？能否将他们全部打印出来？**

首先考虑：n个元素进栈，有几种出栈方式？[https://zhidao.baidu.com/question/1951420269191036708.html][https_zhidao.baidu.com_question_1951420269191036708.html]

> 我们把n个元素的出栈个数的记为f(n), 那么对于1,2,3, 我们很容易得出：
> 
> f(1) = 1     //即 1
> 
> f（2) = 2    //即 12、21
> 
> f(3) = 5     //即 123、132、213、321、231
> 
> 然后我们来考虑f(4), 我们给4个元素编号为a,b,c,d, 那么考虑：元素a只可能出现在1号位置，2号位置，3号位置和4号位置(很容易理解，一共就4个位置，比如abcd,元素a就在1号位置)。
> 
> 分析：
> 
> 1) 如果元素a在1号位置，那么只可能a进栈，马上出栈，此时还剩元素b、c、d等待操作，就是子问题f(3)；
> 
> 2) 如果元素a在2号位置，那么一定有一个元素比a先出栈，即有f(1)种可能顺序（只能是b），还剩c、d，即f(2)，     根据乘法原理，一共的顺序个数为f(1) \* f(2)；
> 
> 3) 如果元素a在3号位置，那么一定有两个元素比1先出栈，即有f(2)种可能顺序（只能是b、c），还剩d，即f(1)，
> 
> 根据乘法原理，一共的顺序个数为f(2) \* f(1)；
> 
> 4) 如果元素a在4号位置，那么一定是a先进栈，最后出栈，那么元素b、c、d的出栈顺序即是此小问题的解，即         f(3)；
> 
> 结合所有情况，即f(4) = f(3) + f(2) \* f(1) + f(1) \* f(2) + f(3);
> 
> 规整化，我们定义f(0) = 1；于是f(4)可以重新写为：
> 
> f(4) = f(0)\*f(3) + f(1)\*f(2) + f(2) \* f(1) + f(3)\*f(0)
> 
> 然后我们推广到n，推广思路和n=4时完全一样，于是我们可以得到：
> 
> f(n) = f(0)\*f(n-1) + f(1)\*f(n-2) + ... + f(n-1)\*f(0)
> 
> 即
> 
> [![1f178a82b9014a909b7bffaca2773912b31bee5e.jpg][]][1f178a82b9014a909b7bffaca2773912b31bee5e.jpg 1]

卡特兰数：**f(n)=C(2n,n)/(n+1) (n=0,1,2,...)[卡特兰数（百度百科）][Link 1]**

具体这公式咋出来的，不清楚，但知道它是对的就成。那如何将他们全部打印出来？

[给定入栈顺序，输出所有可能出栈情况及所有情况的总数][Link 2]

> **1先入栈之后有两种选择，1出栈和2入栈，而若2已经入栈之后，在2出栈之前1则不能先行出栈，故对于1我们只需要考虑其在2入栈之前出栈的情况，若1在栈内时2入栈，则1与2只能看成一个整体。**
> 
>     dostack(输入队列，中间栈，输出队列)
>      
>     if(输入队列为空)
>      
>         if(中间栈为空)
>      
>             输出输出队列中的结果
>      
>         else
>      
>     中间栈出栈，放入输出队列
>      
>     dostack(输入队列，中间栈，输出队列)
>      
>     else
>      
>         if(中间栈非空)
>      
>             新建输入队列2、中间栈2、输出队列2
>      
>             中间栈2出栈并放入输出队列2
>      
>     dostack(输入队列2，中间栈2，输出队列2)
>      
>         输入队列出队一个数并压入中间栈
>      
>     dostack(输入队列，中间栈，输出队列)
> 
>

代码：

#include<iostream>
    #include<queue>
    #include<stack>
    using namespace std;
    
    int count;
    
    void print_queue(queue<int> &out)
    {
    	while(!out.empty())
    	{
    		cout<<out.front()<<" ";
    		out.pop();
    	}
    	cout<<endl;
    }
    
    void outstack(queue<int> &in,stack<int> &smid,queue<int> &out)
    {
    	if(in.empty())
    	{
    		if(smid.empty())
    		{
    			count++;
    			print_queue(out); 
    		}
    		else
    		{
    			out.push(smid.top());
    			smid.pop();
    			outstack(in,smid,out);
    		}
    	} 
    	else
    	{
    		if(smid.empty())
    		{
    			smid.push(in.front());
    			in.pop();
    			outstack(in,smid,out);
    		}
    		else
    		{//这里要理解：先出栈和先入栈都有可能，都得列举出来。
    		 //为了不改变原来，调用拷贝构造函数。 
    			queue<int> in1(in);
    			stack<int> smid1(smid);
    			queue<int> out1(out);
    			smid1.push(in1.front());
    			in1.pop();
    			outstack(in1,smid1,out1);
    			out.push(smid.top());
    			smid.pop();
    			outstack(in,smid,out);
    		}
    	}
    }
    
    int main()
    {
    	int i,n;
    	while(cin>>n)
    	{
    		count=0;
    		queue<int> in,out;//放在循环里面，就不用清零 
    		stack<int> smid;
    		for(i=1;i<=n;i++)
    			in.push(i);
    		outstack(in,smid,out);
    		cout<<"共有情况："<<count<<endl;	
    	}
    	return 0;
    }

注：上面递归程序最后一种判断（输入队列不空，栈不空）情况不好理解。

要打印所有的情况：那有两种，打印栈顶元素和打印in的对头元素。这两种都得打印。

那随意谁先打印，谁后打印都行。打印完栈顶元素，递归回退，打印in的对头元素。为了保持原先状态，调用了拷贝构造。

参考文章：

[https://blog.csdn.net/dextrad\_ihacker/article/details/50083845][https_blog.csdn.net_dextrad_ihacker_article_details_50083845]

[https://zhidao.baidu.com/question/1951420269191036708.html][https_zhidao.baidu.com_question_1951420269191036708.html]

**[卡特兰数（百度百科）][Link 1]**

[给定入栈顺序，输出所有可能出栈情况及所有情况的总数][Link 2]

[https_blog.csdn.net_dextrad_ihacker_article_details_50083845]: https://blog.csdn.net/dextrad_ihacker/article/details/50083845
[70]: /images/20220510/763fef5652ac46249b9f0ab9d3a122dd.png
[https_zhidao.baidu.com_question_1951420269191036708.html]: https://zhidao.baidu.com/question/1951420269191036708.html
[1f178a82b9014a909b7bffaca2773912b31bee5e.jpg]: /images/20220510/1b4f4b1f64164defa8f50b6db6685f48.png
[1f178a82b9014a909b7bffaca2773912b31bee5e.jpg 1]: https://gss0.baidu.com/-vo3dSag_xI4khGko9WTAnF6hhy/zhidao/pic/item/1f178a82b9014a909b7bffaca2773912b31bee5e.jpg
[Link 1]: https://baike.baidu.com/item/%E5%8D%A1%E7%89%B9%E5%85%B0%E6%95%B0/6125746?fromtitle=%E5%8D%A1%E5%A1%94%E5%85%B0%E6%95%B0&fromid=9133402&fr=aladdin
[Link 2]: https://blog.csdn.net/qq1169091731/article/details/51284770