火车进站问题
问题描述
假设杭州东火车站只有一条铁路，并且所有火车都从一侧进来，从另一侧出去。那么，如果火车A先进站，然后火车B在火车A离开之前就进站，那么火车A直到火车B离开后才能离开，可参见下图。
现在，假设车站中有n（n<=9）列火车，所有火车都有一个ID（从1到n的编号），火车以O1的顺序进站，您的任务是确定火车是否可以按O2顺序出站。
输入
输入包含几个测试用例。
每个测试用例均包含三部分：一个表示火车数量的整数和两个字符串O1和O2，其中，火车的进站顺序用O1串表示，火车的出站顺序用O2串表示。
输入在文件末尾终止，更多信息参见样例。
输出
如果不能从O1的入站顺序得到O2的出站顺序，请输出字符串“ No.”。
如果能够得到，则请输出"Yes."
然后输出进站和出站的具体方式（“in”表示火车进站，“out”表示火车出站）。
在每个测试用例之后输出一行“ FINISH”。
更多信息参见样例。
样例输入
3 123 321
3 123 312
样例输出
Yes.
in
in
in
out
out
out
FINISH
No.
FINISH
思路：火车进站先进后出问题，显然是栈的应用。题目主要的难点是关注，已经进栈的火车什么时候出栈。详细步骤，请查看下面代码中注释。
AC代码
#include <iostream>
#include <string>
#include <stack>
#include <vector>
#include <queue>using namespace std;int main() {int n = 0;// 题目已经说了以文件的结尾为标志，输入很显然以这种形式输入while (cin >> n) {string o1, o2;cin >> o1 >> o2;queue<char> q1, q2;stack<char> st;// 这里要用vector<string>将入栈和出栈的信息保存，因为不一定"Yes."vector<string> v;// 这里采用的是队列的方式，用两个队列分别装两个序列，然后先对第一个队列进行遍历for (int i = 0; i < n; i++) {q1.push(o1[i]);q2.push(o2[i]);}// 对第一个队列进行遍历while (q1.empty() == false ) {// q1非空时，首先要考虑的是已经进行栈中的火车，因为一旦这时候“盖住了”，后面可能就出不来了，而队列中的火车后面再进入都行。if (st.empty() == false && st.top() == q2.front()) {v.push_back("out");st.pop();q2.pop();// 这里的continue很重要，因为我们要保证栈顶的元素和q2队首元素不同时，才继续将q1队首的元素入栈continue;}char ch = q1.front();// 直接判断要入栈的元素(q1队首元素)和q2队首元素是否相等if (ch == q2.front()) {q1.pop();q2.pop();v.push_back("in");v.push_back("out");}else {// 不等时，先进栈v.push_back("in");st.push(ch);q1.pop();}}// q1处理完之后，现在只剩下了栈中的火车和q2了，一个一个比对即可while (st.empty() == false && st.top() == q2.front() ) {st.pop();q2.pop();v.push_back("out");}// 栈不空则比对不上，输出"No."if (st.empty() == false) {cout << "No." << endl;}else {cout << "Yes." << endl;int len = v.size();for (int i = 0; i < len; i++) {cout << v[i] << endl;}}cout << "FINISH" << endl;}return 0;
}
