数据结构上机 经典进出栈问题

　TonyY 等火车无聊的时候，会去观察火车的排列，有一天他思考这么一个问题，火车总站的火车只能进站，要出站的话只能先出最后进站的那辆车，那么知道火车的进站顺序，能不能把它的出站顺序调整成火车站想要的呢？

输入第一行为一个正整数 n 表示火车辆数(编号 1-n)（1<=n<=9）。然后为两个长度为 n 的序列，表示火车的进站顺序和出站顺序。每辆火车刚好进出站各一次。
如果可以调整，输出 Yes 和出入站顺序。如果不能，输出 No。

输入示例

3
123
321

输出示例

Yes
in
in
in
out
out
out

代码:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <string.h>
#include <stack>
using namespace std;

int itrain[100];
int otrain[100];
int order[100];

int isright(int n)
{
	bool flag = true;
	
	int i, j;
	
	int iturn = 1;
	int oturn = 1;
	stack<int> s;
	
	int cnt = 1;
	
	while(oturn <= n || !s.empty())
	{
		if(itrain[iturn] == otrain[oturn])
		{
			oturn++;
			iturn++;
			
			order[cnt++] = 2;
			
			if(oturn > n) break;
			
			continue;
		}
		else if(!s.empty())
		{
			if(s.top() == otrain[oturn])
			{
				order[cnt++] = 0;
				s.pop();
				
				oturn++;
				
				if(oturn > n)break;
				
				continue;
			}
			else
			{
				if(iturn == n)
				{
					flag = false;
					
					break;
				}
				
				s.push(itrain[iturn]);
				iturn++;
				
				order[cnt++] = 1;
			}
		}
		else if(s.empty())
		{
			s.push(itrain[iturn++]);
			order[cnt++] = 1;
			continue;
		}
	}
	
	if(!flag)return -1;
	else return cnt-1;
}

void Print(int n)
{
	int i;
	for(i = 1; i <= n; i++)
	{
		if(order[i] == 2)
		{
			printf("in
out
");
		}
		else if(order[i] == 1)
		{
			printf("in
");
		}
		else if(order[i] == 0)
		{
			printf("out
");
		}
	}
	
}

int main()
{
	int n, i;
	cin >> n;
	getchar();
	
	char c;
	
	for(i = 1; i <= n; i++)
	{
		cin >> c;
		itrain[i] = c - '0';
	}
	
	getchar();
	
	for(i = 1; i <= n; i++)
	{
		cin >> c;
		otrain[i] = c - '0';
	}
	
	int t = isright(n);
	
	if(t != -1)
	{
		printf("Yes
");
		Print(t);
	}
	else printf("No
");
	
	return 0;
}