题目描述题目要求判断给定的出站顺序是否可以通过一个栈即站台实现。初始时列车从AAA方向驶来车厢编号为1,2,…,N1, 2, \ldots, N1,2,…,N按顺序。列车可以进入站台栈暂存也可以直接从AAA到BBB而不进站。站台是单轨道后进先出。需要判断是否能得到指定的出站顺序。输入格式输入包含多个数据块。每个数据块的第一行是一个整数NNN1≤N≤10001 \le N \le 10001≤N≤1000表示车厢数量。接下来若干行每行是一个111到NNN的排列表示目标出站顺序。每个数据块以一行0结束。最后一个数据块以一行0结束。输出格式对于每个目标顺序输出一行Yes或No。每个数据块的输出后跟一个空行。样例输入5 1 2 3 4 5 5 4 1 2 3 0 6 6 5 4 3 2 1 0 0输出Yes No Yes题目分析本题的核心是模拟栈的入栈和出栈过程。初始时车厢按顺序从111到NNN依次到达。需要判断是否能通过栈操作得到目标序列。算法维护一个栈表示站台中的车厢。维护一个变量current\textit{current}current表示下一个可入栈的车厢编号从111开始。遍历目标序列中的每个车厢ttt若current≤t\textit{current} \le tcurrent≤t则将current\textit{current}current到ttt的车厢依次压入栈然后current\textit{current}current更新为t1t1t1最后弹出栈顶即ttt。若栈非空且栈顶等于ttt则弹出栈顶。否则无法得到该序列输出No。若成功处理完所有车厢输出Yes。复杂度分析每个车厢最多入栈一次、出栈一次时间复杂度O(N)O(N)O(N)。代码实现// Rails// UVa ID: 514// Verdict: Accepted// Submission Date: 2016-08-09// UVa Run Time: 0.010s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string line;while(getline(cin,line),line!0){intnstoi(line);while(getline(cin,line),line!0){intnumber,current1;stackintrails;istringstreamiss(line);boolyestrue;while(issnumber){if(numbercurrent)current;elseif(rails.empty()falsenumberrails.top())rails.pop();elseif(numbercurrent){while(currentnumber){rails.push(current);current;}current;}else{yesfalse;break;}}cout(yes?Yes\n:No\n);}cout\n;}return0;}