n個の要素がスタックに入り、すべてのスタックシーケンス-カトラン数-再帰を出力する
1498 ワード
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
void printAllOutStackSeq( queue inQueue, int n, stack st, queue 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 stCopy = st; // ,
queue outCopy = out;
if( !st.empty() ) // , ,push
{
out.push( st.top() );
st.pop();
printAllOutStackSeq( inQueue, n, st, out );
}
if( !inQueue.empty() ) // , ,
{
stCopy.push( inQueue.front() );
inQueue.pop();
printAllOutStackSeq( inQueue, n, stCopy, outCopy );
}
return;
}
int main()
{
int ret = 0;
int a[] = { 1, 2, 3, 4 };
queue inQueue;
for( int i = 0; i < 4; i++ )
{
inQueue.push( a[i] );
}
int n;
stack st;
queue out;
printAllOutStackSeq( inQueue, 4, st, out );
return ret;
}
/*
n , : C(2n,n)/(n+1)
./a.out
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 3 1
3 2 1 4
3 2 4 1
3 4 2 1
4 3 2 1
./a.out|wc -l
14
*/