棧的應用——火車進站出站問題

問題：

某城市有一個火車站，鐵軌鋪設如下圖所示。有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;
	}
}
           

測試結果：