train.cpp

模拟堆栈输出从1到n的所有可能输出序列

// DS_03.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <queue>
#include <stack>
using namespace std;

//文件输出函数display，将最终得到的队列输出
void display(queue<int> myqueue, ofstream& out)
{
	while(!myqueue.empty())
	{
		out<<myqueue.front()<<" ";
		myqueue.pop();
	}
	out<<endl;
}
//pop函数，将栈mystack中栈顶元素弹出并压入队列end
void pop (queue<int> start, queue<int> end, stack<int> mystack, int & counter, ofstream& out);
//push函数，将队列start中的队首元素弹出并压入栈mystack
void push (queue<int> start, queue<int> end, stack<int> mystack, int & counter, ofstream& out)
{
		mystack.push(start.front());
		start.pop();
		if(start.empty() && mystack.empty())
		{
			counter++;
			display(end,out);
		}
		if(!start.empty() && mystack.empty())
			push(start,end,mystack,counter,out);
		if(start.empty() && !mystack.empty())
			pop(start,end,mystack,counter,out);
		if(!start.empty() && !mystack.empty())
		{
			pop(start,end,mystack,counter,out);
			push(start,end,mystack,counter,out);
		}
}
void pop (queue<int> start, queue<int> end, stack<int> mystack, int & counter, ofstream& out)
{
		end.push(mystack.top());
		mystack.pop();
		//以下为针对不同情况所进行的操作
		if(mystack.empty() && start.empty())
		{
			counter++;//如果得到一个结果，则令counter加1
			display(end,out);
		}
		if(mystack.empty() && !start.empty())
			push(start,end,mystack,counter,out);
		if(!mystack.empty() && start.empty())
			pop(start,end,mystack,counter,out);
		if(!mystack.empty() && !start.empty())
		{
			pop(start,end,mystack,counter,out);
			push(start,end,mystack,counter,out);
		}
}

void SearchForPermutation(queue<int> start, int & counter, ofstream& out)
{
	//定义空队列和空栈
	queue<int> end;
	stack<int> mystack;
	//递归求解（第一次的操作只能是push）
	push(start, end, mystack, counter,out);
}
	
int main()
{
	queue<int> mytest;
	int N;
	cout<<"请输入测试数据的数量n（n>=1）："<<endl;
	cin>>N;
	while(N<1)
	{
		cout<<"输入数据不在要求范围内！"<<endl;
		cout<<"请重新输入测试数据的数量n（n>=1）："<<endl;
		cin>>N;
	}
	for(int i=0; i<N; i++) mytest.push(i+1);
	int counter=0;//counter即为Catlan number
	ofstream out;
	out.open("outcome.txt");
	out<<"Permutations: "<<endl;
	SearchForPermutation(mytest, counter, out);
	out<<"Catlan number: "<<counter<<endl;
	out.close();
	cout<<"结果已被保存在outcome.txt中"<<endl;
	return 0;
}