栈的应用——火车进站出站问题

问题：

某城市有一个火车站，铁轨铺设如下图所示。有n节车厢从A方向驶入车站，按照进站顺序编号为1~n。你的任务是输出所有可能的出站序列。例如，出站顺序(5 4 1 2 3)是不可能的，但(5 4 3 2 1)是可能的。

为了重组车厢，你可以借助中转站C。这是一个可以停放任意多节车厢的车站，但由于末端封顶，驶入C的车厢必须按照相反的顺序驶出C。在任意时刻，只有两种选择：A->C和C->B.

代码如下：

main函数：

//在中转站C中，车厢符合先进后出的原则，因此是一个栈
#include<iostream>
#include<stack>
using namespace std;
void perm(int *, const int, const int);
void print(int *, const int);
int main()
{
	int n;
	while (cin >> n){//测试多组数据
		int *train = new int[n];
		for (int i = 0; i < n; i++)
			train[i] = i + 1;//初始化
		perm(train, 0, n);//全排列
		delete[]train;
	}
}
           

perm函数：

void perm(int *a, const int k, const int n)
{//递归全排列算法
	if (k == n-1)
		print(a, n);//判断生成的序列是否满足要求
	else
	{
		for (int i = k; i < n; i++)
		{
			char temp = a[k]; a[k] = a[i]; a[i] = temp;
			perm(a, k + 1, n);
			temp = a[k]; a[k] = a[i]; a[i] = temp;
		}
	}
}
           

print函数：

void print(int *a, const int n)
{//判断序列，若符合先进后出原则则输出
	stack<int> s;
	int A= 1, B = 0;//B为a数组指针，A为原序列指针
	bool flag = true;//标志旗子
	while (B < n){
		if (A == a[B]){ A++; B++; }//表示车厢直接由A->C->B
		else if (!s.empty() && a[B] == s.top()){//栈不空，并且栈顶元素与目标序列相等
			s.pop();//C栈顶元素出栈,C->B
			B++;
		}
		else if (A <= n){//A->C
			s.push(A);
			A++;
		}
		else{//不满足上述所有情况，说明该序列不可能出现
			flag = false;
			break;
		}
	}
	if (flag){//符合条件，输出该序列
		for (int i = 0; i < n; i++)
			cout << a[i] << " ";
		cout << endl;
	}
}
           

测试结果：