给定n个元素的集合S，依次入栈，问：
1）有多少种合法的出栈序列？卡特兰数
2）分别是什么？编程
3）如果给出一个另一个由S中所有元素不重复组成的序列q，如何判断q是一个合法的出栈序列。编程题
4）如果S={1,2,3,4,5,6},入栈顺序是1，2，3，4，5，现在知道出栈序列q的前两个元素依次是，2， 4则第三个元素有几种可能？分别是什么？自己想，如何编程实现
- 若第一个出栈的序数是k，则分为二个序列，第一个序列的个数为k-1，第二个序列的个数为n-k，所以f(n)就可以等价于k-1的出栈序列种数乘以序列个数为n-k的出栈序列种数，f(n)=f(k-1)*f(n-k)，k可以取1~n，所以f(n)=f(0)f(n-1)+f(1)f(n-2)+……+f(n-1)f(0)，另f(0)=1,f(1)=1，则给定n个元素，合法的出栈序列的种数有：C(2n,n)-C(2n,n+1)
2.
#include <iostream>
#include <stack>
#include <queue>
#include <algorithm>
#include <string.h>
#include <cstdio>
#include <stdlib.h>
#include <cctype>
#include <stack>
#include <queue>
using namespace std;
void printAllOutStackSeq( queue<int> inQueue, int n, stack<int> st, queue<int> out )
{
if( n <= 0 || ( inQueue.empty() && st.empty() && out.empty() ) )
{
return;
}
if( out.size() == n )
{
while( !out.empty() )
{
cout << out.front() << ' ';
out.pop();
}
cout << endl;
return;
}
stack<int> stCopy = st; // 备份一下，否则储转
queue<int> outCopy = out;
if( !st.empty() ) // 出栈，将元素出栈，push到结果队列中
{
out.push( st.top() );//取出栈顶元素，放到队列out中
st.pop();//弹出栈顶元素
printAllOutStackSeq( inQueue, n, st, out );
}
if( !inQueue.empty() ) // 入栈，将输入队列出队，进行入栈
{
stCopy.push( inQueue.front() );//将inQueue队列的第一个元素放到栈stCpoy中
inQueue.pop();//弹出队列的第一个元素
printAllOutStackSeq( inQueue, n, stCopy, outCopy );
}
return;
}
int main()
{
int k,i;
cout<<"请输入入栈的元素个数"<<endl;
cin>>k;
int a[k];
cout<<"请输入"<<k<<"个元素" <<endl;
for(i=0;i<k;i++)
cin>>a[i];
queue<int> inQueue;
for( int j = 0; j < k; j++ )
{
inQueue.push( a[j] );
}
int n;
stack<int> st;
queue<int> out;
cout<<"出栈顺序有："<<endl;
printAllOutStackSeq( inQueue, k, st, out );
return 0;
}
编辑
编辑
3.
#include <iostream>
#include <string>
//12345
//10324
using namespace std;
int main(){
while(true){
string s1,s2;
cout<<"请输入入栈顺序"<<endl;
cin>>s1;
cout<<"请输入出栈顺序"<<endl;
cin>>s2;
int n=s1.size();
int a[n];
int i,j,k;
int min;
int number1,number2=1;
for(i=0;i<n;i++){
a[i]=s1.find(s2[i]);
//cout<<a[i]<<endl;
}
for(i=0;i<n;i++){
min=a[i];
for(j=i+1;j<n;j++)
{
if(a[j]<a[i])
{
min=a[j];
number1=1;
break;
}
}
number2=1;
if(number1==1)
{
for(k=j+1;k<n;k++)
{
if(a[k]<a[i])
{
if(a[k]<min)
min=a[k];
else
{
number2=0;
break;
}
}
}
}
if(number2==0)
{
cout<<"该出栈顺序是错误的"<<endl<<endl;
break;
}
}
if(number2==1)
cout<<"该出栈顺序是正确的"<<endl<<endl;
}
return 0;
}
编辑
4. 如果入栈顺序为1，2，3，4，5，出栈顺序的前二个为2，4，此时比2小的只有1，比4小的数有1和3，那么出栈顺序规律中，每一个元素的后面比自己小的数，出栈顺序必须是降序排列，那么1肯定在3的后面，而5的位置可以随便出，所以2，4先出栈时，只有三种情况（2,4,3,5,1）(2,4,5,3,1) (2,4,3,1,5)，则第三个元素只有2中可能，只有3或者5。
#include <iostream>
#include <stack>
#include <queue>
#include <algorithm>
#include <string.h>
#include <cstdio>
#include <stdlib.h>
#include <cctype>
#include <stack>
#include <queue>
using namespace std;
void printAllOutStackSeq( queue<int> inQueue, int n, stack<int> st, queue<int> out )
{
int b[n];
int h=0,t=0;
if( n <= 0 || ( inQueue.empty() && st.empty() && out.empty() ) )
{
return;
}
if( out.size() == n )
{
while( !out.empty() )
{
b[h]=out.front();
//cout << out.front() << ' ';
out.pop();
h++;
//cout<<b[h-1] ;
}
if(b[0]==2&&b[1]==4){
cout<<"出栈顺序的前二个元素为2，4，则出栈的第三个元素为："<<b[2]<<endl;
}
//cout<<"宁";
//cout << endl;
return;
}
stack<int> stCopy = st; // 备份一下，否则储转
queue<int> outCopy = out;
if( !st.empty() ) // 出栈，将元素出栈，push到结果队列中
{
out.push( st.top() );//取出栈顶元素，放到队列out中
st.pop();//弹出栈顶元素
printAllOutStackSeq( inQueue, n, st, out );
}
if( !inQueue.empty() ) // 入栈，将输入队列出队，进行入栈
{
stCopy.push( inQueue.front() );//将inQueue队列的第一个元素放到栈stCpoy中
inQueue.pop();//弹出队列的第一个元素
printAllOutStackSeq( inQueue, n, stCopy, outCopy );
}
return;
}
int main()
{
int k,i;
cout<<"请输入入栈的元素个数"<<endl;
cin>>k;
int a[k];
cout<<"请输入"<<k<<"个元素" <<endl;
for(i=0;i<k;i++)
cin>>a[i];
queue<int> inQueue;
for( int j = 0; j < k; j++ )
{
inQueue.push( a[j] );
}
int n;
stack<int> st;
queue<int> out;
//cout<<"出栈顺序有："<<endl;
printAllOutStackSeq( inQueue, k, st, out );
return 0;
}
编辑
